Print all paths between any 2 nodes in a directed Graph
0
/
1293
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(); } |
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; } |
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 = []; } } |
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 />"; } } |
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; } |