myrlund/floyd

An extremely simple cycle-detection library for CommonJS.

Floyd.js

Floyd.js is an extremely simple, yet versatile cycle-detection library in JS. It (surprisingly) implements a version of Floyd's algorithm.

Installation

Grab it directly from Github by cloning or install it with NPM:

npm install floyd

Usage

Floyd.js is usually called through its detectCycles function.

detectCycles(path, [options])

This function takes a path and an optional options object.

A path is an array comprised of nodes. Each node exposes a set of outgoing edges, referencing the indices of other nodes in the path.

A node can either be an array of indices directly, or be an object exposing them through a property.

Examples

A simple number path:

// (0) -> (1) -> (2) -> (3) -> (0)
var numberPath = [1, 2, 3, 0];

floyd.detectCycles(numberPath);
// => [ { firstIndex: 0, stepsFromStart: 0, length: 5 } ]

Each node being an array of out-edges:

var arrayPath = [
    [1, 3],
    [2],
    [3],
    [1],
];

floyd.detectCycles(arrayPath);
// => [ { firstIndex: 3, stepsFromStart: 1, length: 3 } ]

Each node being an object with out-edges exposed in a property:

var disconnectedPath = [
    {'out': [1]},
    {},
    {'out': [3]},
    {'out': [2]},
];

floyd.detectCycles(disconnectedPath);
// => [ { firstIndex: 2, stepsFromStart: 2, length: 2 } ]

Each node being an object comprised of both in-edges and out-edges, and non-default property names:

var complexPath = [
    {},
    {'incoming': [3], 'outgoing': [2, 3]},
    {'incoming': [3]},
    {'incoming': [0], 'outgoing': [3]},
    {'incoming': [1], 'outgoing': [1]},
];

floyd.detectCycles(complexPath, {
    outNodePropertyName: 'outgoing',
    inNodePropertyName: 'incoming',
    normalizePath: true
});
// => [ { firstIndex: 3, stepsFromStart: 2, length: 1 } ]

The path being an object with arbitrary edge keys:

var objectGraph = {
    object1: ['object2'],
    object2: ['object3'],
    object3: ['object1'],
};

floyd.detectCycles(objectGraph);
// => [ { firstKey: 'object1', stepsFromStart: 0, length: 3 } ]

Options

The following default options apply:

{
    outEdgePropertyName: 'out',
    inEdgePropertyName: 'in',
    normalizePath: false
}

Known Issues

• When several cycles partially overlap, not all of them will be returned. Usually in such cases, the shortest cycle (from the start node) is returned.

floyd's Issues

floyd doesn't return (quickly) from a certain path

floyd.detectCycles([ [ 0, 3 ], [ 1, 3 ], [ 2, 3 ], [ 0, 11 ], [ 11, 3 ] ])

does not return.

Floyd runs interminably and without returning a value in certain case

A graph [[2],[2],[3,4],[],[3]] causes Floyd to run interminably and without returning a value. This effectively crashes the browser.

Here is a test case ( run it at https://npm.runkit.com/floyd ):

var floyd = require("floyd");

//var edges = [[2],[2],[3,4],[],[4]]  // -- Works
  var edges = [[2],[2],[3,4],[],[3]]  // -- Does not work - runs interminably.

var result = floyd.detectCycles(edges);