80 lines
2.4 KiB
Text
80 lines
2.4 KiB
Text
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) -> Void
|
||
‘
|
||
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)
|