graph.py

def graphs():
    """
    find longest path from X node, max depth from X node, deepst node from x node, all paths
    
    """
    graphA = {'1' : ['2','3'],
              '2' : ['1','4','5'],
              '3' : ['1'],
              '4' : ['2','6','7'],
              '5' : ['2','8'],
              '6' : ['4'],
              '7' : ['4','9','a'],
              '8' : ['5','b'],
              '9' : ['7'],
              'a' : ['7'],
              'b' : ['8']
    }
    """ *all links are bidirectional
          1
         / \
        2   3
       / \
      4   5
     / \   \
    6   7   8
       / \   \
      9   a   b
    """
    
    graphB ={'A': ['B', 'C'],
             'B': ['C', 'D'],
             'C': ['D', 'B'],
             'D': ['C'],
             'E': ['F'],
             'F': ['C']
            }
    """  *this graph has unidirectional links
          A
         / \
        B - C
         \ / \
          D   F
             /
            E
    """
    def longestPath(graph,start, path=[]):
        nodes = {}
        path=path+[start]
        for node in graph[start]:
            if node not in path:
                deepestNode,maxdepth,maxpath = longestPath(graph,node,path)
                nodes[node] = (deepestNode,maxdepth,maxpath)
        maxdepth = -1
        deepestNode = start
        maxpath = []
        for k,v in nodes.iteritems():
            if v[1] > maxdepth:
                deepestNode = v[0]
                maxdepth = v[1]
                maxpath = v[2]
        return deepestNode,maxdepth +1,maxpath+[start]
    print longestPath(graphB,'A')
    
if __name__ == '__main__':
    graphs()