3

PyGraphviz を使用して二分探索木を描画しています。エッジがノードに循環されるため、PyGraphviz を使用して複製ノードを作成できません。

たとえば、次のコードは 5 つのノードのみを生成し、重複するノードを除外します。各ノードに一意のインデックスを付けようとしましたが、問題は解決しません。

import pygraphviz as pgv
tree = pgv.AGraph(directed=True, strict=True)
tree.add_node(2)
tree.add_node(3)
tree.add_node(1)
tree.add_node(7)
tree.add_node(3)
tree.add_node(9)
tree.add_node(2)
tree.write('foo.dot')
image = pgv.AGraph('foo.dot')
image.layout()
image.draw('foo.pdf')
image.close()

重複ノードがありません

BSTに描画する私のコード:

import pygraphviz as pgv
import random


class Node:
    insertion_step = []

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def addNode(self, data):
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
                self.printSubtree()
            else:
                self.left.addNode(data)  # recursively calling addNode method
        else:
            if self.right is None:
                self.right = Node(data)
                self.printSubtree()
            else:
                self.right.addNode(data)

    def printSubtree(self):
        if not (self.left is None or self.right is None):
            print self.left.data, self.data, self.right.data
            self.insertion_step.append((self.left.data, self.data, self.right.data))

        elif self.left is None and not self.right is None:
            print None, self.data, self.right.data
            self.insertion_step.append((None, self.data, self.right.data))

        elif not self.left is None and self.right is None:
            print self.left.data, self.data, None
            self.insertion_step.append((self.left.data, self.data, None))

        else:
            print None, self.data, None
            self.insertion_step.append((None, self.data, None))

    def drawTree(self, tree, f):
        print self.insertion_step
        for step in self.insertion_step:
            if not step[0] is None:
                tree.add_node(step[0], color='goldenrod2', style='filled')

            tree.add_node(step[1], color='goldenrod2', style='filled')

            if not step[2] is None:
                tree.add_node(step[2], color='goldenrod2', style='filled')

            if step[0] is None or step[1] is None or step[2] is None:
                tree.add_node('', color='goldenrod1', shape='box', style='filled')

            if not step[0] is None:
                tree.add_edge(step[1], step[0], color='sienna', style='filled')
            else:
                tree.add_edge(step[1], '', color='sienna', style='filled')
            if not step[2] is None:
                tree.add_edge(step[1], step[2], color='sienna', style='filled')
            else:
                tree.add_edge(step[1], '', color='sienna', style='filled')

        tree.write(f)
        img = pgv.AGraph(f)
        img.layout()
        img.draw(f.split('.')[0] + '.pdf')
        img.close()


if __name__ == '__main__':
    lst = [random.randint(1, 10) for i in range(10)]
    print lst
    n = Node(lst[0])
    n.printSubtree()
    for num in lst[1:]:
        n.addNode(num)

    tree = pgv.AGraph(directed=True, strict=True)
    filename = 'tree.dot'
    n.drawTree(tree, filename)

BST

上の図からわかるように、重複ノードが作成されていないため、エッジは循環しています。これを達成する方法を教えてください。図の四角いボックスは空のノードを表します。

4

2 に答える 2

1

GraphViz は、グラフを単純化します。これを防ぐには、同じラベルの異なるノードを追加できます。たとえば、2 の代わりに 21 と 22 を追加して、それらに 2 のラベルを付けます。その後、それらを別々に使用できます。ラベルはノードのプロパティです。

ノードとラベルの使用を説明するために、上記のサンプル フォームを使用しました。ノードのさまざまなデータ型を示します。同じラベルのものもあります。描画されたグラフには、ノード ID で作成した混乱は表示されませんが、ラベルのみが表示されます。もちろん、たとえそれが単なる一意の番号であっても、BST に適切な命名スキームを選択するでしょう。

import pygraphviz as pgv
import random
tree = pgv.AGraph(directed=True, strict=True)
tree.add_node("2.1", label='2')
tree.add_node(3.0, label='3')
tree.add_node(3.1, label='3')
tree.add_node(random.randint(1, 1000000), label='7')
tree.add_node(random.randint(1, 1000000), label='7')
tree.add_node(random.randint(1, 1000000), label='7')
tree.add_node("2.2", label='2')
tree.write('foo.dot')
image = pgv.AGraph('foo.dot')
image.layout()
image.draw('foo.pdf')
image.close()

これは私を得る：サンプル グラフ、ノードのみ、エッジなし

編集：サンプルコードを追加しました。

于 2013-04-01T22:59:57.427 に答える