Tarjan: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Python}}: don't use a list as the default argument)
(→‎{{header|Python}}: Add class based solution)
Line 490: Line 490:


=={{header|Python}}==
=={{header|Python}}==

===Python: As function===
<lang python>from collections import defaultdict
<lang python>from collections import defaultdict


Line 556: Line 558:
['A', 'B', 'C']
['A', 'B', 'C']
</pre>
</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}}==
=={{header|Racket}}==

Revision as of 12:57, 11 March 2020

Task
Tarjan
You are encouraged to solve this task according to the task description, using any language you may know.
This page uses content from Wikipedia. The original article was at Graph. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)


Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. Tarjan's Algorithm is named for its discoverer, Robert Tarjan.

References

C#

<lang csharp>using System; using System.Collections.Generic;

class Node { public int LowLink { get; set; } public int Index { get; set; } public int N { get; }

public Node(int n) { N = n; Index = -1; LowLink = 0; } }

class Graph { public HashSet<Node> V { get; } public Dictionary<Node, HashSet<Node>> Adj { get; }

/// <summary> /// Tarjan's strongly connected components algorithm /// </summary> public void Tarjan() { var index = 0; // number of nodes var S = new Stack<Node>();

Action<Node> StrongConnect = null; StrongConnect = (v) => { // Set the depth index for v to the smallest unused index v.Index = index; v.LowLink = index;

index++; S.Push(v);

// Consider successors of v foreach (var w in Adj[v]) if (w.Index < 0) { // Successor w has not yet been visited; recurse on it StrongConnect(w); v.LowLink = Math.Min(v.LowLink, w.LowLink); } else if (S.Contains(w)) // Successor w is in stack S and hence in the current SCC v.LowLink = Math.Min(v.LowLink, w.Index);

// If v is a root node, pop the stack and generate an SCC if (v.LowLink == v.Index) { Console.Write("SCC: ");

Node w; do { w = S.Pop(); Console.Write(w.N + " "); } while (w != v);

Console.WriteLine(); } };

foreach (var v in V) if (v.Index < 0) StrongConnect(v); } }</lang>

Go

<lang go>package main

import ( 

   "fmt"
   "math/big"

)

// (same data as zkl example) var g = [][]int{ 

   0: {1},
   2: {0},
   5: {2, 6},
   6: {5},
   1: {2},
   3: {1, 2, 4},
   4: {5, 3},
   7: {4, 7, 6},

}

func main() { 

   tarjan(g, func(c []int) { fmt.Println(c) })

}

// the function calls the emit argument for each component identified. // each component is a list of nodes. func tarjan(g [][]int, emit func([]int)) { 

   var indexed, stacked big.Int
   index := make([]int, len(g))
   lowlink := make([]int, len(g))
   x := 0
   var S []int
   var sc func(int) bool
   sc = func(n int) bool {
       index[n] = x
       indexed.SetBit(&indexed, n, 1)
       lowlink[n] = x
       x++
       S = append(S, n)
       stacked.SetBit(&stacked, n, 1)
       for _, nb := range g[n] {
           if indexed.Bit(nb) == 0 {
               if !sc(nb) {
                   return false
               }
               if lowlink[nb] < lowlink[n] {
                   lowlink[n] = lowlink[nb]
               }
           } else if stacked.Bit(nb) == 1 {
               if index[nb] < lowlink[n] {
                   lowlink[n] = index[nb]
               }
           }
       }
       if lowlink[n] == index[n] {
           var c []int
           for {
               last := len(S) - 1
               w := S[last]
               S = S[:last]
               stacked.SetBit(&stacked, w, 0)
               c = append(c, w)
               if w == n {
                   emit(c)
                   break
               }
           }
       }
       return true
   }
   for n := range g {
       if indexed.Bit(n) == 0 && !sc(n) {
           return
       }
   }

}</lang>

Output:
[2 1 0]
[6 5]
[4 3]
[7]


Julia

LightGraphs uses Tarjan's algorithm by default. The package can also use Kosaraju's algorithm with the function strongly_connected_components_kosaraju(). <lang julia>using LightGraphs

edge_list=[(1,2),(3,1),(6,3),(6,7),(7,6),(2,3),(4,2),(4,3),(4,5),(5,6),(5,4),(8,5),(8,8),(8,7)]

grph = SimpleDiGraph(Edge.(edge_list))

tarj = strongly_connected_components(grph)

inzerobase(arrarr) = map(x -> sort(x .- 1, rev=true), arrarr)

println("Results in the zero-base scheme: $(inzerobase(tarj))")

</lang>

Output:
Results in the zero-base scheme: Array{Int64,1}[[2, 1, 0], [6, 5], [4, 3], [7]]

Kotlin

<lang scala>// version 1.1.3

import java.util.Stack

typealias Nodes = List<Node>

class Node(val n: Int) { 

   var index   = -1  // -1 signifies undefined
   var lowLink = -1
   var onStack = false

   override fun toString()  = n.toString()

}

class DirectedGraph(val vs: Nodes, val es: Map<Node, Nodes>)

fun tarjan(g: DirectedGraph): List<Nodes> { 

   val sccs = mutableListOf<Nodes>()
   var index = 0
   val s = Stack<Node>()
   
   fun strongConnect(v: Node) {       
       // Set the depth index for v to the smallest unused index
       v.index = index
       v.lowLink = index
       index++ 
       s.push(v)
       v.onStack = true 
     
       // consider successors of v
       for (w in g.es[v]!!) {
           if (w.index < 0) {
               // Successor w has not yet been visited; recurse on it
               strongConnect(w)
               v.lowLink = minOf(v.lowLink, w.lowLink)
           }
           else if (w.onStack) {
               // Successor w is in stack s and hence in the current SCC
               v.lowLink = minOf(v.lowLink, w.index)
           }
       }

       // If v is a root node, pop the stack and generate an SCC
       if (v.lowLink == v.index) {
           val scc = mutableListOf<Node>()
           do {
               val w = s.pop()
               w.onStack = false
               scc.add(w)
           } 
           while (w != v)
           sccs.add(scc)
       }
   }

   for (v in g.vs) if (v.index < 0) strongConnect(v)
   return sccs

}

fun main(args: Array<String>) { 

   val vs = (0..7).map { Node(it) }   
   val es = mapOf(
       vs[0] to listOf(vs[1]),
       vs[2] to listOf(vs[0]),
       vs[5] to listOf(vs[2], vs[6]),
       vs[6] to listOf(vs[5]),
       vs[1] to listOf(vs[2]),
       vs[3] to listOf(vs[1], vs[2], vs[4]),
       vs[4] to listOf(vs[5], vs[3]),
       vs[7] to listOf(vs[4], vs[7], vs[6])
   )
   val g = DirectedGraph(vs, es)
   val sccs = tarjan(g)
   println(sccs.joinToString("\n"))

}</lang>

Output:
[2, 1, 0]
[6, 5]
[4, 3]
[7]

Perl

Translation of: Perl 6

<lang perl>use 5.016; use feature 'state'; use List::Util qw(min); use experimental qw(lexical_subs);

sub tarjan { 

   my (%k) = @_;
   my (%onstack, %index, %lowlink, @stack, @connected);

   my sub strong_connect {
       my ($vertex, $i) = @_;
       $index{$vertex}   = $i;
       $lowlink{$vertex} = $i + 1;
       $onstack{$vertex} = 1;
       push @stack, $vertex;
       for my $connection (@{$k{$vertex}}) {
           if (not defined $index{$connection}) {
               __SUB__->($connection, $i + 1);
               $lowlink{$vertex} = min($lowlink{$connection}, $lowlink{$vertex});
           }
           elsif ($onstack{$connection}) {
               $lowlink{$vertex} = min($index{$connection}, $lowlink{$vertex});
           }
       }
       if ($lowlink{$vertex} eq $index{$vertex}) {
           my @node;
           do {
               push @node, pop @stack;
               $onstack{$node[-1]} = 0;
           } while $node[-1] ne $vertex;
           push @connected, [@node];
       }
   }

   for (sort keys %k) {
       strong_connect($_, 0) unless $index{$_};
   }
   @connected;

}

my %test1 = ( 

            0 => [1],
            1 => [2],
            2 => [0],
            3 => [1, 2, 4],
            4 => [3, 5],
            5 => [2, 6],
            6 => [5],
            7 => [4, 6, 7]
           );

my %test2 = ( 

            'Andy' => ['Bart'],
            'Bart' => ['Carl'],
            'Carl' => ['Andy'],
            'Dave' => [qw<Bart Carl Earl>],
            'Earl' => [qw<Dave Fred>],
            'Fred' => [qw<Carl Gary>],
            'Gary' => ['Fred'],
            'Hank' => [qw<Earl Gary Hank>]
           );

print "Strongly connected components:\n"; print join(', ', sort @$_) . "\n" for tarjan(%test1); print "\nStrongly connected components:\n"; print join(', ', sort @$_) . "\n" for tarjan(%test2);</lang>

Output:
Strongly connected components:
0, 1, 2
5, 6
3, 4
7

Strongly connected components:
Andy, Bart, Carl
Fred, Gary
Dave, Earl
Hank

Perl 6

Works with: Rakudo version 2018.09

<lang perl6>sub tarjan (%k) { 

   my %onstack;
   my %index;
   my %lowlink;
   my @stack;
   my @connected;

   sub strong-connect ($vertex) {
        state $index      = 0;
        %index{$vertex}   = $index;
        %lowlink{$vertex} = $index++;
        %onstack{$vertex} = True;
        @stack.push: $vertex;
        for |%k{$vertex} -> $connection {
            if not %index{$connection}.defined {
                strong-connect($connection);
                %lowlink{$vertex} min= %lowlink{$connection};
            }
            elsif %onstack{$connection} {
                %lowlink{$vertex} min= %index{$connection};
            }
       }
       if %lowlink{$vertex} eq %index{$vertex} {
           my @node;
           repeat {
               @node.push: @stack.pop;
               %onstack{@node.tail} = False;
           } while @node.tail ne $vertex;
           @connected.push: @node;
       }
   }

   .&strong-connect unless %index{$_} for %k.keys;

   @connected

}

  1. TESTING

-> $test { say "\nStrongly connected components: ", |tarjan($test).sort».sort } for

  1. hash of vertex, edge list pairs

(((1),(2),(0),(1,2,4),(3,5),(2,6),(5),(4,6,7)).pairs.hash),

  1. Same layout test data with named vertices instead of numbered.

%(:Andy<Bart>, 

 :Bart<Carl>,
 :Carl<Andy>,
 :Dave<Bart Carl Earl>,
 :Earl<Dave Fred>,
 :Fred<Carl Gary>,
 :Gary<Fred>,
 :Hank<Earl Gary Hank>

)</lang>

Output:
Strongly connected components: (0 1 2)(3 4)(5 6)(7)

Strongly connected components: (Andy Bart Carl)(Dave Earl)(Fred Gary)(Hank)

Phix

Translation of: Go

Same data as other examples, but with 1-based indexes. <lang Phix>constant g = {{2}, {3}, {1}, {2,3,5}, {6,4}, {3,7}, {6}, {5,8,7}}

sequence index, lowlink, stacked, stack integer x

function strong_connect(integer n, r_emit) 

   index[n] = x
   lowlink[n] = x
   stacked[n] = 1
   stack &= n
   x += 1
   for b=1 to length(g[n]) do
       integer nb = g[n][b]
       if index[nb] == 0 then
           if not strong_connect(nb,r_emit) then
               return false
           end if
           if lowlink[nb] < lowlink[n] then
               lowlink[n] = lowlink[nb]
           end if
       elsif stacked[nb] == 1 then
           if index[nb] < lowlink[n] then
               lowlink[n] = index[nb]
           end if
       end if
   end for
   if lowlink[n] == index[n] then
       sequence c = {}
       while true do
           integer w := stack[$]
           stack = stack[1..$-1]
           stacked[w] = 0
           c = prepend(c, w)
           if w == n then
               call_proc(r_emit,{c})
               exit
           end if
       end while
   end if
   return true

end function

procedure tarjan(sequence g, integer r_emit) 

   index   = repeat(0,length(g))
   lowlink = repeat(0,length(g))
   stacked = repeat(0,length(g))
   stack = {}
   x := 1
   for n=1 to length(g) do
       if index[n] == 0
       and not strong_connect(n,r_emit) then
           return
       end if
   end for

end procedure

procedure emit(object c) -- called for each component identified. -- each component is a list of nodes. 

   ?c

end procedure

tarjan(g,routine_id("emit"))</lang>

Output:
{1,2,3}
{6,7}
{4,5}
{8}

Python

Python: As function

<lang python>from collections import defaultdict

def from_edges(edges): 

   translate list of edges to list of nodes

   class Node:
       def __init__(self):
           # root is one of:
           #   None: not yet visited
           #   -1: already processed
           #   non-negative integer: what Wikipedia pseudo code calls 'lowlink'
           self.root = None
           self.succ = []

   nodes = defaultdict(Node)
   for v,w in edges:
       nodes[v].succ.append(nodes[w])

   for i,v in nodes.items(): # name the nodes for final output
       v.id = i

   return nodes.values()

def trajan(V): 

   def strongconnect(v, S):
       v.root = pos = len(S)
       S.append(v)

       for w in v.succ:
           if w.root is None:  # not yet visited
               yield from strongconnect(w, S)

           if w.root >= 0:  # still on stack
               v.root = min(v.root, w.root)

       if v.root == pos:  # v is the root, return everything above
           res, S[pos:] = S[pos:], []
           for w in res:
               w.root = -1
           yield [r.id for r in res]

   for v in V:
       if v.root is None:
           yield from strongconnect(v, [])


tables = [ # table 1 

           [(1,2), (3,1), (3,6), (6,7), (7,6), (2,3), (4,2),
            (4,3), (4,5), (5,6), (5,4), (8,5), (8,7), (8,6)],

           # table 2
           [('A', 'B'), ('B', 'C'), ('C', 'A'), ('A', 'Other')]]

for table in (tables): 

   for g in trajan(from_edges(table)):
       print(g)
   print()</lang>
Output:
[6, 7]
[1, 2, 3]
[4, 5]
[8]

['Other']
['A', 'B', 'C']

Python: As class

This takes inspiration from the Geeks4Geeks explanation and uses its five examples.


Tx1
+---+     +---+     +---+     +---+
| 1 | --> | 0 | --> | 3 | --> | 4 |
+---+     +---+     +---+     +---+
  ^         |
  |         |
  |         v
  |       +---+
  +------ | 2 |
          +---+
Tx2
+---+     +---+     +---+     +---+
| 0 | --> | 1 | --> | 2 | --> | 3 |
+---+     +---+     +---+     +---+
Tx3

  +----------------------------------+
  v                                  |
+---+     +---+     +---+     +---+  |
| 0 | --> |   | --> | 3 | --> | 5 |  |
+---+     |   |     +---+     +---+  |
          |   |                 ^    |
          | 1 |                 |    |
          |   |                 |    |
+---+     |   |     +---+       |    |
| 6 | <-- |   | --> | 2 | ------+----+
+---+     +---+     +---+       |
            |                   |
            |                   |
            v                   |
          +---+                 |
          | 4 | ----------------+
          +---+
Tx4

  +-----------------------------+
  |                             |
  |       +---+                 |
  |       | A |                 |         +-------------------+
  |       +---+                 |         |                   |
  |                             |         |                   |
  |                   +---------+---------+---------+         |                   +---------+
  |                   |         v         v         v         |                   v         |
+---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
| 3 | <-- | 0 | --> | 1 | --> | 2 | --> | 6 | --> | 4 | --> |   | --> | 7 | --> | 9 | --> | 8 |
+---+     +---+     +---+     +---+     +---+     +---+     |   |     +---+     +---+     +---+
            ^                   |         ^         |       |   |                 ^         ^
            +-------------------+         +---------+       | 5 | ----------------+         |
                                                            |   |                           |
                                                            |   |                           |
                                                            |   | --------------------------+
                                                            +---+
Tx5

                      +--------------+
                      |              |
                      |              |
  +-------------------+---------+    |
  v                   v         |    |
+---+     +---+     +---+     +---+  |
| 0 | --> | 1 | --> | 2 | --> | 3 |  |
+---+     +---+     +---+     +---+  |
                      |              |
                      |              |
                      v              |
                    +---+            |
                    | 4 | -----------+
                    +---+
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>
Output:
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]

Racket

Manual implementation

Translation of: Kotlin

<lang racket>#lang racket

(require syntax/parse/define 

        fancy-app
        (for-syntax racket/syntax))

(struct node (name index low-link on?) #:transparent #:mutable 

 #:methods gen:custom-write
 [(define (write-proc v port mode) (fprintf port "~a" (node-name v)))])

(define-syntax-parser change! 

 [(_ x:id f) #'(set! x (f x))]
 [(_ accessor:id v f)
  #:with mutator! (format-id this-syntax "set-~a!" #'accessor)
  #'(mutator! v (f (accessor v)))])

(define (tarjan g) 

 (define sccs '())
 (define index 0)
 (define s '())

 (define (dfs v)
   (set-node-index! v index)
   (set-node-low-link! v index)
   (set-node-on?! v #t)
   (change! s (cons v _))
   (change! index add1)

   (for ([w (in-list (hash-ref g v '()))])
     (match-define (node _ index low-link on?) w)
     (cond
       [(not index) (dfs w)
                    (change! node-low-link v (min (node-low-link w) _))]
       [on? (change! node-low-link v (min index _))]))

   (when (= (node-low-link v) (node-index v))
     (define-values (scc* s*) (splitf-at s (λ (w) (not (eq? w v)))))
     (set! s (rest s*))
     (define scc (cons (first s*) scc*))
     (for ([w (in-list scc)]) (set-node-on?! w #f))
     (change! sccs (cons scc _))))

 (for* ([(u _) (in-hash g)] #:when (not (node-index u))) (dfs u))
 sccs)

(define (make-graph xs) 

 (define store (make-hash))
 (define (make-node v) (hash-ref! store v (thunk (node v #f #f #f))))
 
 ;; it's important that we use hasheq instead of hash so that we compare
 ;; reference instead of actual value. Had we use the actual value,
 ;; the key would be a mutable value, which causes undefined behavior
 (for/hasheq ([vs (in-list xs)]) (values (make-node (first vs)) (map make-node (rest vs)))))

(tarjan (make-graph '([0 1] 

                     [2 0]
                     [5 2 6]
                     [6 5]
                     [1 2]
                     [3 1 2 4]
                     [4 5 3]
                     [7 4 7 6])))</lang>
Output:
'((7) (3 4) (5 6) (2 1 0))

With the graph library

<lang racket>#lang racket

(require graph)

(define g (unweighted-graph/adj '([0 1] 

                                 [2 0]
                                 [5 2 6]
                                 [6 5]
                                 [1 2]
                                 [3 1 2 4]
                                 [4 5 3]
                                 [7 4 7 6])))

(scc g)</lang>

Output:
'((7) (3 4) (5 6) (1 0 2))

Sidef

Translation of: Perl 6

<lang ruby>func tarjan (k) { 

   var(:onstack, :index, :lowlink, *stack, *connected)

   func strong_connect (vertex, i=0) {

        index{vertex}   = i
        lowlink{vertex} = i+1
        onstack{vertex} = true
        stack << vertex

        for connection in (k{vertex}) {
            if (index{connection} == nil) {
                strong_connect(connection, i+1)
                lowlink{vertex} `min!` lowlink{connection}
            }
            elsif (onstack{connection}) {
                lowlink{vertex} `min!` index{connection}
            }
       }

       if (lowlink{vertex} == index{vertex}) {
           var *node
           do {
               node << stack.pop
               onstack{node.tail} = false
           } while (node.tail != vertex)
           connected << node
       }
   }

   { strong_connect(_) if !index{_} } << k.keys

   return connected

}

var tests = [ 

   Hash(
        0 => <1>,
        1 => <2>,
        2 => <0>,
        3 => <1 2 4>,
        4 => <3 5>,
        5 => <2 6>,
        6 => <5>,
        7 => <4 6 7>,
   ),
   Hash(
       :Andy => <Bart>,
       :Bart => <Carl>,
       :Carl => <Andy>,
       :Dave => <Bart Carl Earl>,
       :Earl => <Dave Fred>,
       :Fred => <Carl Gary>,
       :Gary => <Fred>,
       :Hank => <Earl Gary Hank>,
   )

]

tests.each {|t| 

   say ("Strongly connected components: ", tarjan(t).map{.sort}.sort)

}</lang>

Output:
Strongly connected components: [["0", "1", "2"], ["3", "4"], ["5", "6"], ["7"]]
Strongly connected components: [["Andy", "Bart", "Carl"], ["Dave", "Earl"], ["Fred", "Gary"], ["Hank"]]

zkl

<lang zkl>class Tarjan{ 

  // input: graph G = (V, Es)
  // output: set of strongly connected components (sets of vertices)
  // Ick: class holds global state for strongConnect(), otherwise inert
  const INDEX=0, LOW_LINK=1, ON_STACK=2;
  fcn init(graph){
     var index=0, stack=List(), components=List(), 
         G=List.createLong(graph.len(),0);

     // convert graph to ( (index,lowlink,onStack),(id,links)), ...)
     // sorted by id
     foreach v in (graph){ G[v[0]]=T( L(Void,Void,False),v) }

     foreach v in (G){ if(v[0][INDEX]==Void) strongConnect(v) }

     println("List of strongly connected components:");
     foreach c in (components){ println(c.reverse().concat(",")) }

     returnClass(components);	// over-ride return of class instance
  }
  fcn strongConnect(v){  // v is ( (index,lowlink,onStack), (id,links) )
     // Set the depth index for v to the smallest unused index
     v0:=v[0]; v0[INDEX]=v0[LOW_LINK]=index;
     index+=1;
     v0[ON_STACK]=True;
     stack.push(v);

      // Consider successors of v
     foreach idx in (v[1][1,*]){  // links of v to other vs
        w,w0 := G[idx],w[0];	// well, that is pretty vile

if(w[0][INDEX]==Void){ strongConnect(w); // Successor w not yet visited; recurse on it v0[LOW_LINK]=v0[LOW_LINK].min(w0[LOW_LINK]); } else if(w0[ON_STACK]) // Successor w is in stack S and hence in the current SCC v0[LOW_LINK]=v0[LOW_LINK].min(w0[INDEX]); 

     }
     // If v is a root node, pop the stack and generate an SCC
     if(v0[LOW_LINK]==v0[INDEX]){
        strong:=List();  // start a new strongly connected component

do{ w,w0 := stack.pop(), w[0]; w0[ON_STACK]=False; strong.append(w[1][0]); // add w to strongly connected component }while(w.id!=v.id); components.append(strong); // output strongly connected component 

     }
  }

}</lang> <lang zkl> // graph from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm 

  // with vertices id zero based (vs 1 based in article)
  // ids start at zero and are consecutive (no holes), graph is unsorted

graph:= // ( (id, links/Edges), ...) 

  T( T(0,1), T(2,0),     T(5,2,6), T(6,5),
     T(1,2), T(3,1,2,4), T(4,5,3), T(7,4,7,6) );

Tarjan(graph);</lang>

Output:
0,1,2
5,6
3,4
7
Retrieved from "https://rosettacode.org/wiki/Tarjan?oldid=274231"