Skip to content

Commit 1b257d8

Browse files
author
Raghav Dua
committed
Merge pull request algorithm-visualizer#119 from fclvbfm934/gh-pages
Made changes to the efficient bridge-finding algorithm
2 parents 5ab536e + 0178af4 commit 1b257d8

File tree

3 files changed

+47
-40
lines changed

3 files changed

+47
-40
lines changed

‎algorithm/graph_search/bridges/desc.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
{
2-
"Bridges": "An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. A naive solution to finding bridges in a graph is to:<br />1.Delete an edge E<br />2.Perform DFS Exploration to check if the Graph is still connected<br />3.Restore Edge E. E is a bridge only if DFS exploration determines that the graph is disconnected without E. An efficient solution also exists, which uses the idea that edge U-V (U is parent) is a bridge if no subtree rooted at V has a back edge to U or one of its ancestors.",
2+
"Bridges": "An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. A naive solution to finding bridges in a graph is to:<br /> 1.Delete an edge E<br /> 2.Perform DFS Exploration to check if the Graph is still connected<br /> 3.Restore Edge E. E is a bridge only if DFS exploration determines that the graph is disconnected without E. <br /> <br /> A more efficient solution, which can find bridges in linear time, is to perform a DFS (depth-first-search) on the graph. At each step: <br /> 1. Number the vertex with a counter. The first vertex visited should be labelled 0, the second vertex labelled 1, etc. <br /> 2. Each vertex should also keep track of the lowest numbered vertex that can be reached with the DFS. This can be done recursively by looking at the smallest \"low\" of its children <br /> 3. If the lowest vertex that can be reached with the DFS is greater than its own label, that means the edge with its parent is a bridge. This is because the vertex cannot reach its parent with the DFS, implying that the edge is not part of a cycle. ",
33
"Applications": [
44
"Finding vulnerabilities in Graphs and Electrical Circuits"
55
],

‎algorithm/graph_search/bridges/efficient/code.js‎

Lines changed: 42 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -4,61 +4,70 @@
44

55
var timer = 0, bridges = [], adj = []; //adj keeps track of the neighbors of each node
66

7-
var util = function (u, visited, disc, low, parent) {
7+
var util = function (u, disc, low, parent) {
8+
//u is the node that is currently being processed in the DFS (depth-first search)
9+
//disc is the numbering of the vertices in the DFS, starting at 0
10+
//low[v] is the lowest numbered vertex that can be reached from vertex v along the DFS
11+
//parent is the node that u came from
812
logger._print ('');
913
logger._print ('Visiting node ' + u);
1014
graphTracer._visit (u)._wait ();
1115
graphTracer._leave (u)._wait ();
1216

13-
visited [u] = true;
14-
disc [u] = low [u] = ++timer;
17+
//visited [u] = true;
18+
disc [u] = low [u] = timer++;
1519

1620
logger._print ('Nodes adjacent to ' + u + ' are: [ ' + adj [u] + ' ]');
17-
adj [u].forEach (function (v) {
21+
/*adj [u].forEach (function (v) {
1822
graphTracer._visit (v, u)._wait ();
1923
graphTracer._leave (v, u)._wait ();
20-
});
24+
});*/
25+
var trace = function(v) {
26+
graphTracer._visit (v, u)._wait ();
27+
graphTracer._leave (v, u)._wait ();
28+
}
2129

2230
adj [u].forEach (function (v) {
23-
if (visited [v]) {
24-
logger._print (u + '\'s neighbor ' + v + ' has already been visited. Not visiting it.');
31+
if (disc [v] > -1 && v == parent) {
32+
trace(v);
33+
logger._print (u + '\'s neighbor ' + v + ' is u\'s parent. Not visiting it.');
34+
35+
}
36+
else if (disc[v] > -1 && v != parent) {
37+
trace(v);
38+
logger._print(u + '\'s neighbor ' + v + ' is not u\'s parent. Comparing low[u] with disc[v]')
39+
if(low[u] > disc[v]) {
40+
logger._print('low[' + u + '] is greater than disc[' + v + ']. Setting low[' + u + '] to disc[' + v + ']')
41+
low[u] = disc[v]
42+
}
2543
}
2644

27-
if (!visited [v]) {
45+
if (disc[v] == -1) {
46+
trace(v);
2847
logger._print (u + '\'s neighbor ' + v + ' has not been visited yet');
29-
logger._print ('Setting parent of ' + v + ' to ' + u + ' (parent [v] = u)');
30-
31-
parent [v] = u;
3248

33-
logger._print ('recursively calling util (' + v + ', [' + visited + '], [' + disc + '], [' + low + '], [' + parent + '])');
34-
util (v, visited, disc, low, parent);
49+
logger._print ('recursively calling util (' + v + ', [' + disc + '], [' + low + '],' + u + ')');
50+
util (v, disc, low, u);
3551

3652
logger._print ('--------------------------------------------------------------------');
37-
logger._print ('Returned from util (' + v + ', [' + visited + '], [' + disc + '], [' + low + '], [' + parent + '])');
38-
logger._print ('notice that the values of visited, disc, low and parent might have changed');
3953

4054
logger._print ('Setting low [' + u + '] to ' + Math.min (low [u], low [v]));
4155
low [u] = Math.min (low [u], low [v]);
4256

43-
if (low [v] > disc [u]) {
44-
logger._print ('low [v] > disc [u], v=' + v + ', u=' + u + ', (' + low [v] + ' > ' + low [u] + ')');
45-
logger._print (u + ' -> ' + v + ' is a bridge. Adding u->v to the set of bridges found');
57+
if (low [v] == disc [v]) {
58+
logger._print ('low [' + v + '] == disc [' + v + '], low[' + v + ']=' + low[v] + ', disc[' + v + ']=' + disc[v]);
59+
logger._print (u + ' -> ' + v + ' is a bridge. Adding ' + u + '->' + v + 'to the set of bridges found');
4660
bridges.push ([u, v]);
4761
}
4862
}
49-
else if (v !== parent [u]) {
50-
logger._print (v + ' does not equal parent [' + u + '] (' + parent [u] + ')');
51-
logger._print ('Setting low [' + u + '] to ' + Math.min (low [u], disc [v]));
52-
low [u] = Math.min (low [u], disc [v]);
53-
}
63+
5464
});
5565
};
5666

5767
(function findBridges (graph) {
58-
var visited = filledArray (graph.length, 0);
59-
var parent = filledArray (graph.length, -1);
60-
var disc = filledArray (graph.length, 0);
61-
var low = filledArray (graph.length, 0);
68+
69+
var disc = filledArray (graph.length, -1);
70+
var low = filledArray (graph.length, -1);
6271

6372
function filledArray (length, value) {
6473
return Array.apply (null, Array (length)).map (Number.prototype.valueOf, value);
@@ -75,20 +84,18 @@ var util = function (u, visited, disc, low, parent) {
7584
});
7685
}) ();
7786

78-
for (var i = 0; i < visited.length; i++) { visited [i] = false; }
79-
80-
logger._print ('Initializing <b>visited</b>: ' + visited + ', <b>parent</b>: ' + parent + ', <b>disc</b>: ' + disc + ' <b>low</b>: ' + low);
87+
logger._print ('Initializing: <b>disc</b>: ' + disc + ' <b>low</b>: ' + low);
8188
logger._print ('');
8289
logger._print ('Beginning efficient Bridge Finding');
83-
logger._print ('NOTE: call to util () follows pattern: util (nodeToVisit, visited, disc, low, parent). See code for clarity');
90+
logger._print ('NOTE: call to util () follows pattern: util (nodeToVisit, disc, low, parent). See code for clarity');
8491
logger._print ('');
8592

8693
logger._print ('Starting the main for loop (for each node)');
8794
for (var v = 0; v < graph.length; v++) {
88-
if (!visited [v]) {
89-
logger._print (v + ' has not been visited yet. Calling util (' + v + ', [' + visited + '], [' + disc + '], [' + low + '], [' + parent + ']) from the for loop');
90-
util (v, visited, disc, low, parent);
91-
logger._print ('Returned in for loop after util (' + v + ', [' + visited + '], [' + disc + '], [' + low + '], [' + parent + '])');
95+
if (disc[v] == -1) {
96+
logger._print (v + ' has not been visited yet. Calling util (' + v + ', [' + disc + '], [' + low + '],' + v + ') from the for loop');
97+
util (v, disc, low, v);
98+
logger._print ('Returned in for loop after util (' + v + ', [' + disc + '], [' + low + '], [' + v + '])');
9299
}
93100
}
94101
}) (G);

‎algorithm/graph_search/bridges/efficient/data.js‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
11
var graphTracer = new UndirectedGraphTracer ();
22
var logger = new LogTracer ();
33
var G = [
4-
[0,1,0,0,0,0],
5-
[1,0,0,1,1,0],
4+
[0,1,0,0,1,0],
5+
[1,0,0,0,1,0],
66
[0,0,0,1,0,0],
7-
[0,1,1,0,1,1],
8-
[0,1,0,1,0,0],
7+
[0,0,1,0,1,1],
8+
[1,1,0,1,0,0],
99
[0,0,0,1,0,0]
1010
];
1111

0 commit comments

Comments
 (0)