Count Paths in Graph
by Isai Damier, Android Engineer @ Google

#=======================================================================
# Author: Isai Damier
# Title:  Count Paths in Graph
# Project: geekviewpoint
# Package: algorithm.graph
#
# Statement:
#   Given a directed acyclic graph G, a source vertex s, and
#   a terminus t count all the paths from s to t?
#
# Time-complexity: O(E)
#   where E is the number of edges in the graph.
#
# Depth First Search:
#
#   All you have to do here is use depth first search (DFS) to traverse
#   the edges of the graph starting from s and count how many time you
#   reach e.
#=======================================================================
 
 


class CountPathsInGraph( object ):

  def __init__( self ):
    '''
      Constructor
    '''

  def paths( self, G, s, e ) :
    return self.pathsDFS( G, s, e )

  def pathsDFS( self, G, s, e ) :
    counter = 0
    for x in self.adjacency( G, s ) :
      if x == e:
        counter += 1
      else:
        counter += self.pathsDFS( G, x, e )

    return counter


  def adjacency( self, G, s ) :
    result = []
    for i in range( len( G ) ):
      if G[s][i] is not None:
        result.append( i )

    return result

import unittest
from graph.CountPathsInGraph import CountPathsInGraph

class Test( unittest.TestCase ):

  def testPaths( self ):
    dfs = CountPathsInGraph()
    NO = None
    G = [
      [NO, 1, NO, NO, 4, NO, NO, NO, NO, NO, NO], # 0
      [NO, NO, 2, NO, NO, NO, NO, NO, NO, NO, NO], # 1
      [NO, NO, NO, 3, NO, NO, NO, NO, NO, NO, NO], # 2
      [NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO], # 3
      [NO, NO, NO, NO, NO, 5, 6, NO, NO, NO, NO], # 4
      [NO, NO, 2, NO, NO, NO, NO, NO, NO, NO, NO], # 5
      [NO, NO, NO, NO, NO, NO, NO, 7, NO, NO, NO], # 6
      [NO, NO, 2, NO, NO, NO, NO, NO, 8, NO, 10], # 7
      [NO, NO, NO, 3, NO, NO, NO, NO, NO, NO, NO], # 8
      [NO, NO, 2, NO, NO, NO, NO, NO, NO, NO, NO], # 9
      [NO, NO, NO, NO, NO, NO, NO, NO, NO, 9, NO] # 10
    ]
    self.assertEquals( 4, dfs.paths( G, 0, 2 ) )
    self.assertEquals( 5, dfs.paths( G, 0, 3 ) )
    self.assertEquals( 0, dfs.paths( G, 3, 0 ) )