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