Simian Simple Graph

This is a pretty basic DAG structure I cooked up for a particular project (and later expanded on). You are provided two constructors, Graph and Edge. Both Graph and Edge are immutable. Graph contains an immutable set of Edge objects. Edge contains two strings, from and to. The nodes in the graph are always strings, which lets us simplify caching results of various operations. To associate more data with a node, you can either keep data for each node in a Map, or have each node-item have an id, which is what you will store in the Graph.

There are a handful of common Graph operations implemented as static methods on the Graph class, and hopefully those will be enough to enable more advanced use.

Note that children / edges of a node are not stored in order (because we use a Set internally). This would normally preclude inorder / preorder / postorder traversal of the tree. However, our two tree walking functions (Graph.depthFirst() and Graph.breadthFirst()) let you supply sort functions which can enable such ordered traversal.

Please feel free to log bugs / feature-requests in github. Docs can be generated by checking out the repo and running npm run doc, followed by opening docs/index.html.

Installation

npm i --save simian-simple-graph

Usage

import * as SSG from 'simian-simple-graph';

const {
  Graph,
  Edge
} = SSG;

const g0 = new Graph([
  new Edge('a', 'b'), // a -> b
  new Edge('a', 'c'), // a -> c
  new Edge('a', 'd'), // a -> d
  new Edge('d', 'e'), // d -> e
  new Edge('d', 'f'), // d -> f
]);

const g1 = Graph.getSubTree(g0, 'd'); // d -> e, d -> f