Count Paths in Graph
/********************************************************************* * 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) { result.add(i); } } 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