Print all paths between any 2 nodes in a directed Graph

0 / 487 Graph

A Graph is a specific data structure consisting of a finite number of objects or set of objects. This set of objects are connected by edges or lines between them. The objects are called as graph nodes or vertices and the edges symbolize paths between different graph nodes. A graph can be a directed or undirected graph. A directed graph is the one in which the edges E (x,y) have orientation or direction i.e they consist of ordered pair of vertices and thus E(x,y) ≠ E(y,x) . In undirected graphs, the vertices have no orientation or direction and so the edges E(x,y) and E(y,x) are identical. Some graphs may also have specific finite values assigned to the edges. These values or weights denote the costs/capacities/lengths of a particular edge of the graph. Such a graph is called as a weighted graph.

Consider the below diagrams which will clarify how, the different graphs look like. (source Wikipedia)

Fig a):- Undirected Graph Fig B:- Directed Graph Fig C:- Directed Weighted Graph Now we know what a graph is , we will focus on constructing a graph in javascript using a library called visjs and also write algorithms to do the following:-

1) Print all paths between any 2 given nodes in the graph

2) Print all paths in the graph between all 2 arbitrary nodes

3) Print all edges in the graph

Below is the demo of this application in javascript using visjs

Below is the code behind this demo explained into pieces:-

Code for initializing and constructing the above graph using visjs.org. This code also calculates different edges in the graph

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 var nodeMap = []; var graph = [     [0, 16, 13, 0, 0, 0],     [0, 0, 10, 12, 0, 0],     [0, 4, 0, 0, 14, 0],     [0, 0, 9, 0, 0, 20],     [0, 0, 0, 7, 0, 4],     [0, 0, 0, 0, 0, 0] ]; var graph_string = '',     edges = []; init(); function init() {         var nodes = [];     for (var i = 0; i < graph.length; i++) {         var obj = {             id: i,             label: i.toString(),             group: i         }         nodes.push(obj);         nodeMap[i] = [];         for (var j = 0; j < graph[i].length; j++) {             if (graph[i][j] > 0) {                 if (graph[j][i] > 0) {                     obj = {                         from: i,                         to: j,                         label: graph[i][j].toString(),                         arrows: 'to',                         smooth: {                             type: "curvedCCW",                             roundness: 0.1                         }                     };                     edges.push(obj);                 } else {                     obj = {                         from: i,                         to: j,                         label: graph[i][j].toString(),                         arrows: 'to'                     };                     edges.push(obj);                 }                 nodeMap[i].push(j);             }         }         graph_string += i;     }     // create a network     var container = document.getElementById('mynetwork');     var data = {         nodes: nodes,         edges: edges     };     var options = {         // TODO - if you need to add any options they can be added here ref:- http://visjs.org     };     network = new vis.Network(container, data, options);     document.getElementById("source").focus(); }

Algorithm for printing all routes between 2 given nodes

1)  Store all nodes with their adjacent nodes in an array nodeMap

2) Initialize the visited array which will keep track of the visited nodes

3) Mark the source node as visited and push it into an array path which will store path from source to destination

4) If target node is found, print the path and return

5) if step 4 is FALSE, traverse through the nodeMap and check nodes adjacent to the ith node being processed from the nodeMap array, if it’s not visited, make a recursive call to the function with the new ith node from the nodeMap array as source node (s), leaving the target node intact.

6) if all nodes adjacent to a given node are processed and yet target node isn’t found, remove the last visited node from the path array and backtrack. This step means that the target node isn’t reachable via that particular node and we need to process additional nodes to get alternative paths to the destination.Repeat steps until ether entire nodeMap is processed or we reach the target node.

 123456789101112131415161718192021222324252627282930313233343536 function printPaths(nodeMap, graph, s, t, routeFound) {     var path = [];     var visited = [];     for (var i = 0; i < graph.length; i++) {         visited[i] = false;     }     return printAllPaths(nodeMap, s, t, visited, path, routeFound); } function printAllPaths(nodeMap, s, t, visited, path, routeFound) {     visited[s] = true;     path.push(s);     if (s === t) {         // print path from s to t         var value = document.getElementById("output").innerHTML;         document.getElementById("output").innerHTML += (path.join(",").replace(/,/g, '->')) + "
";         routeFound = true;     } else if (nodeMap[s]) {         // iterate through the edges a.k.a nodeMap         for (var i = 0; i < nodeMap[s].length; i++) {             if (visited[nodeMap[s][i]] === false) {                 routeFound = printAllPaths(nodeMap, nodeMap[s][i], t, visited, path, routeFound);             }         }     }     // remove the last visited node and backtrack     path.pop();     visited[s] = false;     return routeFound; }

Algorithm to print all paths between any 2 nodes in the graph

This is fairly straightforward. We just need to find all subsets containing 2 nodes from an N node graph which means there will be Np2 total combinations for which we will call printAllPaths() each time for each of those combinations. To calculate the Np2 combinations, we simply consider the N node graph as an N bit binary number and count all combinations from 0 to N which have 2 bits set in them (i.e two 1’s) . For Npr, we will need to count r bits set for each number from 0 to N and use the corresponding indices of the set bits to print a particular combination.

 123456789101112131415161718192021222324 // function to calculate nPr permutations function printSubsets(set, r, graph, nodeMap) {     var n = set.length;     var string = [];     var sum = 0;     // Print all 2^n subsets one by one     for (var i = 0; i < (1 << n); i++) {         // Print current subset         for (var j = 0; j < n; j++)             // count the number of bits set to 1 here             if ((i & (1 << j)) > 0) {                 string.push(set[j]);             }         if (string.length === r) {             // convert array to string             document.getElementById("output").innerHTML += ("

Printing All routes from Node " + string + " to Node " + string + " :
");             printPaths(nodeMap, graph, parseInt(string), parseInt(string), false);         }         // clear the string         string = [];     } }

Below piece of code prints all the edges in the graph:

 123456789 function printAllEdges() {     document.getElementById("output").innerHTML = "Output appears here :

";     document.getElementById("output").innerHTML += ("
Printing All edges in the graph as below :

");     for (var x = 0; x < edges.length; x++) {         document.getElementById("output").innerHTML += edges[x].from + "->" + edges[x].to + "

";     } }

Putting it all together

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167 var nodeMap = []; var graph = [     [0, 16, 13, 0, 0, 0],     [0, 0, 10, 12, 0, 0],     [0, 4, 0, 0, 14, 0],     [0, 0, 9, 0, 0, 20],     [0, 0, 0, 7, 0, 4],     [0, 0, 0, 0, 0, 0] ]; var graph_string = '',     edges = []; init(); function init() {     var nodes = [];     for (var i = 0; i < graph.length; i++) {         var obj = {             id: i,             label: i.toString(),             group: i         }         nodes.push(obj);         nodeMap[i] = [];         for (var j = 0; j < graph[i].length; j++) {             if (graph[i][j] > 0) {                 if (graph[j][i] > 0) {                     obj = {                         from: i,                         to: j,                         label: graph[i][j].toString(),                         arrows: 'to',                         smooth: {                             type: "curvedCCW",                             roundness: 0.1                         }                     };                     edges.push(obj);                 } else {                     obj = {                         from: i,                         to: j,                         label: graph[i][j].toString(),                         arrows: 'to'                     };                     edges.push(obj);                 }                 nodeMap[i].push(j);             }         }         graph_string += i;     }     // create a network     var container = document.getElementById('mynetwork');     var data = {         nodes: nodes,         edges: edges     };     var options = {         // TODO fill this if needed - ref visjs.org     };     network = new vis.Network(container, data, options);     document.getElementById("source").focus(); } function printAllEdges() {     document.getElementById("output").innerHTML = "Output appears here :

";     document.getElementById("output").innerHTML += ("
Printing All edges in the graph as below :

");     for (var x = 0; x < edges.length; x++) {         document.getElementById("output").innerHTML += edges[x].from + "->" + edges[x].to + "

";     } } function findRoute() {     document.getElementById("output").innerHTML = "Output appears here :

";     var source = parseInt(document.getElementById("source").value);     var destination = parseInt(document.getElementById("destination").value);     document.getElementById("output").innerHTML += ("
Printing All routes from Node " + source + " to Node " + destination + "
as below :

");     var found = printPaths(nodeMap, graph, source, destination, false);     if (!found) {         document.getElementById("output").innerHTML += ("
Route doesn't exist
");     } } function printAllRoutes() {     document.getElementById("output").innerHTML = "Output appears here :

";     printSubsets(graph_string, 2, graph, nodeMap); } // function to calculate nPr permutations function printSubsets(set, r, graph, nodeMap) {     var n = set.length;     var string = [];     var sum = 0;     // Print all 2^n subsets one by one     for (var i = 0; i < (1 << n); i++) {         // Print current subset         for (var j = 0; j < n; j++)             // count the number of bits set to 1 here             if ((i & (1 << j)) > 0) {                 string.push(set[j]);             }         if (string.length === r) {             // convert array to string             document.getElementById("output").innerHTML += ("

Printing All routes from Node " + string + " to Node " + string + " :
");             printPaths(nodeMap, graph, parseInt(string), parseInt(string), false);         }         // clear the string         string = [];     } } function printPaths(nodeMap, graph, s, t, routeFound) {     var path = [];     var visited = [];     for (var i = 0; i < graph.length; i++) {         visited[i] = false;     }     return printAllPaths(nodeMap, s, t, visited, path, routeFound); } function printAllPaths(nodeMap, s, t, visited, path, routeFound) {     visited[s] = true;     path.push(s);     if (s === t) {         // print path from s to t         var value = document.getElementById("output").innerHTML;         document.getElementById("output").innerHTML += (path.join(",").replace(/,/g, '->')) + "
";         routeFound = true;     } else if (nodeMap[s]) {         // iterate through the edges a.k.a nodeMap         for (var i = 0; i < nodeMap[s].length; i++) {             if (visited[nodeMap[s][i]] === false) {                 routeFound = printAllPaths(nodeMap, nodeMap[s][i], t, visited, path, routeFound);             }         }     }     // remove the last visited node and backtrack     path.pop();     visited[s] = false;     return routeFound; }

We have an IDE now and code can be tried at http://code.golibrary.co