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.