Package Exports

@rtsao/scc
@rtsao/scc/index.js

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@rtsao/scc) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

`@rtsao/scc`

Find strongly connected components of a directed graph using Tarjan's algorithm.

This algorithm efficiently yields both a topological order and list of any cycles.

Installation

yarn add @rtsao/scc

npm install @rtsao/scc

Usage

const scc = require("@rtsao/scc");

const digraph = new Map([
  ["a", new Set(["c", "d"])],
  ["b", new Set(["a"])],
  ["c", new Set(["b"])],
  ["d", new Set(["e"])],
  ["e", new Set()]
]);

const components = scc(digraph);
// [ Set { 'e' }, Set { 'd' }, Set { 'b', 'c', 'a' } ]

Illustration of example input digraph

┌───┐     ┌───┐
│ d │ ◀── │ a │ ◀┐
└───┘     └───┘  │
  │         │    │
  ▼         ▼    │
┌───┐     ┌───┐  │
│ e │     │ c │  │
└───┘     └───┘  │
            │    │
            ▼    │
          ┌───┐  │
          │ b │ ─┘
          └───┘