PersistentGraph.js

// Generated by CoffeeScript 1.6.3
/*

An implementation of simple, directed graphs as a [persistent data
structure](http://en.wikipedia.org/wiki/Persistent_data_structure).

For our purposes, a directed graph consists of a set of vertices and a
collection of ordered vertex pairs, called the edges of the graph. Vertices
can be of any type, including mixed types within the same graph, but must be
immutable.

This implementation is restricted to simple graphs, meaning that no vertex
pair can occur more than once as an edge, and there are no *loops* (edges that
start and end in the same vertex). It is, however, possible to have an edge,
say `[v, w]`, as well as its reverse, `[w, v]`.

Persistence means in essence that instances of this class are immutable and
any methods that create modifications of existing graphs will return new,
independent objects which may share some common data with the originals.


This module exports as a factory function which can be called to create new
directed graphs. The first argument must be an array of directed edges, given
as vertex pairs. The optional second argument must be an array of vertices and
can be used when creating graphs with some isolated vertices.

Usage example:

    makeGraph = require('./PersistentGraph')
    G = makeGraph([[1,2],[1,3],[2,4],[3,4]], [5])
    console.log(G.predecessors(4))
    # -> [2, 3]
    console.log(G.adjacent(5))
    # -> []
*/

var PersistentGraph, _;

_ = require('mori');

PersistentGraph = (function() {
  /*
  
  The Implementation class. This class is not exported. Instead, the
  containing module exports as a factory function which can be called to
  create new instances. In addition, there are instance methods
  `withVertices`, `withEdges`, `withoutVertices` and `withoutEdges` for
  creating modifications of existing graph instances.
  
  A graph is represented redundantly as a set of vertices and two maps for the
  sets of predecessors and successors of vertices. We store this data in
  persistent data structures borrowed from ClojureScript via the
  [Mori](https://github.com/swannodette/mori) library by David Nolen
  (@swannodette).
  
  When Mori data structures are used as vertices, their equality is determined
  structurally. In other words, two Mori collections with the same contents
  and order are considered equal even if the representing objects are
  distinct. This is not the case for plain Javascript objects.
  */

  function PersistentGraph(_verts, _pred, _succ) {
    this._verts = _verts;
    this._pred = _pred;
    this._succ = _succ;
    /*
    This low-level constructor should not be called directly (see above).
    */

  }

  PersistentGraph.prototype.vertices = function() {
    /* The vertices of this graph as an array.*/

    return _.into_array(this._verts);
  };

  PersistentGraph.prototype.predecessors = function(v) {
    /* The immediate predecessors of the given vertex as an array.*/

    return _.into_array(_.get(this._pred, v));
  };

  PersistentGraph.prototype.successors = function(v) {
    /* The immediate successors of the given vertex as an array.*/

    return _.into_array(_.get(this._succ, v));
  };

  PersistentGraph.prototype.isVertex = function(v) {
    /* Tests whether the given object is a vertex of this graph.*/

    return _.has_key(this._verts, v);
  };

  PersistentGraph.prototype.isEdge = function(v, w) {
    /* Tests whether the given pair forms a directed edge of this graph.*/

    return _.has_key(_.get(this._succ, v), w);
  };

  PersistentGraph.prototype.isSource = function(v) {
    /* Tests whether the given object is a vertex with no predecessors.*/

    return this.isVertex(v) && _.seq(_.get(this._pred, v)) === null;
  };

  PersistentGraph.prototype.isSink = function(v) {
    /* Tests whether the given object is a vertex with no successors.*/

    return this.isVertex(v) && _.seq(_.get(this._succ, v)) === null;
  };

  PersistentGraph.prototype.edges = function() {
    /* The directed edges of this graph as an array of pairs.*/

    var outgoing,
      _this = this;
    outgoing = function(v) {
      return _.map(_.vector, _.repeat(v), _.get(_this._succ, v));
    };
    return _.into_array(_.map(_.into_array, _.mapcat(outgoing, this._verts)));
  };

  PersistentGraph.prototype.adjacent = function(v) {
    /* All the vertices adjacent to the given one as an array.*/

    return _.into_array(_.union(_.get(this._pred, v), _.get(this._succ, v)));
  };

  PersistentGraph.prototype.equals = function(other) {
    /*
    Tests whether this graph is equal to the given one in the sense that the
    two graphs have the same sets of vertices and directed edges.
    */

    var v, _i, _len, _ref;
    if (!_.equals(this.vertices(), other.vertices())) {
      false;
    } else {
      _ref = this.vertices();
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        v = _ref[_i];
        if (!_.equals(this.predecessors(v), other.predecessors(v))) {
          return false;
        }
      }
    }
    return true;
  };

  PersistentGraph.prototype.toJSON = function() {
    /*
    
    Produces a representation of this graph as an object with properties
    `"vertices"` and `"edges"` suitable for serialisation via JSON.
    
    When using this function to serialize and later recreate a graph, please
    note that any Mori collections used as vertices will be converted to
    corresponding plain Javascript objects or arrays on output. The functions
    and methods that create graph instances, on the other hand, do not perform
    the opposite conversion.
    */

    var edges, outgoing,
      _this = this;
    outgoing = function(v) {
      return _.map(_.vector, _.repeat(v), _.get(_this._succ, v));
    };
    edges = _.mapcat(outgoing, this._verts);
    return {
      'vertices': _.clj_to_js(_.sort(this._verts)),
      'edges': _.clj_to_js(_.sort(edges))
    };
  };

  PersistentGraph.prototype.withVertices = function(vs) {
    /*
    Creates a modification of this graph with some vertices added. The
    argument must be an array containing the new vertices. Vertices already
    present in the graph are silently ignored.
    */

    var add, addOne;
    vs = _.set(vs);
    addOne = function(m, v) {
      if (_.has_key(m, v)) {
        return m;
      } else {
        return _.assoc(m, v, _.set());
      }
    };
    add = function(m, vs) {
      return _.reduce(addOne, m, vs);
    };
    return new PersistentGraph(_.union(this._verts, vs), add(this._pred, vs), add(this._succ, vs));
  };

  PersistentGraph.prototype.withoutVertices = function(vs) {
    /*
    Creates a modification of this graph with some vertices, together with all
    their incident edges, removed. The argument must be an array containing
    the vertices to be removes. Vertices not present in the graph are silently
    ignored.
    */

    var purge;
    vs = _.set(vs);
    purge = function(m, vs) {
      var clean, keys, seen;
      seen = _.partial(_.has_key, vs);
      clean = function(m, w) {
        return _.assoc(m, w, _.set(_.remove(seen, _.get(m, w))));
      };
      keys = _.map(_.first, _.seq(m));
      return _.reduce(_.dissoc, _.reduce(clean, m, keys), vs);
    };
    return new PersistentGraph(_.difference(this._verts, vs), purge(this._pred, vs), purge(this._succ, vs));
  };

  PersistentGraph.prototype.withEdges = function(es) {
    /*
    Creates a modification of this graph with some directed edges added. The
    argument must be an array containing the new edges as vertex pairs. Edges
    already present in the graph, as well as pairs of the form `[v,v]`, are
    silently ignored.
    */

    var conjIn, withEdge;
    conjIn = function(m, k, v) {
      return _.assoc(m, k, _.conj(_.get(m, k), v));
    };
    withEdge = function(G, _arg) {
      var G1, v, w;
      v = _arg[0], w = _arg[1];
      if (_.equals(v, w) || G.isEdge(v, w)) {
        return G;
      } else {
        G1 = G.withVertices([v, w]);
        return new PersistentGraph(G1._verts, conjIn(G1._pred, w, v), conjIn(G1._succ, v, w));
      }
    };
    return _.reduce(withEdge, this, es);
  };

  PersistentGraph.prototype.withoutEdges = function(es) {
    /*
    Creates a modification of this graph with some directed edges removed. The
    argument must be an array containing the edges to be removed as vertex
    pairs. Edges not present in this graph are silently ignored.
    */

    var disjIn, withoutEdge;
    disjIn = function(m, k, v) {
      return _.assoc(m, k, _.disj(_.get(m, k), v));
    };
    withoutEdge = function(G, _arg) {
      var v, w;
      v = _arg[0], w = _arg[1];
      if (!G.isEdge(v, w)) {
        return G;
      } else {
        return new PersistentGraph(G._verts, disjIn(G._pred, w, v), disjIn(G._succ, v, w));
      }
    };
    return _.reduce(withoutEdge, this, es);
  };

  return PersistentGraph;

})();

module.exports = function(es, vs) {
  var g;
  if (vs == null) {
    vs = [];
  }
  /* The factory function this module exports (see above).*/

  g = new PersistentGraph(_.set(), _.hash_map(), _.hash_map());
  return g.withEdges(es).withVertices(vs);
};