ARCcore.graph Library Documentation
Login
-Home
/
-Documentation
/
-ARCcore
/
-graph
+identifier
-graph
+filter
+discriminator
+types
+util
+DirectedGraph
+Algorithms
Examples
ARCcore.graph Library Documentation
ARCcore.graph library provides an in-memory directed graph database and extensible algorithms based on the visitor pattern.

graph Library Introduction

See also: Mathematical Graph Theory (Wikipedia)

Build Status

"... 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:

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": {}
}'

graph Library Details

DirectedGraph - ARCcore.graph DirectedGraph Class
Developer documentation for ARCcore.graph DirectedGraph container class.
Vertex Methods - ARCcore.graph DirectedGraph vertex methods documentation.
Edge Methods - ARCcore.graph DirectedGraph edge methods documentation.
Container Methods - ARCcore.graph DirectedGraph container methods documentation.
API Objects - ARCcore.graph DirectedGraph API standard parameter objects.
Serialization - ARCcore.graph DirectedGraph serialization & deserialization reference.
Algorithms - ARCcore.graph Algorithms Reference
Developer documentation for ARCcore.graph bundled algorithms.
Digraph Transpose - ARCcore.graph.DirectedGraph transpose tranformation algorithm.
Digraph Breadth-First - ARCcore.graph.DirectedGraph breadth-first visit/search traversal algorithm.
Digraph Depth-First - ARCcore.graph.DirectedGraph depth-first visit/search traversal algorithm.
Digraph Traversals - Initializing and controlling traversal algorithm state.
Examples - ARCcore.graph Library Examples
ARCcore.graph library examples.
Encapsule Project, Seattle WA
Copyright © 2017 Chris Russell
Thu Oct 19 2017 23:03:01 GMT-0400 (EDT)

Encapsule/holism v0.0.26
Documents Under Contruction