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/
Leave Print all paths between any 2 nodes in a directed Graph to:
Best Posts From golibrary
We have not curated any of golibrary's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.
More Posts From golibrary
- Algorithm to find prime factors of very big numbers
- How to create a VM In Microsoft Azure Cloud
- Algorithm to solve linear equation in one variable
- Remove duplicates from sorted array in place
- Finding maximum number of fruits that can be kept in one basket
- Length of smallest subarray with a sum greater than or equal to S
- Finding max sum of subarray with a given length in an array
- Puppet Basic Concepts
- History of Unix and Linux
- Optimizing hierarchical SQL queries
- Application performance analysis using Windows toolkit
- Quantum money and bitcoin
- Finding diameter of a binary tree
- Find cells with odd values in a matrix
- Check if two given strings are ispmorphic
- System Design: Design scalable typeahead component
- Hack remote databases using SQL injection
- What is Quantum Computing
- Print all paths between any 2 nodes in a directed Graph
- Find an element in an Array of length N which is rotated at point K