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