TheDAG
What is it ?
A well-tested data structure to represent data as Directed Unweighted ( for now) Graphs.
Why not call it TheDUG then ?
Because its aimed for use cases where the graph is acyclic.
Adding weights support to edges and the corresponding traversal and utility methods is something I will add when I need it or when someone is kind enough to submit a PR for it.
Installation
yarn add the-dag
Or from unpkg :
Full API documentation
Usage
Instantiate a DAG
constructor
const TheDAG = ;const aDAG = ; // You can optionally pass in your own state read/writer
Create a simple graph
addNodes & addEdges ( simple )
aDAG;aDAG;
Destroy graph
destroy
aDAG;const nodeIDs = Object;// expect(nodeIDs.length).toBe(0);const edgeIDs = Object;// expect(edgeIDs.length).toBe(0);
Create aCyclic graph
addNodes & addEdges
aDAG; aDAG;
Get distance from one node to another
getDistanceTo
/* Get distance or number of hops required to go from one node to another */const distanceFromNodeOneToNodeTwo = aDAG; // expect(distanceFromNodeOneToNodeTwo).toBe(2);
API
API Usage Demo
/* import graph from any different format */const inputGraphWithDifferentFormat = nodes: 1 2 3 4 5 edges: source: 1 target: 2 source: 2 target: 3 source: 2 target: 4 ;const graphReducers = node edgesource edgetarget;aDAG;; aDAG; /* Get edge by source and target ids */const edgeFromOneToThree = aDAG;; /* Get edge by source and target nodes */const edgeFromOneToThreeUsingNodes = aDAG;; /* Get all DAG edges */const allDAGEdges = aDAG;; /* Get all DAG nodes */const allDAGNodes = aDAG;; /* Check if node exists */;; /* Get edge ID */;; /* Get node by id */const nodeOne = aDAG;; /* Get nodes by relative distance */const nodesTwoHopsAway = aDAG;; /* Check for acyclicity and get topologically sorted array */const isAcyclic topologicallySortedNodeIDs = aDAG;; /* Traverse the graph breadth first synchronously */const visitNode = jest;const syncTraversalResult = aDAG;;; /* Traverse the graph breadth first using generators */const nodeIterator = aDAG;let currentNode = nodeIteratornext;let orderedNodes = ;while !currentNodedone orderedNodes; currentNode = nodeIteratornext;;
Read tests and snapshots for more usage information.
Development
git clone https://github.com/rakannimer/the-dagcd the-dag && yarn installyarn test ## To make sure everything is setup correctly