# Simple Directed Graph in Python

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:

class Node:
def __init__( self, data ):
self.data = data
def pointsTo( self, node ):

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:
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.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:

class Node:
def __init__( self, data ):
self.data = data
self.visited = False
def pointsTo( self, node ):

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
node = data.pop(0)
if node.visited == True:
continue
node.visited = True
print "visiting {}".format( node.data )