@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.
yarn add @rtsao/scc
npm install @rtsao/scc
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' } ]
┌───┐ ┌───┐ │ d │ ◀── │ a │ ◀┐ └───┘ └───┘ │ │ │ │ ▼ ▼ │ ┌───┐ ┌───┐ │ │ e │ │ c │ │ └───┘ └───┘ │ │ │ ▼ │ ┌───┐ │ │ b │ ─┘ └───┘