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;// => [ { firstIndex: 0, stepsFromStart: 0, length: 5 } ]
Each node being an array of out-edges:
var arrayPath = 1 3 2 3 1; floyd;// => [ { 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;// => [ { 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;// => [ { firstIndex: 3, stepsFromStart: 2, length: 1 } ]
The path being an object with arbitrary edge keys:
var objectGraph = object1: 'object2' object2: 'object3' object3: 'object1'; floyd;// => [ { 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.