graph.js

// Generated by CoffeeScript 1.6.3
/*

This module provides a layer of indirection between implementations of
(directed) graphs and client code.

At the minimum, a graph instance needs to implement three methods,
each returning an array of vertices:

    vertices    : ()  -> ... # The vertices of the graph
    predecessors: (v) -> ... # The direct predecessors of vertex v
    successors  : (v) -> ... # The direct successors of vertex v

Further methods will be used where present. For example, the function call
`equals(G, H)` will defer to `G.equals(H)` if the graph `G` has an attribute
`"equals"`.
*/

var adjacent, edges, equals, isEdge, isInternal, isIsolated, isSink, isSource, isVertex, predecessors, successors, vertices;

vertices = function(G) {
  /* The vertices of the given graph as an array.*/

  return G.vertices();
};

predecessors = function(G, v) {
  /* The immediate predecessors of vertex `v` in graph `G` as an array.*/

  return G.predecessors(v);
};

successors = function(G, v) {
  /* The immediate successors of vertex `v` in graph `G` as an array.*/

  return G.successors(v);
};

isVertex = function(G, v) {
  /* Tests whether `v` is a vertex of the graph `G`.*/

  if (G.isVertex != null) {
    return G.isVertex(v);
  } else {
    return vertices(G).indexOf(v) >= 0;
  }
};

isEdge = function(G, v, w) {
  /* Tests whether `[v, w]` is a directed edge of the graph `G`.*/

  if (G.isEdge != null) {
    return G.isEdge(v, w);
  } else {
    return successors(G, v).indexOf(w) >= 0;
  }
};

isSource = function(G, v) {
  /* Tests whether `v` is a vertex in `G` with no predecessors.*/

  if (G.isSource != null) {
    return G.isSource(v);
  } else {
    return predecessors(G, v).length === 0;
  }
};

isSink = function(G, v) {
  /* Tests whether `v` is a vertex in `G` with no successors.*/

  if (G.isSink != null) {
    return G.isSink(v);
  } else {
    return successors(G, v).length === 0;
  }
};

isInternal = function(G, v) {
  /*
  Tests whether `v` is a vertex in `G` with both predecessors and successors.
  */

  if (G.isInternal != null) {
    return G.isInternal(v);
  } else {
    return isVertex(G, v) && !(isSource(G, v) || isSink(G, v));
  }
};

isIsolated = function(G, v) {
  /*
  Tests whether `v` is a vertex in `G` neither predecessors nor successors.
  */

  if (G.isIsolated != null) {
    return G.isIsolated(v);
  } else {
    return isVertex(G, v) && isSource(G, v) && isSink(G, v);
  }
};

edges = function(G) {
  /* The directed edges of the graph `G` as an array of pairs.*/

  var a, v, w, _i, _j, _len, _len1, _ref, _ref1;
  if (G.edges != null) {
    return G.edges();
  } else {
    a = [];
    _ref = vertices(G);
    for (_i = 0, _len = _ref.length; _i < _len; _i++) {
      v = _ref[_i];
      _ref1 = successors(G, v);
      for (_j = 0, _len1 = _ref1.length; _j < _len1; _j++) {
        w = _ref1[_j];
        a.push([v, w]);
      }
    }
    return a;
  }
};

adjacent = function(G, v) {
  /* All the vertices adjacent to `v` in the graph `G` as an array.*/

  var a, w, _i, _len, _ref;
  if (G.adjacent != null) {
    return G.adjacent(v);
  } else {
    a = predecessors(G, v);
    _ref = successors(G, v);
    for (_i = 0, _len = _ref.length; _i < _len; _i++) {
      w = _ref[_i];
      if (!(a.indexOf(w) >= 0)) {
        a.push(w);
      }
    }
    return a;
  }
};

equals = function(G, H) {
  /*
  Tests whether the graphs `G` and `H` are equal in the sense that they have
  the same sets of vertices and directed edges.
  */

  var eq, v, _i, _len, _ref;
  if (G.equals != null) {
    return G.equals(H);
  } else {
    eq = function(a, b) {
      var i, _i, _ref;
      a = a.slice(0).sort();
      b = b.slice(0).sort();
      if (a.length !== b.length) {
        return false;
      } else {
        for (i = _i = 0, _ref = a.length; 0 <= _ref ? _i < _ref : _i > _ref; i = 0 <= _ref ? ++_i : --_i) {
          if (a[i] !== b[i]) {
            return false;
          }
        }
        return true;
      }
    };
    if (!eq(vertices(G), vertices(H))) {
      return false;
    } else {
      _ref = vertices(G);
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        v = _ref[_i];
        if (!eq(successors(G, v), successors(H, v))) {
          return false;
        }
      }
      return true;
    }
  }
};

module.exports = {
  vertices: vertices,
  predecessors: predecessors,
  successors: successors,
  isVertex: isVertex,
  isSource: isSource,
  isSink: isSink,
  isInternal: isInternal,
  isIsolated: isIsolated,
  isEdge: isEdge,
  edges: edges,
  adjacent: adjacent,
  equals: equals
};