strongly-connected-components
Computes strongly connected components of a directed graph
npm install strongly-connected-components
Want to see pretty graphs? Log in now!
7 | downloads in the last week |
25 | downloads in the last month |
Last Published By | |
---|---|
Version | 1.0.1 last updated 18 days ago |
License | MIT |
Keywords | strongly, connected, component, directed, graph, tarjan |
Repository | git://github.com/mikolalysenko/strongly-connected-components.git (git) |
Homepage | https://github.com/mikolalysenko/strongly-connected-components |
Bugs | https://github.com/mikolalysenko/strongly-connected-components/issues |
Dependencies | None |
Dependents | 2-sat, mikolalysenko-hoarders |
Starred by | niclashoyer |
strongly-connected-components
Given a directed graph, splits it into strongly connected components.
Example
var scc = require("strongly-connected-components")
var adjacencyList = [
[4], // 0
[0,2], // 1
[1,3], // 2
[2], // 3
[1], // 4
[4,6], // 5
[5,2], // 6
[7,6,3], // 7
]
console.log(scc(adjacencyList))
Install
npm install strongly-connected-components
API
require("strongly-connected-components")(adjacencyList)
Computes the strongly connected components of a graph using Tarjan's algorithm.
adjacencyList
is an array of lists representing the directed edges of the graph
Returns An object containing:
components
: an array of arrays representing the partitioning of the vertices in the graph into connected components.adjacencyList
: an array lists representing the directed edges of the directed acyclic graph between the strongly connected components
Credits
(c) 2013 Mikola Lysenko. MIT License. Based on the implementation of Tarjan's algorithm on Wikipedia.