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 topologically ordered map of key/value pairs with a simple API for adding constraints.

Used for ordering initializers in Ember. Has a flexible constraint syntax that can add before/after contraints that can forward reference things yet to be added.

API

// import DAGMap from "dag-map";
const DAGMap = require("dag-map").default;

let map = new DAGMap();

// map a key value pair
// #add(
//   key: string, value: any,
//   before?: string[] | string | undefined,
//   after?: string[] | string | undefined
// )
map.add('eat', 'Eat Dinner');

// add a key value pair with before and after constraints
map.add('serve', 'Serve the food', 'eat', 'set');

// keys can be added after a key has been referenced
map.add('set', 'Set the table');

// graph now is eat -> serve -> set

// constraints can be an array
map.add('cook', 'Cook the roast and veggies', 'serve', ['prep', 'buy']);

map.add('wash', 'Wash the veggies', 'prep', 'buy');
map.add('buy', 'Buy roast and veggies');
map.add('prep', 'Prep veggies', undefined, 'wash');

// log in order (multiple valid spots for set the table).
map.each((key, val) => console.log(`${key}: ${val}`));
// set: Set the table
// buy: Buy roast and veggies
// wash: Wash the veggies
// prep: Prep veggies
// cook: Cook the roast and veggies
// serve: Serve the food
// eat: Eat Dinner

Notes

add is aliased as addEdges for backwards compat. each is aliased as topsort for backwards compat.

Developing

• npm install
• npm test runs the tests headless
• npm run build rebuild
• npm run docs documentation