Anonymous user
Tarjan: Difference between revisions
→{{header|Python}}: Add class based solution
(→{{header|Python}}: don't use a list as the default argument) |
(→{{header|Python}}: Add class based solution) |
||
Line 490:
=={{header|Python}}==
===Python: As function===
<lang python>from collections import defaultdict
Line 556 ⟶ 558:
['A', 'B', 'C']
</pre>
===Python: As class===
This takes inspiration from the [https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/ Geeks4Geeks explanation] and uses its five examples.
;Tx1:
<pre>
+---+ +---+ +---+ +---+
| 1 | --> | 0 | --> | 3 | --> | 4 |
+---+ +---+ +---+ +---+
^ |
| |
| v
| +---+
+------ | 2 |
+---+
</pre>
;Tx2:
<pre>
+---+ +---+ +---+ +---+
| 0 | --> | 1 | --> | 2 | --> | 3 |
+---+ +---+ +---+ +---+
</pre>
;Tx3:
<pre>
+----------------------------------+
v |
+---+ +---+ +---+ +---+ |
| 0 | --> | | --> | 3 | --> | 5 | |
+---+ | | +---+ +---+ |
| | ^ |
| 1 | | |
| | | |
+---+ | | +---+ | |
| 6 | <-- | | --> | 2 | ------+----+
+---+ +---+ +---+ |
| |
| |
v |
+---+ |
| 4 | ----------------+
+---+
</pre>
;Tx4:
<pre>
+-----------------------------+
| |
| +---+ |
| | A | | +-------------------+
| +---+ | | |
| | | |
| +---------+---------+---------+ | +---------+
| | v v v | v |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| 3 | <-- | 0 | --> | 1 | --> | 2 | --> | 6 | --> | 4 | --> | | --> | 7 | --> | 9 | --> | 8 |
+---+ +---+ +---+ +---+ +---+ +---+ | | +---+ +---+ +---+
^ | ^ | | | ^ ^
+-------------------+ +---------+ | 5 | ----------------+ |
| | |
| | |
| | --------------------------+
+---+
</pre>
;Tx5:
<pre>
+--------------+
| |
| |
+-------------------+---------+ |
v v | |
+---+ +---+ +---+ +---+ |
| 0 | --> | 1 | --> | 2 | --> | 3 | |
+---+ +---+ +---+ +---+ |
| |
| |
v |
+---+ |
| 4 | -----------+
+---+
</pre>
;Code:
<lang python>from collections import defaultdict
class Graph:
"Directed Graph Tarjan's strongly connected components algorithm"
def __init__(self, name, connections):
self.name = name
self.connections = connections
self.gv = self._to_gv()
g = defaultdict(list) # map node vertex to direct connections
for n1, n2 in connections:
if n1 != n2:
g[n1].append(n2)
else:
g[n1]
for _, n2 in connections:
g[n2] # For leaf nodes having no edges from themselves
self.graph = dict(g)
self.tarjan_algo()
def _visitor(self, this, low, disc, stack):
'''
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] = self._order
self._order += 1
stack.append(this)
for neighbr in self.graph[this]:
if neighbr not in disc:
# neighbour not visited so do DFS recurrence.
self._visitor(neighbr, low, disc, stack)
low[this] = min(low[this], low[neighbr]) # Prior connection?
elif neighbr in stack:
# Update low value of this only if neighbr in stack
low[this] = min(low[this], disc[neighbr])
if low[this] == disc[this]:
# Head node found of SCC
top, new = None, []
while top != this:
top = stack.pop()
new.append(top)
self.scc.append(new)
def tarjan_algo(self):
'''
Recursive function that finds strongly connected components
using the Tarjan Algorithm and function _visitor() to visit nodes.
'''
self._order = 0 # Visitation order counter
disc, low = {}, {}
stack = []
self.scc = [] # SCC result accumulator
for vertex in sorted(self.graph):
if vertex not in disc:
self._visitor(vertex, low, disc, stack)
self._disc, self._low = disc, low
if __name__ == '__main__':
for n, m in [('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(f"\n\nGraph({repr(n)}, {m}):\n")
g = Graph(n, m)
print(" : ", ' '.join(str(v) for v in sorted(g._disc)))
print(" DISC of", g.name + ':', [v for _, v in sorted(g._disc.items())])
print(" LOW of", g.name + ':', [v for _, v in sorted(g._low.items())])
scc = repr(g.scc if g.scc else '').replace("'", '').replace(',', '')[1:-1]
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|Racket}}==
| |||