encapsule-annex / jsgraph

Deprecated: Use the @encapsule/arccore package that includes the graph library

Encapsule Project: GitHub / Twitter

Exploration of declarative programming with data models and graph theory using JavaScript, Node.js, and HTML5.

Encapsule/jsgraph v0.7.1

"Begin at the beginning," the King said very gravely. "and go on till you come to the end: then stop." - Lewis Carroll, Alice in Wonderland

See also: Mathematical Graph Theory

NEW DOCS for the v0.7.1 release: ARCcore.graph

About

This is a data modeling and algorithms library. It does not draw graphs in your browser!

Encapsule/jsgraph (aka 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 but does provide a very useful subset its functionality that is useful for building data-driven JavaScript applications.

Briefly, jsgraph library provides:

• DirectedGraph container class:
  • Vertex and edge add, remove, enumerate, and existence testing. And, vertex and edge-associated property maps.
  • JSON serialization and deserialization 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

Encapsule/jsgraph is a stand-alone JavaScript library that may be used directly in Node.js applications. Or in the browser via webpack.

The library is also distributed as part of the Encapsule/ARCcore package that contains a number of other libraries for modeling and processing complex in-memory data in JavaScript applications that some of you may find interesting and useful.

Contributing

This library is used in production applications. And, in ridiculous derived science projects. So, the bar is pretty high for taking changes (particularly breaking changes). And, PR's need to come with tests! Exceptions made on a case-by-case basis for nice people and important projects with wide benefit.

Release Notes

v0.7.1 is a maintenance release

• Encapsule/jsgraph sources are now officially part of the Encapsule/ARCcore package.
• Travis CI updated for Node.js v6.10.x LTS and v7.9.0 current releases. Older builds dropped.
• Fixed a single test break caused by latest Node.js increasing verbosity of JSON parse error to include character position of failure.
• Documentation has been revised and is now available on the Encapsule Project website: ARCcore.graph.

v0.7 is a breaking API change and documentation release

• Added new method DirectedGraph.stringify
• Changed method semantics of DirectedGraph.toJSON to return a serializable object instead of a JSON-encoded string.
• Alias method DirectedGraph.toObject to call DirectedGraph.toJSON. The toObject method is now deprecated and will be removed in a future release.
• Updated documentation:
  • Per above breaking changes to the DirectedGraph serialization API.
  • Added additional information on set/get of DirectedGraph name and description properties.

v0.6 is a bug fix release that's API-compatible with v0.5

• DFT algorithm bug fixes impacting order and identity of client visitor callbacks.
• Better error handling on bad developer-supplied visitor interfaces.
• Better error handling for BFT/DFT algorithm empty start vector case.
• You can now set name and description string properties on a DirectedGraph:

v0.5 is a breaking upgrade for users of v0.4

• Stylistic changes are required to v0.4 clients to upgrade.
• No more exceptions. jsgraph now returns error/result response objects.
• Breadth-first * algorithms coalesced into breadthFirstTraverse.
• Depth-first * algorithms coalesced into depthFirstTraverse.
• Algorithms now support early terminate under client control.
• ~400 new tests added for v0.5 release.
• Documentation and example updates.

---

Copyright © 2014-2017 Christopher D. Russell

jsgraph's Issues

v0.4 JSON serialization format is too verbose

Too many characters. This should be as compact as possible: use single character property names in JSON.

DFT visitor callback order bugs

• treeEdge should not fire before discoverVertex for the edge's target vertex
• finishEdge callback is not implemented

Noticed some inconsistencies while writing a new DTF-derived visitor algorithm for JBUS vs. my recollection of how the BGL implementation works. Go through this carefully and review.

DirectedGraph API tests don't provide sufficient bad input test coverage

Just refactored in-parameter validation inside of DirectedGraph methods and note that although there should have been some breaks due to changing error messages on bad input to these methods there were no breaks whatsoever.

Release latest jsgraph w/fix to DirectedGraph.toJSON

There's a more recent version of jsgraph that's integrated in the Encapsule/ARCcore package (https://github.com/Encapsule/ARCcore). The latest includes a bug fix to DirectedGraph.toJSON which you'll note returns a string, not an object as it should.

If you need this, drop me a note and I'll get the patch applied here.

Traveral algorithms (breadth & depth-first visit/search) should return context object

Useful for diagnosing the behavior of invoked visitors. And, for advanced applications involving multiple searches performed using a shared traversal context (aka color map and other ancillary metadata).

Methods that return edges don't include properties

If I create a digraph with edges like

var digraph = new DirectedGraph()
digraph.addEdge({ e: { u: 'a', v: 'b' }, p: {/* some other stuff */} })

Methods like getEdges() or outEdges(nodeId) return simply Array<{ u: string, v: string }> and I'm unable to access {/* some other stuff */}.

Is it possible to access that data in the current API?

Need a way to obtain root and leaf vertex count w/out obtaining the list

... working to ensure that there's a reasonable way for client code to always get what they need out of a DirectedGraph container without actually touching the object's private state. Currently, if you want to know the size of either the root or leaf vertex set, you need to request that the set be constructed via a call to DirectedGraph.getLeafVertices/getRootVertices and then take the length of the array. That's just a waste when I just need the count. No need to allocate a new array and then throw it away just to xfer the count.

Add container-scope methods:

• DirectedGraph.leafVerticesCount()
• Directedgraph.rootVerticesCount()

Document graph name/description use

Document methods DirectedGraph.getGraphName, setGraphName, getGraphDescription, setGraphDescription. Also update the JSON import/export docs with these properties.

All API methods switch to single descriptor object in-parameter

... discrete parameters suck. Switch all exposed API functions to request/response-style API that accept a single, descriptor object as input and produce a response descriptor { error: string result: variant }.

+digraph raw serialization object

It's sometimes necessary to serialize a digraph (and deserialize a serialized digraph) directly from the JavaScript object produced internally by digraph.toJSON. Make this internal object accessible to client code via new methods, constructor re-work etc.

Eliminate the use of thrown Error objects

... switch to request/response-style API.

Empty start vector error message

For breadth and depth-first traversal, default behavior is to call DirectedGraph.getRootVertices to obtain the start vertex set. Depending on graph topology, this set might be empty resulting in a v0.5.14 errors message:

'''jsgraph.directed.depthFirstTraverse algorithm failure: You have specified an empty starting vertex set for this traversal. This is allowed only if you set request.options.allowEmptyStartVector === true.'''

True, but not really enough to infer back root cause if you happen to dislike reading documentation, forget, or whatever.

Ideas:

We can track if we are taking default behavior or caller override (DirectedGraph.getRootVertices vs. client-provided start vertex set) and make the error message more descriptive:

Set 'request.options.allowEmptyStartVector true or provide a graph that has one or more root vertices, or specify your own start vertex set`

Make arccore.graph.directed.create accept a DirectedGraph instance by reference

... as a means to clone the DirectedGraph instance.

'vertices' global leak in digraph.js

Caught while working on jbus.

Breadth/depth algorithms should fail if no starting vertex set is specified

... can be overridden w/request.options.allowEmptyStartVector Boolean flag set true

Document how to clone a DirectedGraph

Add documentation about how to clone a DirectedGraph instance (because it's not necessarily obvious).

Currently, the best way is as follows:

const arccore = require("@encapsule/arccore");
var response = arccore.graph.directed.create({ name: "Source Graph" });
if (response.error) throw new Error(response.error);
var sourceDigraph = response.result;

// Clone sourceDigraph
response = arccore.graph.directed.create(sourceDigraph.toJSON());
if (response.error) throw new Error(response.error);
var clonedDigraph = response.result;

DirectedGraph private state should be clearly partitioned

... to help developers understand the separation of concerns, and the importance of always using the public API and never taking a dependency on the details of how DirectedGraph stores its internal state.

Change export/import JSON outer container object...

... format to use jbus-style CIDS IRUT identifier (meaningless to everyone else at this point but also harmless).

Add the ability to pass a context reference through to visitor interface callbacks...

Developers are currently forced to manage any context their visitor interfaces require above and beyond the context provided by the request object passed to each callback by the algorithm. Typically, developers leverage a JavaScript closure scope and define their visitor object and invocation of the jsgraph algorithm in that scope.

For example, it is typical that visitor interface function implementations record information that is required in part or in whole to produce the result of the operation. Currently, it is assumed that developers will take care of this detail on their own.

cycleEdges = [];
var dftVisitor = {
    forwardOrCrossEdge: function(request) {
        cyclesEdges.push(request.e); // record the edge
        // What I want is rather: request.context.cyclesEdges.push(request.e);
       return true; // continue the traversal
    }
};
var response = jsgraph.directed.depthFirstTraverse({ digraph: digraph, visitor: dftVisitor });
if (response.error) {
    throw new Error(response.error); // e.g.
}
if (cycleEdges.length) {
    console.log("Digraph contains cycles on the following edges: " + JSON.stringify(cycleEdges) );
}

'''

However, in more advanced scenarios it would be helpful to have a standard way to direct visitor interfaces to a specific sandbox for keeping track of intermediate state and building results.

Make it possible to pass a context reference via traversal algorithm request object that gets passed to visitor callbacks. This will allow the algorithm caller far more flexibility and control than is now convenient.

DFT visitor failing to return Boolean error message...

jsgraph.directed.depthFirstTraverse algorithm failure: BFS visitor.backEdge returned type '[object Number]' instead of expected '[object Boolean]'.

The routine that checks the return type of all visitor interface callback functions is a shared code path now. No need for an algorithm-specific string in the error message: the context is provided when the caller notices the error and adds the outer context to the error.

Drop BFS out above, reset expected results in tests.

Can this lib be used for the sequential graph coloring algorithm implemented by boost::graph?

This is more of a question than an issue, but does this lib port that functionality as well?

createBF*/DF*Context export cut API?

The createDepthFirstSearchContext and createBreadthFirstSearchContext are poorly documented and may not need to be exposed at all to 95% of likely jsgraph library users. Action:

• Take a look at DFS implementation. Why does it inconsistently appear to manage its own context? Does this imply the need to expose context (aka the color map) externally only in the case of BFS?

I smell a rat. Budget a couple hours to encapsulate the color map in all standard cases (i.e. calling the search algorithm will internally allocate and initialize whatever colormap it needs on your behalf and you don't need to worry about it). update tests and docs.

Vertex/edge property should be return copy not reference

Will add more detail here later. See discussion in #53

Normalize digraph edge method signatures

A suggestion from @aembke is to make all digraph.Edge methods that currently accept discrete in-parameter vertex identifier strings for the u and v vertices instead accept a single edge descriptor object (i.e. {u: 'dfsdf', v: 'sdfsdfs'}) as is returned by the digraph.get*Edges methods. This is reasonable: I don't like discrete parameters anyway (but plan only this small change for 0.5 with more sweeping API switch to full request/response API in a later release).

jsgraph.directed.create request enhancements

Add public member variables DirectedGraph.name and DirectedGraph.description and include their values in exported data. Optionally accept name/description values as input in serialized data (on construction or via DirectedGraph.fromObject/fromJSON methods.

Convert jsgraph.directed.create to accept either a raw JSON string, raw data export object, or request object containing all optional name/description/data props.

No way to clear vertex or edge properties back to undefined state...

... without reaching into DirectedGraph's private state and deleting the hash table row.

Add the following methods to DirectedGraph, test, and document.

• DirectedGraph.hasVertexProperty
• DirectedGraph.clearVertexProperty
• DirectedGraph.hasEdgeProperty
• DirectedGraph.clearEdgeProperty

Import/Export

It'd be nice to have import and export functions on a graph instance. I'd imagine this would just be stringified json of a wrapper around the vertexMap, rootMap, leafMap, and edgeCount, but maybe not.

Update copyright and file headers