graph.js

/*******************************************************************************
 * Copyright (c) 2013 Max Schaefer.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     Max Schaefer - initial API and implementation
 *******************************************************************************/

/* Graphs represented using adjacency sets. */
if(typeof define !== 'function') {
  var define = require('amdefine')(module);
}

define(function(require, exports) {
  var numset = require('./numset');

  function Graph() {
    this.succ = [];
  };
  
  var id2node = Graph.prototype.id2node = [];
  var nextNodeId = 1;
  var nodeId = Graph.prototype.nodeId = function nodeId(nd) {
    var id = nd.attr.hasOwnProperty('node_id') ? nd.attr.node_id 
                                               : (nd.attr.node_id = nextNodeId++);
    id2node[+id] = nd;
    return id;
  };

  Graph.prototype.addEdge = function(from, to) {
    var fromId = nodeId(from), toId = nodeId(to);
    if(fromId === toId)
      return;
    this.succ[fromId] = numset.add(this.succ[fromId], toId);
  };
  
  Graph.prototype.addEdges = function(from, tos) {
    for(var i=0;i<tos.length;++i)
      this.addEdge(from, tos[i]);
  };
  
  Graph.prototype.iter = function(cb) {
    for(var i=0;i<this.succ.length;++i) {
      if(!this.succ[i])
        continue;
      var from = id2node[i];
      numset.iter(this.succ[i], function(succ) {
        cb(from, id2node[succ]);
      });
    }
  };

  Graph.prototype.hasEdge = function(from, to) {
    var fromId = nodeId(from), toId = nodeId(to);
    return numset.contains(this.succ[fromId], toId);    
  }

  exports.Graph = Graph;
  return exports;
});