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.
 **********************************************************************/ 
 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