Commit f415cf5
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -41,7 +41,8 @@ | |||
| 41 | 41 | "dijkstra": "Dijkstra", | |
| 42 | 42 | "floyd_warshall": "Floyd-Warshall", | |
| 43 | 43 | "page_rank": "PageRank Algorithm", | |
| 44 | - "topological_sort": "Topological-Sort" | ||
| 44 | + "topological_sort": "Topological-Sort", | ||
| 45 | + "tarjan": "Tarjan" | ||
| 45 | 46 | }, | |
| 46 | 47 | "name": "Graph Search" | |
| 47 | 48 | }, | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,90 @@ | |||
| 1 | + function SCCVertex(u, disc, low, st, stackMember, carry) | ||
| 2 | + { | ||
| 3 | + graphTracer._visit(u)._wait(); | ||
| 4 | + | ||
| 5 | + disc[u] = ++carry.time; | ||
| 6 | + discTracer._notify(u, carry.time)._wait(); | ||
| 7 | + | ||
| 8 | + low[u] = carry.time; | ||
| 9 | + lowTracer._notify(u, carry.time)._wait(); | ||
| 10 | + | ||
| 11 | + st.push(u); | ||
| 12 | + stTracer._setData(st)._wait(); | ||
| 13 | + | ||
| 14 | + stackMember[u] = true; | ||
| 15 | + stackMemberTracer._notify(u, true)._wait(); | ||
| 16 | + | ||
| 17 | + // Go through all vertices adjacent to this | ||
| 18 | + for (var v = 0; v < G[u].length; v++) { | ||
| 19 | + if (G[u][v]) { | ||
| 20 | + | ||
| 21 | + // If v is not visited yet, then recur for it | ||
| 22 | + if (disc[v] == -1) { | ||
| 23 | + SCCVertex(v, disc, low, st, stackMember, carry); | ||
| 24 | + | ||
| 25 | + // Check if the subtree rooted with 'v' has a | ||
| 26 | + // connection to one of the ancestors of 'u' | ||
| 27 | + low[u] = Math.min(low[u], low[v]); | ||
| 28 | + lowTracer._notify(u, low[u]); | ||
| 29 | + } | ||
| 30 | + | ||
| 31 | + // Update low value of 'u' only of 'v' is still in stack | ||
| 32 | + // (i.e. it's a back edge, not cross edge). | ||
| 33 | + else if (stackMember[v] == true) { | ||
| 34 | + low[u] = Math.min(low[u], disc[v]); | ||
| 35 | + lowTracer._notify(u, low[u])._wait(); | ||
| 36 | + } | ||
| 37 | + | ||
| 38 | + } | ||
| 39 | + } | ||
| 40 | + | ||
| 41 | + // head node found, pop the stack and print an SCC | ||
| 42 | + var w = 0; // To store stack extracted vertices | ||
| 43 | + if (low[u] == disc[u]) { | ||
| 44 | + | ||
| 45 | + while (st[st.length-1] != u) { | ||
| 46 | + w = st.pop(); | ||
| 47 | + stTracer._setData(st)._wait(); | ||
| 48 | + | ||
| 49 | + logger._print(w)._wait(); | ||
| 50 | + | ||
| 51 | + stackMember[w] = false; | ||
| 52 | + stackMemberTracer._notify(w, false)._wait(); | ||
| 53 | + } | ||
| 54 | + | ||
| 55 | + w = st.pop(); | ||
| 56 | + stTracer._setData(st)._wait(); | ||
| 57 | + | ||
| 58 | + logger._print(w)._wait(); | ||
| 59 | + logger._print('------'); | ||
| 60 | + | ||
| 61 | + stackMember[w] = false; | ||
| 62 | + stackMemberTracer._notify(w, false)._wait(); | ||
| 63 | + } | ||
| 64 | + } | ||
| 65 | + | ||
| 66 | + function SCC() | ||
| 67 | + { | ||
| 68 | + var disc = new Array(G.length); | ||
| 69 | + var low = new Array(G.length); | ||
| 70 | + var stackMember = new Array(G.length); | ||
| 71 | + var st = []; | ||
| 72 | + var carry = { time: 0 }; | ||
| 73 | + | ||
| 74 | + for (var i = 0; i < G.length; i++) { | ||
| 75 | + disc[i] = -1; | ||
| 76 | + low[i] = -1; | ||
| 77 | + stackMember[i] = false; | ||
| 78 | + } | ||
| 79 | + | ||
| 80 | + discTracer._setData(disc); | ||
| 81 | + lowTracer._setData(low); | ||
| 82 | + stackMemberTracer._setData(stackMember); | ||
| 83 | + stTracer._setData(st); | ||
| 84 | + | ||
| 85 | + for (var i = 0; i < G.length; i++) { | ||
| 86 | + if (disc[i] == -1) { | ||
| 87 | + SCCVertex(i, disc, low, st, stackMember, carry); | ||
| 88 | + } | ||
| 89 | + } | ||
| 90 | + } | ||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,20 @@ | |||
| 1 | + var G = [ | ||
| 2 | + [0,0,1,1,0,0], | ||
| 3 | + [1,0,0,0,0,0], | ||
| 4 | + [0,1,0,0,0,0], | ||
| 5 | + [0,0,0,1,0,0], | ||
| 6 | + [0,0,0,0,0,1], | ||
| 7 | + [0,0,0,0,1,0] | ||
| 8 | + ]; | ||
| 9 | + | ||
| 10 | + var graphTracer = new DirectedGraphTracer(); | ||
| 11 | + graphTracer._setData(G); | ||
| 12 | + | ||
| 13 | + var discTracer = new Array1DTracer('Disc'); | ||
| 14 | + var lowTracer = new Array1DTracer('Low'); | ||
| 15 | + var stackMemberTracer = new Array1DTracer('stackMember'); | ||
| 16 | + var stTracer = new Array1DTracer('st'); | ||
| 17 | + | ||
| 18 | + var logger = new LogTracer(); | ||
| 19 | + | ||
| 20 | + SCC(); | ||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,12 @@ | |||
| 1 | + { | ||
| 2 | + "Tarjan": "Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph", | ||
| 3 | + "Complexity": { | ||
| 4 | + "time": "worst $O(|V|+|E|)$" | ||
| 5 | + }, | ||
| 6 | + "References": [ | ||
| 7 | + "<a href='https://www.wikiwand.com/en/Tarjan%27s_strongly_connected_components_algorithm'>Wikipedia</a>" | ||
| 8 | + ], | ||
| 9 | + "files": { | ||
| 10 | + "basic": "Find the strongly connected components of a graph" | ||
| 11 | + } | ||
| 12 | + } | ||
0 commit comments