🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more

strongly-connected-components

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install
s

strongly-connected-components

Computes strongly connected components of a directed graph

1.0.1
latest
Version published
Weekly downloads
249K
0.33%
Maintainers
1
Weekly downloads
 
Created
Issues
1

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.

FAQs

Package last updated on 31 Mar 2014

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts