python-2.7 - 如何在 PyGraphviz 中创建重复节点？

Question

我正在使用 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)

从上图中可以看出，由于没有创建重复节点，因此边是循环的。请建议我一种实现此目标的方法。图中的方框代表空节点。

Answer 1

节点名称让 GraphViz 能够跟踪各个节点，因此它们必须具有唯一的命名。

但是，您可以自由使用重复的标签。标签是将在最终结果中显示的内容，节点的标签默认设置为节点名称。

创建时将标签与节点名称一起设置:

tree.add_node(1, label=2)
tree.add_node(2, label=3)
tree.add_node(3, label=1)
tree.add_node(4, label=7)
tree.add_node(5, label=3)
tree.add_node(6, label=9)
tree.add_node(7, label=2)

请注意，在内部，所有内容都被转换为字符串。

这会导致:

您需要重构代码，为唯一节点生成唯一 ID，然后使用这些 ID 创建边。在这里，我只是用带有父 ID 的堆栈遍历你的树:

def drawTree(self, tree, f):
    id = 0
    nodes = [(None, self)]  # queue with nodes to process

    while nodes:
        parent, node = nodes.pop(0)
        tree.add_node(id, label=node.data, color='goldenrod2', style='filled')
        if parent is not None:
            tree.add_edge(parent, id, color='sienna', style='filled')

        if node.left is not None:
            nodes.append((id, node.left))
        else:
            none_id = '{}_left_none'.format(id)
            tree.add_node(none_id, label='', color='goldenrod1', shape='box', style='filled')
            tree.add_edge(id, none_id, color='sienna', style='filled')

        if node.right is not None:
            nodes.append((id, node.right))
        else:
            none_id = '{}_right_none'.format(id)
            tree.add_node(none_id, label='', color='goldenrod1', shape='box', style='filled')
            tree.add_edge(id, none_id, color='sienna', style='filled')

        id += 1

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

给出:

要拉直具有相等值的节点之间的边缘，您需要尝试向边缘添加权重:

def drawTree(self, tree, f):
    id = 0
    nodes = [(None, self)]  # queue with nodes to process

    while nodes:
        parent, node = nodes.pop(0)
        tree.add_node(id, label=node.data, color='goldenrod2', style='filled')

        if parent is not None:
            weight = 1
            if tree.get_node(parent).attr['label'] == str(node.data):
                # same value, increase weight of edge to straighten it.
                weight = 10
            tree.add_edge(parent, id, color='sienna', style='filled', weight=weight)

        if node.left is not None:
            nodes.append((id, node.left))
        else:
            none_id = '{}_left_none'.format(id)
            tree.add_node(none_id, label='', color='goldenrod1', shape='box', style='filled')
            tree.add_edge(id, none_id, color='sienna', style='filled')

        if node.right is not None:
            nodes.append((id, node.right))
        else:
            none_id = '{}_right_none'.format(id)
            tree.add_node(none_id, label='', color='goldenrod1', shape='box', style='filled')
            tree.add_edge(id, none_id, color='sienna', style='filled')

        id += 1

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

结果是:

您可以调整精确的权重。