# 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 ) )
```