Wednesday 5 August 2015

Find all paths from source to destination

Find all possible paths from source to destination.

Step 1: Start with source, mark it as visited. If source is equal to destination, it is valid path from source to destination

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.

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

public class PathFromSrcToDest {

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

 public List<String> getPaths(int pathMatrix[][], int src, int dest) {
  /* Check for preconditions */
  Objects.nonNull(pathMatrix);

  length = pathMatrix.length;
  if (length != pathMatrix[0].length)
   throw new IllegalArgumentException(
     "Matrix should be rectangular (rows and columns must equal)");

  if (src < 0 || src > length - 1 || dest < 0 || dest > length - 1)
   throw new IllegalArgumentException(
     "Illegal Source (or) destination is ");

  if (src == dest) {
   System.out.println("Source and destination must be different");
   return paths;
  }

  /*Initialize variables */
  this.pathMatrix = pathMatrix;
  this.dest = dest;
  paths = new ArrayList<>();
  visited = new BitSet(length);

  getPaths(src, "" + src);
  return paths;
 }

 private void getPaths(int src, String path) {
  visited.set(src);
  if (src == dest)
   paths.add(path);

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

 }
}


Following is the junit test case fro above program.
import static org.junit.Assert.assertEquals;

import java.util.List;

import org.junit.Test;

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

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

  assertEquals(possiblePaths.get(0), "0,1,3");
  assertEquals(possiblePaths.get(1), "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 } };

  PathFromSrcToDest paths = new PathFromSrcToDest();

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

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


No comments:

Post a Comment