encapsule-annex / jsgraph Goto Github PK

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`

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.

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).

... switch to request/response-style 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.

... 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()

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

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.

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.

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?

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.

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).

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

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

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

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

... 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 }.

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.

• 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.

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

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

Caught while working on jbus.

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

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;

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.

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.

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