Hanser Ring Finder

Find ring structures in reasonably sized graphs, such as molecular graphs. Works in node and in the browser.

Installation

node.js:

npm install hanser-ring-finder

browser:

component install viatropos/hanser-ring-finder

Example

This simple graph structure creates a triangle with an extra edge sticking out (so there is one cycle and one extra edge):

var graph = {
  nodes:
   [ { id: 0 },
     { id: 1 },
     { id: 2 },
     { id: 3 } ],
  edges:
   [ { source: 0, target: 1 },
     { source: 1, target: 2 },
     { source: 2, target: 0 },
     { source: 3, target: 0 } ];

Then just pass that into the hanser function and it will return a set of arrays containing the indices of nodes that create a complete cycle:

var hanser = require('hanser-ring-finder');
var cycles = hanser(graph);
// [ [ 0, 2, 1 ] ]

Combine this with the mol-parser, and you can parse a chemical mol file and find the rings in it. Here is how you'd do that for a cholesterol.mol:

var mol = require('mol-parser');
var hanser = require('hanser-ring-finder');
var graph = mol(cholesterol); // mol file string
var cycles = hanser(graph);

Resources

• Lots of help from https://github.com/rapodaca/mx
• and http://efficientbits.blogspot.com/2013/06/implementing-hansers-path-graph.html

Licence

MIT