Graphviz is an excellent and free graph visualization program that provides a simple way to generate graphs for pretty much anything with a variety of layouts. The Graphviz layout programs take descriptions of graphs in a simple text language. These descriptions can be created and edited manually but are more usually generated programatically – especially for large data sets. 

This post provides an example of using the Visitor pattern to generate a directed graph visualization of a trie using the Graphviz dot layout manager. Full python source code listing of this example is available here.

A Trie class is used to represent the trie data structure. This class is composed of a set of nodes representing the trie nodes. These nodes are anchored via a root node. The code for adding data to the trie is omitted for clarity but is available in the full source listing. 

class Trie:
    def __init__(self):
        self.root = Node()

    def walk(self, visitor):
        self.root.walk(visitor)

From a visitor pattern perspective, the Node.walk() method is used to traverse the nodes and to pass each node encountered to the visitor object.

class Node:
    def walk(self, visitor):
        visitor.visitNode(self)
        for nextNode in self.children.values():
            nextNode.walk(visitor)

The GraphvizVisitor class is a Visitor subclass that generates the appropriate dot language representation for each visited node.

# Visitor interface
class Visitor:
    def visitNode(self, node):
        pass

# Visitor subclass that generates Graphviz dot file contents.
class GraphvizVisitor:
    def __init__(self, dotGen):
        self.dotGen = dotGen

    def visitNode(self, node):
        if node.isOutputNode:
            dotGen.setNodeProperty(node.name, 'shape', 'doublecircle')
        for edge, nextNode in node.children.items():
            dotGen.addLink(node.name, nextNode.name, edge)

The dotGen object is an instance of the DotFileGenerator class which is used as a simple utility class to generate the dot file.

class DotFileGenerator:
    def __init__(self, name):
        self.name = name
        self.outf = open(name+'.dot', 'w')
        print >> self.outf, 'digraph %s {' % (self.name)
        print >> self.outf, 'trankdir="LR";'
        print >> self.outf, 'tnode [shape = "circle"];'

    def setNodeProperty(self, nodeName, property, value):
        print >> self.outf, 't%s [%s = %s];' %(nodeName, property, value)

    def addLink(self, lhs, rhs, label):
        print >> self.outf, 't%s -> %s [label = %s];' % (lhs, rhs, label)

    def close(self):
        self.outf.close()

Consider the following example to illustrate the generated output:

# Build a trie
trie = Trie()
trie.addPattern("abc")
trie.addPattern("abcdef")
trie.addPattern("abcxyz")
trie.addPattern("abdef")

# Generate the dot file contents by walking the trie
dotGen = DotFileGenerator('trie')
visitor = GraphvizVisitor(dotGen)
trie.walk(visitor)
dotGen.close()

This produces the following dot file contents:

digraph trie {
	rankdir="LR";
	node [shape = "circle"];
	0 -> 1 [label = a];
	1 -> 2 [label = b];
	2 -> 3 [label = c];
	2 -> 10 [label = d];
	3 [shape = doublecircle];
	3 -> 7 [label = x];
	3 -> 4 [label = d];
	7 -> 8 [label = y];
	8 -> 9 [label = z];
	9 [shape = doublecircle];
	4 -> 5 [label = e];
	5 -> 6 [label = f];
	6 [shape = doublecircle];
	10 -> 11 [label = e];
	11 -> 12 [label = f];
	12 [shape = doublecircle];
}

After passing this dot file through Graphviz, we get: