How to create duplicate nodes in PyGraphviz?

Question

I am using PyGraphviz to draw a Binary Search Tree. I am unable to create duplicate nodes using PyGraphviz because of which the edges are cycled back to nodes.

For Example, the following code produces only 5 nodes, leaving out the duplicate nodes. I tried labeling each node with a unique index but that does not fix the issue.

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()

My code to draw to 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)

As you can see from the figure above, the edges are in cycles since duplicate nodes are not created. Please suggest me a way to achieve this. Square box in the figure represents empty node.

Answer 1

The node name is what lets GraphViz track individual nodes, so they have to be named uniquely.

You are, however, free to use duplicate labels. The labels is what will be shown in the end result, and labels for nodes are by default set to the node name.

Set the label together with the node name when creating:

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)

Note that internally, everything is converted to strings here.

This results in:

You'll need to refactor your code to generate unique ids for your unique nodes, then use those ids to create your edges. Here I just traverse your tree with a stack with parent ids:

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()

which gives:

To straighten out the edges between nodes with equal values you need to experiment with adding weights to the edges:

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()

which results in:

You can tweak the exact weights.

Answer 2

GraphViz is simplifying the graph for you. To hinder it doing so you could add different nodes with the same label, e.g. add 21 and 22 instead of 2 and label them 2. Then you can use them separately. Label is a property of the node.

I took your sample form above to illustrate the use of nodes and labels. It demonstrates different data types for nodes. Some have the same label. The drawn graph does not show the mess I created with node IDs though but just the labels. Of course you would pick a sensible naming scheme for your BST, even if it might be just unique numbers.

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()

This gets me:

Edit: Added example code.