Skip to content
/ scc Public

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

License

Notifications You must be signed in to change notification settings

rtsao/scc

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

@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 │ ─┘
          └───┘

About

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

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published