Detect graph cycle, in Javascript

After searching for some times, I start making my own graph cycle algorithm.

The idea is to have a lightweight code, both in terms of performance and size, to be able to ship it in browser directly. The code use underscore.js, but ca be easily workaround if you don’t use it…

The algorithm is based on Kahn’s algorithm which can be found in pseudo-code here. The implementation provided here does follow it strictly.

Here is the code (License: MIT), and have fun:

/**
 * LICENSE: MIT
*/

// Node.JS need to import underscore first
if (typeof module !== 'undefined' && module.exports) {
  var _ = require('underscore');
}

/**
 * Try to get a topological sorting out of directed graph.
 *
 * @param nodes {Object} A list of nodes, including edges (see below).
 * @return {Array | Null} An array if the topological sort could succeed, null if there is any cycle somewhere.
*/
function toposort (nodes) {
  // Test if a node got any icoming edge
  function hasIncomingEdge(list, node) {
    for (var i = 0, l = list.length; i < l; ++i) {
      if (_.contains(list[i].links, node._id)) {
        return true;
      }
    }
    return false;
  };

  // Kahn Algorithm
  var L = [],
      S = _.filter(nodes, function(node) {
        return !hasIncomingEdge(nodes, node);
      }),
      n = null;

  while(S.length) {
    // Remove a node n from S
    n = S.pop();
    // Add n to tail of L
    L.push(n);

    var i = n.links.length;
    while (i--) {
      // Getting the node associated to the current stored id in links
      var m = _.findWhere(nodes, {
        _id: n.links[i]
      });

      // Remove edge e from the graph
      n.links.pop();

      if (!hasIncomingEdge(nodes, m)) {
        S.push(m);
      }
    }
  }

  // If any of them still got links, there is cycle somewhere
  var nodeWithEdge = _.find(nodes, function(node) {
    return node.links.length !== 0;
  });

  return (nodeWithEdge) ? null: L;
}

To use it, quite simple:

// see: https://en.wikipedia.org/wiki/File:Directed_acyclic_graph.png
var nodes = [
  {  _id: "3",  links: ["8", "10"]      },
  {  _id: "5",  links: ["11"]           },
  {  _id: "7",  links: ["11", "8"]      },
  {  _id: "8",  links: ["9"]            },
  {  _id: "11", links: ["2", "9", "10"] },
  {  _id: "10", links: []               },
  {  _id: "9",  links: []               },
  {  _id: "2",  links: []               }
];

var result = toposort(nodes);

if (result === null) {
  console.error('Graph got cycle somehwere');
} else {
  console.log('topological sorting:');
  console.log(result);
}

The links are the edges starting from this point, and of course, the number inside are other « _id » elements.
This example is a direct relation to this schema provided in the Wikipedia article.

Here is for example a failing graph:

var nodes = [
  {  _id: "3",  links: ["8", "10"]      },
  {  _id: "5",  links: ["11"]           },
  {  _id: "7",  links: ["11", "8"]      },
  {  _id: "8",  links: ["9"]            },
  {  _id: "11", links: ["2", "9", "10"] },
  {  _id: "10", links: ["7"]            },
  {  _id: "9",  links: []               },
  {  _id: "2",  links: []               }
];

Will fail because the id « 10 » is back linked to id « 7 », making a cycle with « 7 », « 11 » and « 10 »…

Hope you enjoy, have fun with!

Étiquettes : graph, javascript, node graph, toposort