tarjan-graph
    TypeScript icon, indicating that this package has built-in type declarations

    2.0.0 • Public • Published

    tarjan-graph

    Build Status NPM version

    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

    Note: as of v1.0.0 this library requires node >= v8.0.0. Use v0.3.0 for node < v8.0.0.

    npm install tarjan-graph
    

    Usage

    All examples use the following graph:

    node -e "
    const Graph = require('tarjan-graph');
     
    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

    Dat Graph

    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
    }
    */

    Keywords

    none

    Install

    npm i tarjan-graph

    DownloadsWeekly Downloads

    3,858

    Version

    2.0.0

    License

    MIT

    Unpacked Size

    7.21 kB

    Total Files

    4

    Last publish

    Collaborators

    • tmont