DAGraph

A directed acyclic graph (DAG) implementation in TypeScript.

• DAGraph
  • Features
  • Usage
    • Basic
    • Custom Objects
    • Visualization
    • Custom Traversal
  • Install
  • Development

Features

• Generic Graph Structure: Store any identifiable data in the graph.
• Topological Sort: Iterate over nodes in topological order (dependencies first).
• Cycle Detection: Automatically detects and prevents cycles when adding edges.
• Root Traversal: Efficiently access all root nodes (nodes with no dependencies).
• Graph Reversal: Create a new graph with all edges reversed.
• Depth-First Traversal: Visit nodes with context, parent, depth, and index information.
• TypeScript: Written in TypeScript with full type definitions.

Usage

Basic

import createDAG from '@sha1n/dagraph';

const dag = createDAG();

dag.addNode({id : 'a'});
dag.addEdge({id : 'b'}, {id : 'a'}); // b -> a
dag.addEdge({id : 'c'}, {id : 'a'}); // c -> a
dag.addEdge({id : 'd'}, {id : 'b'}); // d -> b

// Topological sort
for (const node of dag.topologicalSort()) {
  console.log(node.id);
}

Custom Objects

Any object implementing the Identifiable interface (having an id: string property) can be stored.

import { createDAG, Identifiable } from '@sha1n/dagraph';

type MyThing = {
  id: string; 
  name: string;
  doSomething(): void;
};

const myThing: MyThing = {
    id: 'a',
    name: 'my thing',
    doSomething: () => {
      console.log('A');
    }
  };

const myOtherThing: MyThing = {
    id: 'b',
    name: 'my other thing',
    doSomething: () => {
      console.log('B');
    }
  };

const myDAG = createDAG<MyThing>();

// Add nodes explicitly or implicitly via addEdge
myDAG.addEdge(myThing, myOtherThing); // myThing -> myOtherThing

Visualization

You can visualize the graph structure using built-in formatters with the traverse method.

Indented List

import createDAG, { createIndentFormatter } from '@sha1n/dagraph';

const dag = createDAG();
// ... add nodes and edges ...

const lines: string[] = [];
dag.traverse(createIndentFormatter(), lines);
console.log(lines.join('\n'));

// Output example:
// A
//   B
//     C

Tree Structure

import createDAG, { createTreeAsciiFormatter } from '@sha1n/dagraph';

const dag = createDAG();
// ... add nodes and edges ...

const lines: string[] = [];
dag.traverse(createTreeAsciiFormatter(), lines);
console.log(lines.join('\n'));

// Output example:
// A
// ├── B
// │   └── C
// └── D
//     └── E

Custom Traversal

The traverse method allows you to visit every node in a depth-first manner, effectively expanding the graph into a tree (nodes with multiple parents are visited for each path).

import createDAG, { DAGVisitor } from '@sha1n/dagraph';

// ... setup dag ...

const visitor: DAGVisitor<MyType, void> = (node, state, context) => {
  console.log(`Node: ${node.id}, Depth: ${state.depth}, Parent: ${state.parent?.id}`);
};

dag.traverse(visitor);

Install

Using pnpm (recommended):

pnpm add @sha1n/dagraph

Using npm:

npm i @sha1n/dagraph

Using yarn:

yarn add @sha1n/dagraph

Development

This project uses pnpm for dependency management.

Prerequisites

• Node.js (version specified in .nvmrc or engines in package.json)
• pnpm

Commands

• Install dependencies:

  pnpm install

• Build:

  pnpm build

• Run Tests:

  pnpm test

• Lint:

  pnpm lint