Print all paths between any 2 nodes in a directed Graph

0 / 83
finding all routes in a graph between 2 nodes

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

Undirected Graph

Fig B:- Directed Graph

Directed Graph

Fig C:- Directed Weighted Graph

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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;
}

 

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.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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 = [];
    }
}

 

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

 

1
2
3
4
5
6
7
8
9
function printAllEdges() {
    document.getElementById("output").innerHTML = "Output appears here : <br /><br />";
    document.getElementById("output").innerHTML += ("<br />Printing All edges in the graph as below : <br /><br />");

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

}

 

Putting it all together

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
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 : <br /><br />";
    document.getElementById("output").innerHTML += ("<br />Printing All edges in the graph as below : <br /><br />");

    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 : <br /><br />";
    var source = parseInt(document.getElementById("source").value);
    var destination = parseInt(document.getElementById("destination").value);
    document.getElementById("output").innerHTML += ("<br />Printing All routes from Node " + source + " to Node " + destination + "<br /> as below : <br /><br />");

    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 : <br /><br />";
    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;
}

 

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

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.
loading...

Related Posts