JavaScript kata for directed acyclic graph data structure
npm install simplegraphsimplegraph
============
Makes a fairly simple graph structure (used to be "simple-graph")
update
------
[19 DEC 2013] ~ v0.1.0 contains several breaking changes ~ if you're using an
earlier version please update.
Thanks to Ferry Boender
-----------------------
...for his post on the
[dependency resolving algorithm]
(http://www.electricmonk.nl/log/2008/08/07/dependency-resolving-algorithm/),
and for his ongoing encouragement in this exploration.
travis
------

testling
--------

rawgit
------
__View the generated test-bundle page on
target='_new' title='opens in new tab or window'>rawgit.__
install
-------
npm install simplegraph
git clone git://github.com/dfkaye/simplegraph.git
use
---
node.js
var simplegraph = require('simplegraph');
browser
window.simplegraph
justify
-------
Everyone should figure out at least one directed acyclic graph data structure in
JavaScript. Here's mine.
I'm using this for learning tests in order to work out dependency-loading trivia
in another project, and re-learning performance optimizations for scaling with
big collections (over 2 million elements in the big-fixture tests).
what makes it simple?
---------------------
There is no concept of a node or external node lookup map. Rather, every
object on a graph is a graph instance whose edges are other graph instances.
Nothing special - perhaps a bit naïve, but traversal is required by several
methods, and making that simple has been a challenge.
structure
---------
A graph contains a map of edges (other graphs) by their id. The required
constructor argument is a string id. The constructor can be called with or
without the new keyword.
var main = simplegraph('main');
var main = new simplegraph('main');
That returns an object with the following fields:
main.id // string 'main'
main.edges // map of graphs {}
These are the only constructor-created properties.
No graph data element is stored in a graph element - __final answer__
traversal
---------
__[20 DEC 2013 ] API/DOC IN PROGRESS__
The traversal API is not ideal, but has the virtue of being testable so far...
Some graph child methods use procedural code (for-loops) rather than iterator
functions in order to support IE6-8 - and to execute faster (iterators run just
under an order of magnitude slower).
The resolve (traversal) methods use visitor iteration methods internally. The
pattern looks like this:
// pass visit function to the visitor method...
var visitor = this.visitor(function visit(edge) {
// process this edge
});
// or define visit directly:
visitor.visit = function (edge) {
// process this edge
};
// define an optional post traversal processing method
visitor.after = function (edge) {
// post-process this edge
};
// run it
this.resolve(visitor);
// inspect it
visitor.results.join('');
// etc.
__resolve(visitor?)__
Any graph object can be resolved independently with the resolve() method. The
resolve() method __optionally__ accepts a visitor object. If one is not
specified, resolve() creates one for use internally from the graph on which
resolve() is first called. The visitor is a collecting parameter which lets
you manage results, terminate processing at specified points, and so on.
__If the resolve() method detects a cycle, it will throw an error.__
If no cycle or other error occurs, resolve() returns a visitor object.
__visitor(fn?)__
Any graph object can create a visitor object. A visitor has an id set to the
creating graph's id, an ids array, visited and visiting maps, a results
array, and a done() method.
The visitor() method can optionally take a visit function argument. The
visit function will run on the current graph being visited before descending
to edges. The function takes a graph param representing a child or edge.
The visitor object is used internally by the resolve() method for tracking
visited subgraphs, and for throwing an error if a cycle is detected.
A fully returned visitor has the following properties:
.id ~ string id of the graph for which visitor is first created
.ids ~ array of graph ids visited
.results ~ collecting parameter array of results
.visited ~ map of ids used internally for cycle detection
.visiting ~ map of ids used internally for cycle detection
.done ~ method that halts further processing or traversals when called
.visit ~ optional iteration function to run when visiting a graph element
.after ~ optional post-processing function to run when a graph's depth
traversal is completed
__visitor examples__
The following snippet from the remove(id) method demonstrates a visitor usage.
It calls detach internally and pushes detached edges to the visitor's results
array:
var visitor = this.visitor(function(edge) {
// uses closure on id param
if (edge.detach(id)) {
// this is the visitor
this.results.push(edge);
}
});
return this.resolve(visitor);
which lets you retrieve the visitor's results array:
var results = remove('something').results;
__visitor.done()__
The following snippet from descendant(id) shows a call to done():
var child = false;
var visitor = this.visitor(function(edge) {
// uses closure on descendant(id) param
var item = edge.edges[id];
if (item) {
child = item;
this.done(); // halt further processing
}
});
this.resolve(visitor);
return child;
__visitor.after = function () {}__
The following snippet from sort() shows how to define an after callback:
var visitor = this.visitor();
visitor.after = function (edge) {
// if the current edge has not been marked as visited yet,
// unshift it to the front of results if it's a leaf,
// otherwise, push it to the end if it has edges
if (!this.visited[edge.id]) {
if (edge.empty()) {
this.results.unshift(edge.id);
} else {
this.results.push(edge.id);
}
}
};
You can define visit as a method directly on a created visitor rather than
passing it as a parameter. The following snippet from the list() method shows
how to define visit, after, and some custom or nonce properties:
var visitor = this.visitor();
// assign nonce properties we can use in visit and after functions
visitor.depth = -1;
visitor.INDENT = 2;
// explicit visit assignment
visitor.visit = function (edge) {
// unset depth after() visiting...
this.depth += this.INDENT;
for (var i = 0; i < this.depth; i++) {
this.results.push(' ');
}
if (edge.empty()) {
this.results.push('-');
} else {
this.results.push('+');
}
this.results.push(' ' + edge.id + '\n');
};
// post-processing aop
// unset depth after() visiting...
visitor.after = function (edge) {
this.depth -= this.INDENT;
};
methods
-------
__attach(graph)__
attach() accepts a graph object as a child in the current graph.
If adding a graph that is __not__ already a child, attach() returns the added
child; else it returns __false__.
var main = simplegraph('main')
var a = simplegraph('a');
main.attach(a);
// => a
main.attach(a); // again
// => false
__detach(id)__
detach() accepts a string id for the child in the current graph.
If a child matching the id is found, detach() returns returns the detached
child; else it returns __false__.
The graph is removed from the child's parents array. The child's root is
set to itself if the parents array is empty.
main.detach('a');
// => a
main.detach('a'); // again
// => false
__empty()__
empty() returns true if a graph has no edges; else returns __false__.
var main = simplegraph('main');
main.empty()
// true
main.attach(a);
// => a
main.empty()
// false
main.detach('a');
// => a
main.empty()
// true
__has(id)__
has() accepts a string id for the target child of a graph. If a child is
found matching the id, the child is returned; else has() returns __false__.
main.attach(a);
// => a
main.has('a')
// a
main.detach('a');
// => a
main.has('a')
// false
__descendant(id)__
descendant() accepts a string id for the target descendant of a graph. If a
descendant is found matching the id, the found target is returned; else
descendant() returns __false__.
// main -> a -> b -> c
main.descendant('c');
// => c
__remove(id)__
remove() accepts a string id for the target as a child in the current graph or
as a descendant within any subgraph.
remove() visits every child and descendant of the current graph. If a
descendant's id matches the given argument, the item is detached from its graph.
remove() returns a visitor with a results array of all __parent__ graphs
from which the target item has been detached. This allows for graph "refreshes"
or migrations as necessary.
// main -> a -> b -> c -> d
// a -> c -> e
var visitor = main.remove('c');
visitor.results
// => ['a', 'b']
__parents(id) - aka 'fan-in'__
parents() accepts a string id for an item in the graph, and finds all graphs
in subgraph that depend on graph with given id. Found graphs are returned in the
visitor.results array.
parents() always returns a visitor object with a visitor.results' array.
subgraph()
// main -> a -> b -> c -> d
// a -> c -> e
var visitor = main.parents('c');
visitor.results
// => ['a', 'b']
__subgraph() - aka 'fan-out'__
traverses a graph's edges and their edges recursively, and returns
visitor.results
all graphs visited in the array. The current graph is __not__
subgraph()
included as a dependency in the subgraph.
always returns a visitor object with a visitor.results' array.
// main -> a -> b
// b -> d
// a -> c -> e
var visitor = main.subgraph();
visitor.results
// => ['a', 'b', 'd', 'c', 'e']
__size()__
size() returns the number of edges under a graph.
// main -> a -> b
// b -> d -> e
// a -> c -> d -> e
// c -> e
main.size();
// => 8 arrows
__list(depth?)__
list() is really a 'just for show' visitor-based method with both
visitor.visit and visitor.after methods - meaning some AOP is creeping into
the resolve() algorithm, so that definitely needs re-visiting (pun - sorry).
list() iterates over a graph and returns a string showing the graph and its
subgraph, indented, something like:
main.list()
// =>
+ main
+ a
+ b
+ c
- d
- e
- d
+ c
- d
- e
+ b
+ c
- d
- e
- d
+ c
- d
- e
sort() uses visitor internally, and returns an array of ids found from the
sort() on any graph element to retrieve the topo-sort for that element's
big-fixture-test generates over 2 million graph items (currently
tape module and its dependencies
dom-console.js shim that outputs console
console.log().
load method that runs attachment on
indexOf
has() method
new inside big fixture reduces time
empty() method to replace the for-in fakeoutsrequire'd graph function to simplegraphdependants() (items that depend on certain node) as parentsroot and parent support - gad, what a mistakeroot field so we can sort() from the top by default