path-scc

1.0.2 • Public • Published

Path-based strong component algorithm

Find all strongly-connected components in a graph structure. These can be used to identify cycles (= components with more than one node).

Usage

``````const scc = require('scc').scc // or: import {scc} from 'scc'
const nodes = [{ id: 'A' }, { id: 'B' }]
const links = [{ source: 'A', target: 'B' }, { source: 'B', target: 'A' }]
components == [{ id: 'A' }, { id: 'B' }]
``````

TypeScript type declarations are included.

Description

Source: WikiPedia

The algorithm performs a depth-first search of the given graph G, maintaining as it does two stacks S and P (in addition to the normal call stack for a recursive function). Stack S contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices. Stack P contains vertices that have not yet been determined to belong to different strongly connected components from each other. It also uses a counter C of the number of vertices reached so far, which it uses to compute the preorder numbers of the vertices.

When the depth-first search reaches a vertex v, the algorithm performs the following steps:

1. Set the preorder number of v to C, and increment C.
2. Push v onto S and also onto P.
3. For each edge from v to a neighboring vertex w:
• If the preorder number of w has not yet been assigned, recursively search w;
• Otherwise, if w has not yet been assigned to a strongly connected component:
• Repeatedly pop vertices from P until the top element of P has a preorder number less than or equal to the preorder number of w.
4. If v is the top element of P:
• Pop vertices from S until v has been popped, and assign the popped vertices to a new component.
• Pop v from P.

The overall algorithm consists of a loop through the vertices of the graph, calling this recursive search on each vertex that does not yet have a preorder number assigned to it.

Package Sidebar

Install

`npm i path-scc`

Repository

github.com/jdiehl/path-scc

2

1.0.2