"""
Digraph class written by Rob Hochberg, 3/1/09
Represents a graph as a dictionary of lists.

Notice how there are no separate "vertex" or
"edge" classes.


"""
class Digraph:
    # constructor
    def __init__(self, g):
        self.g = g

    # return a list of vertices
    def V(self):
        return list(self.g.keys())

    # return the vertices adjacent to v
    def Adj(self,v):
        return list(self.g[v])

    # Find all simple (no repeated vertices) paths from
    # start to end in the graph.  Notice how the graph
    # class has no "parent" or "color" members, until this
    # method adds them.  
    def path(self, start, end):
        self.parent = {}
        self.color = {}
        self.numPaths = 0
        for v in self.V():
            self.color[v] = 'white'
        p = [start]
        self.parent[start] = start
        self.color[start] = 'gray'
        nextVs = self.Adj(start)
        for v in nextVs:
            self.parent[v] = start
            self.path_visit(v, end)
        print("There were", self.numPaths, "paths")

    # The recursive step for finding all paths.
    def path_visit(self, v, end):
        if v == end:    # Print the path
            self.numPaths = self.numPaths + 1
            pe = end
            thePath = [pe]
            while self.parent[pe] != pe:
                pe = self.parent[pe]
                thePath.insert(0, pe)
            print(thePath)
            return
       
        self.color[v] = 'gray'
        nextVs = self.Adj(v)
        for w in nextVs:
            if self.color[w] == 'white':
                self.parent[w] = v
                self.path_visit(w, end)
        self.color[v] = 'white'
    
"""
Now some examples of commandline usage of the Digraph class
"""

L = {1:[2, 4], 2:[3, 5], 3:[6], 4:[5, 7], 5:[6, 8], 6:[9], 7:[8], 8:[9], 9:[]}
"""  Here is the graph that the list above builds
1 --> 2 --> 3
|     |     |
v     v     v
4 --> 5 --> 6
|     |     |
v     v     v
7 --> 8 --> 9
"""
"""Uncomment out the list below to add some edges, but keep the graph acyclic"""
#L.update({7:[2, 8], 8:[3, 9]})

"""Uncomment out the list below to add edges, which introduce cycles, but
   the path algorithm still counts correctly"""
#L.update({3:[1, 6], 6:[4, 9]})

# Now make the graph
g = Digraph(L)

""" to test the class, type g.path(1, 9), for example, to find all paths
from 1 to 9.
"""