

 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

 The article on Wikipedia.


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)