Graph

Graph implemented as a modified incidence list. O(1) for every typical operation except removeNode() at O(E) where E is the number of edges.

Overview example:

var graph = new Graph;
graph.addNode('A'); // => a node object. For more info, log the output or check
                    // the documentation for addNode
graph.addNode('B');
graph.addNode('C');
graph.addEdge('A', 'C'); // => an edge object
graph.addEdge('A', 'B');
graph.getEdge('B', 'A'); // => undefined. Directed edge!
graph.getEdge('A', 'B'); // => the edge object previously added
graph.getEdge('A', 'B').weight = 2 // weight is the only built-in handy property
                                   // of an edge object. Feel free to attach
                                   // other properties
graph.getInEdgesOf('B'); // => array of edge objects, in this case only one;
                         // connecting A to B
graph.getOutEdgesOf('A'); // => array of edge objects, one to B and one to C
graph.getAllEdgesOf('A'); // => all the in and out edges. Edge directed toward
                          // the node itself are only counted once
forEachNode(function(nodeObject) {
  console.log(node);
});
forEachEdge(function(edgeObject) {
  console.log(edgeObject);
});
graph.removeNode('C'); // => 'C'. The edge between A and C also removed
graph.removeEdge('A', 'B'); // => the edge object removed

Properties:

• nodeSize: total number of nodes.
• edgeSize: total number of edges.

Instance Methods

constructor()

addNode(id)

The id is a unique identifier for the node, and should not change after it's added. It will be used for adding, retrieving and deleting related edges too.

Note that, internally, the ids are kept in an object. JavaScript's object hashes the id '2' and 2 to the same key, so please stick to a simple id data type such as number or string.

Returns: the node object. Feel free to attach additional custom properties on it for graph algorithms' needs. Undefined if node id already exists, as to avoid accidental overrides.

getNode(id)

Returns: the node object. Feel free to attach additional custom properties on it for graph algorithms' needs.

removeNode(id)

Returns: the node object removed, or undefined if it didn't exist in the first place.

addEdge(fromId, toId, weight)

fromId and toId are the node id specified when it was created using addNode(). weight is optional and defaults to 1. Ignoring it effectively makes this an unweighted graph. Under the hood, weight is just a normal property of the edge object.

Returns: the edge object created. Feel free to attach additional custom properties on it for graph algorithms' needs. Or undefined if the nodes of id fromId or toId aren't found, or if an edge already exists between the two nodes.

getEdge(fromId, toId)

Returns: the edge object, or undefined if the nodes of id fromId or toId aren't found.

removeEdge(fromId, toId)

Returns: the edge object removed, or undefined of edge wasn't found.

getInEdgesOf(nodeId)

Returns: an array of edge objects that are directed toward the node, or empty array if no such edge or node exists.

getOutEdgesOf(nodeId)

Returns: an array of edge objects that go out of the node, or empty array if no such edge or node exists.

getAllEdgesOf(nodeId)

Note: not the same as concatenating getInEdgesOf() and getOutEdgesOf(). Some nodes might have an edge pointing toward itself. This method solves that duplication.

Returns: an array of edge objects linked to the node, no matter if they're outgoing or coming. Duplicate edge created by self-pointing nodes are removed. Only one copy stays. Empty array if node has no edge.

forEachNode(operation)

Traverse through the graph in an arbitrary manner, visiting each node once. Pass a function of the form fn(nodeObject, nodeId).

Returns: undefined.

forEachEdge(operation)

Traverse through the graph in an arbitrary manner, visiting each edge once. Pass a function of the form fn(edgeObject).

Returns: undefined.