JavaScript Implementation of Tarjan's Cycle Detection Algorithm

Abstract from the original article by Robert Tarjan (1972)

Tarjan's strongly connected components algorithm, published in paper Enumeration of the Elementary Circuits of a Directed Graph by Robert Tarjan in 1972, is a graph theory algorithm for detecting all cycles and loops (edges connecting vertices to themselves) in a directed graph.

It performs a single pass of depth-first search. It maintains a stack of vertices that have been explored by the search but not yet assigned to a component, and calculates "low numbers" of each vertex (an index number of the highest ancestor reachable in one step from a descendant of the vertex) which it uses to determine when a set of vertices should be popped off the stack into a new component.

It is trivial to write algorithms to detect cycles in a graph, but most approaches prove highly impractical due to the immense time and storage they require to complete the computation. Tarjan's algorithm is one of the precious few that is able to compute strongly connected components in linear time (time increases linearly with the number of vertices and edges).
The others include Kosaraju's algorithm and the path-based strong component algorithm (Purdo, Munro, Dijkstra, Cheriyan & Mehlhorn, Gabow). Although Kosaraju's algorithm is conceptually simple, Tarjan's and the path-based algorithm are favoured in practice since they require only one depth-first search rather than two.

See a demo at CodePen.

This JavaScript implementation of Tarjan's algorithm is based on the PHP version I created in 2015.

Questions, issues and comments are most welcome in the GitHub repository: js-tarjan.

/*
 * Array $G is to contain the source graph in node-adjacency format.
 */
var $G = [];
$G.push(<span className="dropcap">1</span>);
$G.push([4, 6, 7]);
$G.push([4, 6, 7]);
$G.push([4, 6, 7]);
$G.push([2, 3]);
$G.push([2, 3]);
$G.push([5, 8]);
$G.push([5, 8]);
$G.push([]);
$G.push([]);
$G.push(<span className="dropcap">10</span>); // This is a self-cycle (aka "loop").

console.log($G);

/*
 * There are 11 results for the above example (strictly speaking: 10 cycles and 1 loop):
 * 2|4
 * 2|4|3|6|5
 * 2|4|3|7|5
 * 2|6|5
 * 2|6|5|3|4
 * 2|7|5
 * 2|7|5|3|4
 * 3|4
 * 3|6|5
 * 3|7|5
 * 1|0
 */
var $cycles = js_tarjan_entry($G);
console.log("Cycles found: " + $cycles.length);
console.log($cycles);

// All the following must be global to pass them to recursive function js_tarjan().
var $cycles;
var $marked;
var $marked_stack;
var $point_stack;

/*
 * js_tarjan_entry() iterates through the graph array rows, executing js_tarjan().
 */
function js_tarjan_entry($G_local) {
  // Initialize global values that are so far undefined.
  $cycles = [];
  $marked = [];
  $marked_stack = [];
  $point_stack = [];

  for (let $x = 0; $x < $G_local.length; $x++) {
    $marked[$x] = false;
  }

  for (let $i = 0; $i < $G_local.length; $i++) {
    js_tarjan($i, $i);
    while ($marked_stack.length > 0) {
      $marked[$marked_stack.pop()] = false;
    }
    // console.log($i + 1 + ' / ' + $G_local.length); // Enable if you wish to follow progression through the array rows.
  }

  $cycles = Object.keys($cycles);

  return $cycles;
}

/*
 * Recursive function to detect strongly connected components (cycles, loops).
 */
function js_tarjan($s, $v) {
  // Update global values.
  $marked[$v] = true;
  $marked_stack.push($v);
  $point_stack.push($v);

  // Define local values.
  let $f = false;
  let $t;

  // var $maxlooplength = 3; // Enable to Limit the length of loops to keep in the results (see below).

  $G[$v]?.forEach(($w) => {
    if ($w < $s) {
      $G[$w] = [];
    } else if ($w === $s) {
      // if ($point_stack.length == $maxlooplength){ // Enable to collect cycles of a given length only.
      // Add new cycles as array keys to avoid duplication. Way faster than using array search.
      $cycles[$point_stack.join("|")] = true;
      // }
      $f = true;
    } else if ($marked[$w] === false) {
      // if ($point_stack.length < $maxlooplength){ // Enable to only collect cycles up to $maxlooplength.
      $t = js_tarjan($s, $w);
      // }
      if ($f.length !== 0 || $t.length !== 0) {
        $f = true;
      }
    }
  });

  if ($f === true) {
    while ($marked_stack.slice(-1)<span className="dropcap">0</span> !== $v) {
      $marked[$marked_stack.pop()] = false;
    }
    $marked_stack.pop();
    $marked[$v] = false;
  }

  $point_stack.pop();

  return $f;
}

Demo^#

Tomáš Fülöpp

Sint-Agatha-Berchem, Belgium

December 7, 2021, December 8, 2021, December 9, 2021, February 17, 2022

GitHub

Files

Robert Tarjan - Enumeration of the Elementary Circuits of a Directed Graph (September 1972)

Children

Loop Mining in the Encyclopedia of World Problems

Socials

https://twitter.com/vacilandois/status/1468727583277785089

JavaScript Implementation of Tarjan's Cycle Detection Algorithm

Demo#

Demo^#