Tarjan: Difference between revisions
Content added Content deleted
m (added whitespace before the TOC.) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 14: | Line 14: | ||
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]]. |
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]]. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python: As class}} |
|||
<lang 11l>T Graph |
|||
String name |
|||
[Char = [Char]] graph |
|||
Int _order |
|||
[Char = Int] disc |
|||
[Char = Int] low |
|||
[Char] stack |
|||
[[Char]] scc |
|||
F (name, connections) |
|||
.name = name |
|||
DefaultDict[Char, [Char]] g |
|||
L(n) connections |
|||
V (n1, n2) = (n[0], n[1]) |
|||
I n1 != n2 |
|||
g[n1].append(n2) |
|||
E |
|||
g[n1] |
|||
g[n2] |
|||
.graph = Dict(move(g)) |
|||
.tarjan_algo() |
|||
F _visitor(this) -> N |
|||
‘ |
|||
Recursive function that finds SCC's |
|||
using DFS traversal of vertices. |
|||
Arguments: |
|||
this --> Vertex to be visited in this call. |
|||
disc{} --> Discovery order of visited vertices. |
|||
low{} --> Connected vertex of earliest discovery order |
|||
stack --> Ancestor node stack during DFS. |
|||
’ |
|||
.disc[this] = .low[this] = ._order |
|||
._order++ |
|||
.stack.append(this) |
|||
L(neighbr) .graph[this] |
|||
I neighbr !C .disc |
|||
._visitor(neighbr) |
|||
.low[this] = min(.low[this], .low[neighbr]) |
|||
E I neighbr C .stack |
|||
.low[this] = min(.low[this], .disc[neighbr]) |
|||
I .low[this] == .disc[this] |
|||
[Char] new |
|||
L |
|||
V top = .stack.pop() |
|||
new.append(top) |
|||
I top == this |
|||
L.break |
|||
.scc.append(new) |
|||
F tarjan_algo() |
|||
‘ |
|||
Recursive function that finds strongly connected components |
|||
using the Tarjan Algorithm and function _visitor() to visit nodes. |
|||
’ |
|||
._order = 0 |
|||
L(vertex) sorted(.graph.keys()) |
|||
I vertex !C .disc |
|||
._visitor(vertex) |
|||
L(n, m) [(‘Tx1’, ‘10 02 21 03 34’.split(‘ ’)), |
|||
(‘Tx2’, ‘01 12 23’.split(‘ ’)), |
|||
(‘Tx3’, ‘01 12 20 13 14 16 35 45’.split(‘ ’)), |
|||
(‘Tx4’, ‘01 03 12 14 20 26 32 45 46 56 57 58 59 64 79 89 98 AA’.split(‘ ’)), |
|||
(‘Tx5’, ‘01 12 23 24 30 42’.split(‘ ’)) |
|||
] |
|||
print("\n\nGraph('#.', #.):\n".format(n, m)) |
|||
V g = Graph(n, m) |
|||
print(‘ : ’sorted(g.disc.keys()).map(v -> String(v)).join(‘ ’)) |
|||
print(‘ DISC of ’(g.name‘:’)‘ ’sorted(g.disc.items()).map((_, v) -> v)) |
|||
print(‘ LOW of ’(g.name‘:’)‘ ’sorted(g.low.items()).map((_, v) -> v)) |
|||
V scc = (I !g.scc.empty {String(g.scc).replace(‘'’, ‘’).replace(‘,’, ‘’)[1 .< (len)-1]} E ‘’) |
|||
print("\n SCC's of "(g.name‘:’)‘ ’scc)</lang> |
|||
{{out}} |
|||
<pre> |
|||
Graph('Tx1', [10, 02, 21, 03, 34]): |
|||
: 0 1 2 3 4 |
|||
DISC of Tx1: [0, 2, 1, 3, 4] |
|||
LOW of Tx1: [0, 0, 0, 3, 4] |
|||
SCC's of Tx1: [4] [3] [1 2 0] |
|||
Graph('Tx2', [01, 12, 23]): |
|||
: 0 1 2 3 |
|||
DISC of Tx2: [0, 1, 2, 3] |
|||
LOW of Tx2: [0, 1, 2, 3] |
|||
SCC's of Tx2: [3] [2] [1] [0] |
|||
Graph('Tx3', [01, 12, 20, 13, 14, 16, 35, 45]): |
|||
: 0 1 2 3 4 5 6 |
|||
DISC of Tx3: [0, 1, 2, 3, 5, 4, 6] |
|||
LOW of Tx3: [0, 0, 0, 3, 5, 4, 6] |
|||
SCC's of Tx3: [5] [3] [4] [6] [2 1 0] |
|||
Graph('Tx4', [01, 03, 12, 14, 20, 26, 32, 45, 46, 56, 57, 58, 59, 64, 79, 89, 98, AA]): |
|||
: 0 1 2 3 4 5 6 7 8 9 A |
|||
DISC of Tx4: [0, 1, 2, 9, 4, 5, 3, 6, 8, 7, 10] |
|||
LOW of Tx4: [0, 0, 0, 2, 3, 3, 3, 6, 7, 7, 10] |
|||
SCC's of Tx4: [8 9] [7] [5 4 6] [3 2 1 0] [A] |
|||
Graph('Tx5', [01, 12, 23, 24, 30, 42]): |
|||
: 0 1 2 3 4 |
|||
DISC of Tx5: [0, 1, 2, 3, 4] |
|||
LOW of Tx5: [0, 0, 0, 0, 2] |
|||
SCC's of Tx5: [4 3 2 1 0] |
|||
</pre> |
|||
=={{header|C|C}}== |
=={{header|C|C}}== |