floyd

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:

``bash
npm install floyd
`

Usage
-----

Floyd.js is usually called through its detectCycles function.

$3

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.

$3

A simple number path:

`javascript
// (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:

`javascript
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:

`javascript
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:

`javascript
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:

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

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

Options
-------

The following default options apply:

`javascript
{
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.