See also: Mathematical Graph Theory (Wikipedia)

"... At the other end of the spectrum is, for example, graph theory, where the basic object, a graph, can be immediately comprehended. One will not get anywhere in graph theory by sitting in an armchair and trying to understand graphs better. Neither is it particularly necessary to read much of the literature before tackling a problem: it is of course helpful to be aware of some of the most important techniques, but the interesting problems tend to be open precisely because the established techniques cannot easily be applied." - W.T. Gowers

ARCcore.graph is a JavaScript library for storing and processing in-memory directed graph data sets inspired by Jeremy Siek's work on the Boost C++ Graph Library (BGL). The library is not a complete port of the BGL to JavaScript. Rather, the library implements a small but useful subset of the vast functionality provided by the BGL. ARCcore.graph specifically provides:

• DirectedGraph container class:
  • Vertex and edge add, remove, enumerate, and existence testing.
  • Vertex and edge properties add, remove, and existence testing.
  • JSON serialization and de-serialization of the container.
• Algorithms:
  • Directed graph transpose algorithm.
  • Non-recursive visitor pattern implementation of breadth-first visit and search algorithms with edge classification.
  • Non-recursive visitor pattern implementation of depth-first visit and search algorithm with edge classification.

Packaging

ARCcore.graph is part of the ARCcore package. Primarily, this helps reduce testing overhead.

For those wishing to use ARCcore.graph without taking a dependency on ARCcore, this library is distributed as a stand-alone npm package called jsgraph.

ARCcore.graph Exports

$ node
> const arccore = require('arccore')
undefined
> arccore.graph
{ directed:
   { create: [Function: a],
     transpose: [Function],
     breadthFirstTraverse: [Function],
     depthFirstTraverse: [Function],
     colors: { white: 0, gray: 1, black: 2 },
     createTraversalContext: [Function] } }
>

DirectedGraph Container Class

See also: DirectedGraph

Here's a dump of DirectedGraph class methods so you can get an idea of what the container provides:

$ node
> const arccore = require('arccore');
undefined
> var digraph = arccore.graph.directed.create().result;
undefined
> digraph
DirectedGraph {
  getGraphName: [Function],
  setGraphName: [Function],
  getGraphDescription: [Function],
  setGraphDescription: [Function],
  isVertex: [Function],
  addVertex: [Function],
  removeVertex: [Function],
  getVertexProperty: [Function],
  setVertexProperty: [Function],
  hasVertexProperty: [Function],
  clearVertexProperty: [Function],
  inDegree: [Function],
  inEdges: [Function],
  outDegree: [Function],
  outEdges: [Function],
  isEdge: [Function],
  addEdge: [Function],
  removeEdge: [Function],
  getEdgeProperty: [Function],
  setEdgeProperty: [Function],
  hasEdgeProperty: [Function],
  clearEdgeProperty: [Function],
  verticesCount: [Function],
  getVertices: [Function],
  edgesCount: [Function],
  getEdges: [Function],
  rootVerticesCount: [Function],
  getRootVertices: [Function],
  leafVerticesCount: [Function],
  getLeafVertices: [Function],
  toJSON: [Function],
  toObject: [Function],
  stringify: [Function],
  fromObject: [Function],
  fromJSON: [Function],
  _private:
   { name: '',
     description: '',
     vertexMap: {},
     rootMap: {},
     leafMap: {},
     edgeCount: 0,
     constructionError: null } }
>

Use Cases

ARCcore.graph is a data structure and algorithms library for storing, analyzing, serializing, and de-serializing complex run-time data, metadata, and relationships that can be used in Node.js and browser client code. If you're looking for a graph visualization library, start here.

Use of the DirectedGraph container in derived code provides the following benefits:

• Simple, normalized API makes your code more readable. And, simplifies debugging and test tasks.
• Passing DirectedGraph container instances by reference (or by JSON) allows you to change the structure of your data without breaking API contracts.
• Avoids the hassle of serializing and de-serializing cyclic data structures linked by reference.
• Normalized container API provides the basis for re-usable algorithms that save significant time vs. writing and testing your own traversal algorithms from scratch.

Short Example

The following short example constructs a DirectedGraph container, and leverages the breadthFirstTraverse algorithm to calculate the depth of each vertex which is assigned to each vertex's property. After running the algorithm, the container contents is serialized showing the depth of each vertex as the vertex property value p.

// bft-vertex-ranking.js
const graph = require('arccore').graph;
var response = graph.directed.create({
    elist: [
        { e: { u: "A", v: "B" } },
        { e: { u: "B", v: "C" } },
        { e: { u: "B", v: "D" } }
    ]
});


// Check the response object for error!
if (response.error)
    throw new Error(response.error);


// No error; de-reference the new container.
var digraph = response.result;
// THINK OF VISITOR INTERFACES LIKE ALGORITHM FLIGHT RECORDERS
// VERTEX RANKING ALGORITHM (breadthFirstTraverse visitor interface)
var bftVisitorInterface = {
    startVertex: function(request) {
        request.g.setVertexProperty({ u: request.u, p: 0});
        return true; // continue the traversal
    },
    treeEdge: function (request) {
        request.g.setVertexProperty({
            u: request.e.v,
            p: request.g.getVertexProperty(request.e.u) + 1
        });
        return true;
    }
};


// ACTUATE OUR VISITOR INTERFACE WITH BFT TO PRODUCE THE RESULT
response = graph.directed.breadthFirstTraverse({
    digraph: digraph,
    visitor: bftVisitorInterface
});
if (response.error) {
    throw new Error(response.error);
}


console.log("DirectedGraph: '" + digraph.stringify(undefined,4) + "'");
console.log("BFT traversal: '" + JSON.stringify(response.result,undefined,4) + "'");

... produces the following output with each vertex's property value set to its rank (edge hops away from a root vertex in this example).

DirectedGraph: '{
    "vlist": [
        {
            "u": "A",
            "p": 0
        },
        {
            "u": "B",
            "p": 1
        },
        {
            "u": "C",
            "p": 2
        },
        {
            "u": "D",
            "p": 2
        }
    ],
    "elist": [
        {
            "e": {
                "u": "A",
                "v": "B"
            }
        },
        {
            "e": {
                "u": "B",
                "v": "C"
            }
        },
        {
            "e": {
                "u": "B",
                "v": "D"
            }
        }
    ]
}'
BFT traversal: '{
    "searchStatus": "completed",
    "colorMap": {
        "A": 2,
        "B": 2,
        "C": 2,
        "D": 2
    },
    "undiscoveredMap": {}
}'