Print all paths between any 2 nodes in a directed Graph
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:-
Print all paths between any 2 given nodes in the graph
Print all paths in the graph between all 2 arbitrary nodes
Print all edges in the graph
Below is the demo of this application in javascript using visjs
[iframe src="http://www.golibrary.co/jhtree/graph.html" width=750 height=1000 allowfullscreen]
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
[cc lang = "javascript" lines="-1" tab_size="4" width="100%"]
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();
}
[/cc]
Algorithm for printing all routes between 2 given nodes
Store all nodes with their adjacent nodes in an array nodeMap
Initialize the visited array which will keep track of the visited nodes
Mark the source node as visited and push it into an array path which will store path from source to destination
If target node is found, print the path and return
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.
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.
[cc lang = "javascript" lines="-1" tab_size="4" width="100%"]
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, '->')) + "<br />";
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;
}
[/cc]
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.
[cc lang = "javascript" lines="-1" tab_size="4" width="100%"]
// 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 += ("<br /><br />Printing All routes from Node " + string[0] + " to Node " + string[1] + " : <br />");
printPaths(nodeMap, graph, parseInt(string[0]), parseInt(string[1]), false);
}
// clear the string
string = [];
}
}
[/cc]
Below piece of code prints all the edges in the graph:
[cc lang = "javascript" lines="-1" tab_size="4" width="100%"]
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 + "<br /><br />";
}
}
[/cc]
Putting it all together
[cc lang = "javascript" lines="-1" tab_size="4" width="100%"]
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 + "<br /><br />";
}
}
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 += ("<br />Route doesn't exist<br />");
}
}
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 += ("<br /><br />Printing All routes from Node " + string[0] + " to Node " + string[1] + " : <br />");
printPaths(nodeMap, graph, parseInt(string[0]), parseInt(string[1]), 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, '->')) + "<br />";
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;
}
[/cc]
We have an IDE now and code can be tried at http://code.golibrary.co
Posted from my blog with SteemPress : http://www.golibrary.co/print-all-paths-between-any-2-nodes-in-a-directed-graph/