# Count Paths in Graphby 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.
**********************************************************************/
package algorithm.graph;

import java.util.ArrayList;
import java.util.List;

public class CountPathsInGraph {

int paths(Integer[][] G, int s, int e) {
return pathsDFS(G, s, e);
}

int pathsDFS(Integer[][] G, int s, int e) {
int counter = 0;
for (int x : adjacency(G, s)) {
if (x == e) {
counter++;
} else {
counter += pathsDFS(G, x, e);
}
}
return counter;
}

Integer[] adjacency(Integer[][] G, int s) {
List<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < G.length; i++) {
if (G[s][i] != null) {
}
}
return result.toArray(new Integer[0]);
}
}```
```package algorithm.graph;

import static org.junit.Assert.*;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

public class CountPathsInGraphTest {

CountPathsInGraph graph;

@Before
public void setUp() throws Exception {
graph = new CountPathsInGraph();
}

@After
public void tearDown() throws Exception {
graph = null;
}

@Test
public void testPaths() {
final Integer NO = null;
Integer[][] 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
};
assertEquals(4, graph.paths(G, 0, 2));
assertEquals(5, graph.paths(G, 0, 3));
assertEquals(0, graph.paths(G, 3, 0));
}//testPaths
}//CountPathsInGraphTest```