tarjan-graph

This is a simple directed graph lib, mostly just for checking if a directed graph contains a cycle. It uses Tarjan's algorithm for checking if the graph contains a cycle.

This library also has some very basic Graphviz support for visualizing graphs using the DOT language.

Installation

Install using npm:

npm install tarjan-graph

• Note: as of v1.0.0 this library requires node >= v8.0.0. Use v0.3.0 for node < v8.0.0.
• Note: as of v3.0.0 this library was ported to TypeScript and the default export changed to get with the times. So now instead of this:

  const Graph = require('tarjan-graph');  // js
  import Graph = require('tarjan-graph'); // ts

  you now do this:

  const Graph = require('tarjan-graph').default; // js
  import Graph from 'tarjan-graph';              // ts

Usage

JavaScript:

const Graph = require('tarjan-graph').default;

TypeScript:

import Graph from 'tarjan-graph';

All examples use the following graph:

node -e "
const Graph = require('tarjan-graph').default;

const graph = new Graph()
  .add('a', ['b', 'c'])
  .add('b', ['d', 'e'])
  .add('c', ['b'])
  .add('d', ['e'])
  .add('e', ['c'])
  .add('f', ['c', 'a', 'g'])
  .add('g', ['h', 'i'])
  .add('h', ['j'])
  .add('i', ['j'])
  .add('j', ['f', 'k'])
  .add('k', ['k']);

console.log(graph.toDot());
" | dot -o docs/example-graph.png -Tpng`

Doing stuff with cycles:

console.log(graph.hasCycle()); 
//true
console.log(graph.getCycles());
// [ 
//   [ { name: 'b', successors: [...] }, { name: 'e', ... }, ... ], 
//   ... 
// ]

//use addAndVerify() instead of add() to throw an error when adding
//an edge would create a cycle

Doing stuff with SCCs:

//same as graph.getCycles() except includes single vertices
console.log(graph.getStronglyConnectedComponents());

Searching:

//depth-first search (pre-order)
graph.dfs('g', (v) => {
  console.log(v.name + ': ' + v.successors.map(w => w.name).join(', '));
});
/*
g: i, h
h: j
j: k, f
f: g, a, c
c: b
b: e, d
d: e
e: c
a: c, b
k: k
i: j
*/

//retrieve descendants
console.log(graph.getDescendants('a'));
//[ 'b', 'd', 'e', 'c' ]

And of course, dat dot:

console.log(graph.toDot());
/*
digraph {
  subgraph cluster0 {
    color=red;
    d; c; e; b;
  }
  subgraph cluster1 {
    color=red;
    k;
  }
  subgraph cluster2 {
    color=red;
    h; f; j; i; g;
  }
  b -> e
  b -> d
  c -> b
  a -> c
  a -> b
  d -> e
  e -> c
  g -> i
  g -> h
  f -> g
  f -> a
  f -> c
  h -> j
  i -> j
  j -> k
  j -> f
  k -> k
}
*/