Find all paths

Find all paths from given source, which covers all vertices exactly once.

We can solve this problem by using backtracking.

Step 1: Start with source, mark it as visited. If all nodes are visited print path here.

Step 2:for(V in vertices (v1, v2, … vn){

         if V is unvisited, and there is a path from source to V. Make V as source and repeat step 1.

Mark V as unvisited.

}

Following is the java program for above problem.

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.Objects;

/**
 * Get all possible paths from given matrix
 * 
 * @author harikrishna_gurram
 */
public class FindPaths {

 private List<String> paths;
 private BitSet visited;
 private int pathMatrix[][];
 private int length;

 public List<String> getPaths(int pathMatrix[][], int source) {
  /* Checking for pre conditions */
  Objects.nonNull(pathMatrix);
  if (pathMatrix.length != pathMatrix[0].length)
   throw new IllegalArgumentException(
     "Array must be rectangular (rows and columns must equal)");

  if (source < 0 || source > pathMatrix[0].length - 1)
   throw new IllegalArgumentException("Source is invalid");

  /* Initialize all variables */
  visited = new BitSet(pathMatrix[0].length);
  paths = new ArrayList<>();
  this.pathMatrix = pathMatrix;
  length = pathMatrix[0].length;

  /* Set the source and start finding paths */
  visited.set(source);
  findPathFrom(source, "" + source);

  return paths;
 }

 private void findPathFrom(int source, String path) {

  if (visited.cardinality() == length) {
   paths.add(path);
  }

  for (int i = 0; i < length; i++) {
   if (source != i && visited.get(i) == false
     && pathMatrix[source][i] != 0) {
    visited.set(i);
    findPathFrom(i, path + "," + i);
    visited.flip(i);
   }
  }

 }

}

Following is the junit test case for above program.

import static org.junit.Assert.assertEquals;

import java.util.List;

import org.junit.Test;

public class FindPathsTest {

 @Test
 public void test1() {
  int arr[][] = { { 0, 1, 1, 0 }, { 1, 0, 1, 1 }, { 1, 1, 0, 0 },
    { 0, 1, 0, 0 } };
  FindPaths paths = new FindPaths();

  List<String> possiblePaths = paths.getPaths(arr, 0);

  assertEquals(possiblePaths.get(0), "0,2,1,3");
 }

 @Test
 public void test2() {
  int arr[][] = { { 0, 1, 1, 1, 0 }, { 1, 0, 0, 0, 1 },
    { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 1 }, { 0, 1, 0, 1, 0 } };

  FindPaths paths = new FindPaths();

  List<String> possiblePaths = paths.getPaths(arr, 0);

  assertEquals(possiblePaths.get(0), "0,1,4,3,2");
  assertEquals(possiblePaths.get(1), "0,2,3,4,1");
 }
}