CC-9 : Check how many paths exists between 2 vertices in a directed graph.

Description:

In a directed graph, the edges are uni-directional from one vertex v1 to other vertex v2 (and not from v2 to v1 at the same time as it is in case of bi-directional/ undirectional graphs). Given an input uni-directional graph and two input vertices, check how many paths are present between the two vertices.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphDirectedCheckPath gph= new GraphDirectedCheckPath(5); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(0, 3); gph.addEdge(0, 4); gph.addEdge(1, 2); gph.addEdge(2, 3); gph.addEdge(3, 4); gph.displayGraph(); gph.checkPath(0,4); System.out.println("Count of path between 0 and 4?: "+gph.getPathCount() );	vertex 0->1->2->3->4 vertex 1->2 vertex 2->3 vertex 3->4 vertex 4 Count of path between 0 and 4?: 4
gph=new GraphDirectedCheckPath(5); gph.setPathCount(0); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(1, 2); gph.addEdge(1, 3); gph.addEdge(3, 4); gph.displayGraph(); System.out.println("Count of path between 0 and 4?: "+gph.getPathCount() );	vertex 0->1->2 vertex 1->2->3 vertex 2 vertex 3->4 vertex 4 Count of path between 0 and 4?: 0

Pseudocode:

Initialize a variable named pathCount at class level to count the number of paths between two input nodes.

checkPath() method:

The method receives 2 input parameters named currVertice and destVertice.

If currVertice==destVertice, increment pathCount by 1.

Set visited[currVertice] to 1 as the current nodehas been visited.

From the adjacencyListof graph extract the connected nodes of currVertice.

Iterate through connected vertices of currVertice using a for loop with iIdx as loop variable with values from 0 to count of connectedVertices:

Set variable adjacentNode to point to current connected vertice.

If visited[adjacentNode] is not 1, then:

Call checkPath(adjacentNode, destVertice) recursively.

Set visited[currVertice] to 0.

The variable pathCount now contains the number of paths between currVertice and destVertice.

Code:

public class GraphDirectedCheckPath {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 private String dfsTraversal=new String();
 private int pathCount=0;
 
 public GraphDirectedCheckPath(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
  
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 //adjacencyLists.get(dest).add(source);
 }
 
 public void checkPath(int currVertice, int destVertice) {
	if (currVertice==destVertice) {
		pathCount++;
		return; 
	}
	 visited[currVertice]=1;
	 ArrayList<Integer> adjacentNodes=adjacencyLists.get(currVertice);
	 for (int idx=0; idx < adjacentNodes.size(); idx++) {
		 int adjNode=adjacentNodes.get(idx);
		 if (visited[adjNode]==0) {
			 checkPath(adjNode, destVertice);			 
		 } 
	 }
	visited[currVertice]=0;
	return;	
 }
 }

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;

public class GraphDirectedCheckPath {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 private String dfsTraversal=new String();
 private int pathCount=0;
 
 public GraphDirectedCheckPath(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
  
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 //adjacencyLists.get(dest).add(source);
 }
 
 public void checkPath(int currVertice, int destVertice) {
	if (currVertice==destVertice) {
		pathCount++;
		return; 
	}
	 visited[currVertice]=1;
	 ArrayList<Integer> adjacentNodes=adjacencyLists.get(currVertice);
	 for (int idx=0; idx < adjacentNodes.size(); idx++) {
		 int adjNode=adjacentNodes.get(idx);
		 if (visited[adjNode]==0) {
			 checkPath(adjNode, destVertice);			 
		 } 
	 }
	visited[currVertice]=0;
	return;	
 }
 
 public int getPathCount() {
		return pathCount;
} 
 
 public void setPathCount(int pathCount) {
		this.pathCount=pathCount;
} 
 
 
 public void displayGraph() {
	 for (int iIdx=0;iIdx< adjacencyLists.size();iIdx++) {
		 System.out.println();
		 System.out.print("vertex "+iIdx);
		 for (int jIdx=0;jIdx< adjacencyLists.get(iIdx).size();jIdx++) {
			 System.out.print("->"+adjacencyLists.get(iIdx).get(jIdx));
		 }
	 }
 }
public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	boolean retVal;
	try {
	GraphDirectedCheckPath gph=new GraphDirectedCheckPath(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(0, 4);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(3, 4);
	gph.displayGraph();
	gph.checkPath(0,4);
	System.out.println();
	System.out.println("Count of path between 0 and 4?: "+gph.getPathCount() );
	
	gph=new GraphDirectedCheckPath(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 4);
	gph.addEdge(1, 3);
	gph.addEdge(3, 4);
	gph.displayGraph();
	gph.checkPath(0,4);
	System.out.println();
	System.out.println("Count of path between 0 and 4?: "+gph.getPathCount() );
	
	gph=new GraphDirectedCheckPath(5);
	gph.setPathCount(0);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(1, 2);
	gph.addEdge(2, 4);
	gph.addEdge(4, 3);
	gph.displayGraph();
	gph.checkPath(1,3);
	System.out.println();
	System.out.println("Count of path between 0 and 4?: "+gph.getPathCount() );
	
	gph=new GraphDirectedCheckPath(5);
	gph.setPathCount(0);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(1, 2);
	gph.addEdge(1, 3);
	gph.addEdge(3, 4);
	gph.displayGraph();
	System.out.println();
	System.out.println("Count of path between 0 and 4?: "+gph.getPathCount() );	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}