An implementation of Tarjan's algorithm.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
es6
lib
test/unit/es6
.gitignore
README.md
index.js
license.txt
package.json

README.md

Tarjan

An implementation of Tarjan's algorithm.

Contents

Introduction

This algorithm partitions a graph into its strongly connected components. The Wikipedia page has a good explanation of the algorithm itself.

A graph can be constructed with the fromVertexLiterals() factory method as follows:

const tarjan = require('occam-tarjan');

const { Graph } = tarjan;

const graph = Graph.fromVertexLiterals(

  ['a', ['b', 'c']],
  ['b', ['b', 'd']],
  ['c', ['a']],
  ['d', []]
  
);

Note that the array of names that is the second element of each literal gives the descendants of the vertex and not its ancestors.

The cycles, vertices and strongly connected components of the graph are then made available:

const cycles = graph.getCycles(),
      vertices = graph.getVertices(),
      stronglyConnectedComponents = graph.getStronglyConnectedComponents();

Installation

With npm:

npm install occam-tarjan

You can also clone the repository with Git...

git clone https://github.com/jecs-imperial/occam-tarjan.git

...and then install the necessary modules with npm from within the project's root directory:

npm install

Building

Automation is done with npm scripts, have a look at the package.json file. The pertinent commands are:

npm run build-debug
npm run watch-debug

Acknowledgements

This implementation was closely based on the following:

https://github.com/tmont/tarjan-graph

Contact