biconnected-components
Find biconnected component in a graph using algorithm by John Hopcroft and Robert Tarjan
Last updated 4 years ago by chr.vadala .
MIT · Repository · Bugs · Original npm · Tarball · package.json
$ cnpm install biconnected-components 
SYNC missed versions from official npm registry.

biconnected-components

Find biconnected component in a graph using algorithm by John Hopcroft and Robert Tarjan

npm install --save biconnected-components
  let g = new Graph(12);
  g.addEdge(0, 1);
  g.addEdge(1, 0);
  g.addEdge(1, 2);
  g.addEdge(2, 1);
  g.addEdge(1, 3);
  g.addEdge(3, 1);
  g.addEdge(2, 3);
  g.addEdge(3, 2);
  g.addEdge(2, 4);
  g.addEdge(4, 2);
  g.addEdge(3, 4);
  g.addEdge(4, 3);
  g.addEdge(1, 5);
  g.addEdge(5, 1);
  g.addEdge(0, 6);
  g.addEdge(6, 0);
  g.addEdge(5, 6);
  g.addEdge(6, 5);
  g.addEdge(5, 7);
  g.addEdge(7, 5);
  g.addEdge(5, 8);
  g.addEdge(8, 5);
  g.addEdge(7, 8);
  g.addEdge(8, 7);
  g.addEdge(8, 9);
  g.addEdge(9, 8);
  g.addEdge(10, 11);
  g.addEdge(11, 10);

  g.BCC();

  console.log(g.count);
  console.log(g.subgraphs);


  //  output
  //  [{u: 4, v: 2}, {u: 3, v: 4}, {u: 3, v: 1}, {u: 2, v: 3}, {u: 1, v: 2}],
  //  [{u: 8, v: 9}],
  //  [{u: 8, v: 5}, {u: 7, v: 8}, {u: 5, v: 7}],
  //  [{u: 6, v: 0}, {u: 5, v: 6}, {u: 1, v: 5}, {u: 0, v: 1}],
  //  [{u: 10, v: 11}]



Credits

JS porting of this code http://www.geeksforgeeks.org/biconnected-components/

Current Tags

  • 1.1.1                                ...           latest (4 years ago)

3 Versions

  • 1.1.1                                ...           4 years ago
  • 1.1.0                                ...           4 years ago
  • 1.0.0                                ...           4 years ago
Maintainers (1)
Downloads
Today 0
This Week 0
This Month 2
Last Day 0
Last Week 0
Last Month 1
Dependencies (2)
Dev Dependencies (0)
None
Dependents (0)
None

Copyright 2014 - 2016 © taobao.org |