Tarjan: Difference between revisions
Added 11l
m (added whitespace before the TOC.) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 14:
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]].
<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}}==
| |||