dag-map

What is dag-map?

The dag-map npm package provides a data structure for managing directed acyclic graphs (DAGs). It allows you to add nodes and edges, check for cycles, and perform topological sorting. This is useful for scenarios where you need to manage dependencies or represent hierarchical relationships.

What are dag-map's main functionalities?

Add Nodes and Edges

This feature allows you to add nodes and edges to the DAG. In the example, nodes 'a', 'b', and 'c' are added, and edges are created from 'a' to 'b' and from 'b' to 'c'.

const DAGMap = require('dag-map');
const dag = new DAGMap();
dag.add('a');
dag.add('b');
dag.add('c');
dag.addEdge('a', 'b');
dag.addEdge('b', 'c');

Check for Cycles

This feature allows you to check if the DAG contains any cycles. In the example, a cycle is created by adding an edge from 'b' back to 'a', and the `hasCycle` method returns true.

const DAGMap = require('dag-map');
const dag = new DAGMap();
dag.add('a');
dag.add('b');
dag.addEdge('a', 'b');
dag.addEdge('b', 'a');
console.log(dag.hasCycle()); // true

Topological Sorting

This feature allows you to perform a topological sort on the DAG. In the example, the nodes are sorted in topological order, resulting in the array ['a', 'b', 'c'].

const DAGMap = require('dag-map');
const dag = new DAGMap();
dag.add('a');
dag.add('b');
dag.add('c');
dag.addEdge('a', 'b');
dag.addEdge('b', 'c');
console.log(dag.topsort()); // ['a', 'b', 'c']

Other packages similar to dag-map

graphlib

Graphlib is a library for creating and manipulating directed and undirected graphs. It provides more extensive graph manipulation capabilities compared to dag-map, including algorithms for finding shortest paths, detecting cycles, and more.

js-graph-algorithms

js-graph-algorithms is a library that implements various graph algorithms, including those for directed acyclic graphs. It offers a broader range of algorithms and data structures for graph manipulation compared to dag-map.

graph-data-structure

graph-data-structure is a simple library for creating and manipulating graphs. It supports both directed and undirected graphs and provides basic functionalities like adding nodes and edges, checking for cycles, and finding paths.

README

dag-map

A directed acyclic graph library for JavaScript.

In addition to being a DAG implmentation, it also provides value storage on the vertices. So in-short, it is a key/value DAG.

Downloads

API

  // create a new draph;
  var graph = new DAG();

  // add some nodes
  graph.add('foo');
  graph.add('bar');
  graph.add('baz');

  // currently, no edges exist between these nodes, so lets add some

  graph.addEdge('foo', 'bar');

  // we now have an edge from 'foo' -> 'bar';

  graph.addEdge('bar', 'baz');

  // we now have an edge from 'foo' -> 'bar' -> 'baz';

  // to have the graph calculate this topSort for us, we can use the topSort
  // iterator, to build an ordered
  var vertices = [];

  graph.topsort(function(vertex, path){
    vertices.push(vertex.name);
  });

  vertices === [ 'foo', 'bar', 'baz' ];

Developing

• npm install
• npm test runs the tests headless
• npm run test:server runs the tests and the development server
• npm build builds the development dist
• npm build:production builds the production dist