This is a work in progress, there’s a lot of complex questions you can ask about graphs, but I though it was neat that you could produce an actual graphy looking thing in so few lines of code. This is a directed graph, and you use the graph object to first create nodes, and then define (unweighted) edges between them or to themselves. The __repr__() method just lists the node data, whatever that is, with an ASCII arrow pointing to another node’s data.

Bare Bones

This is was my first attempt at implementing a graph. Next, I’ll look at depth first and breadth first searching.

class DirectedGraph:
    
    linkCount = 0
    
    class Node:
        def __init__( self, data ):
            self.data = data
            self.links = []
        def pointsTo( self, node ):
            self.links.append( node )
            DirectedGraph.linkCount += 1
    
    def __init__( self ):
        self.nodes = []
        self.nodeCount = 0
    def newNode( self, data ):
        node = self.Node( data )
        self.nodes.append( node )
        self.nodeCount += 1
        return node
    def __repr__( self ):
        result = ""
        for node in self.nodes:
            for link in node.links:
                result += "{0} --> {1}\n".format( node.data, link.data )
        return result
    
dg = DirectedGraph()
n0 = dg.newNode("A")
n1 = dg.newNode("B")
n2 = dg.newNode("C")
n0.pointsTo( n1 )
n1.pointsTo( n2 )
n2.pointsTo( n0 )
n2.pointsTo( n2 )
assert dg.linkCount == 4
assert dg.nodeCount == 3

Searching

What’s neat about this code is that it shows that the depth first and breadth first algorithms are essentially the same except for your choice of internal data structure. If you add child nodes to a queue, then you get breadth first behavior, but if you add child nodes to a stack, then you get depth first behavior. I mean, you could define depth first searches recursively, but then you wouldn’t see the beauty of that symmetry between depth first and breadth first searches.

class DirectedGraph:
    
    linkCount = 0
    
    class Node:
        def __init__( self, data ):
            self.data = data
            self.links = []
            self.visited = False
        def pointsTo( self, node ):
            self.links.append( node )
            DirectedGraph.linkCount += 1
    
    def __init__( self ):
        self.nodes = []
        self.nodeCount = 0
    def unvisit( self ):
        for node in self.nodes:
            node.visited = False
    def newNode( self, data ):
        node = self.Node( data )
        self.nodes.append( node )
        self.nodeCount += 1
        return node
    def search( self, node, method ):
        self.unvisit()
        # `data` is short for `data structure`
        data = [ node ]
        while True:
            if len( data ) == 0:
                break
            # treat `data` as a stack
            if method == "depth first":
                node = data.pop()
            # treat `data` as a queue
            elif method == "breadth first":
                node = data.pop(0)
            if node.visited == True:
                continue
            node.visited = True
            print "visiting {}".format( node.data )
            for link in node.links:
                data.append( link )
    def depthFirstSearch( self, node ):
        self.search( node, "depth first" )
    def breadthFirstSearch( self, node ):
        self.search( node, "breadth first" )
    def __repr__( self ):
        result = ""
        for node in self.nodes:
            for link in node.links:
                result += "{0} --> {1}\n".format( node.data, link.data )
        return result