DAGraph

A directed acyclic graph (DAG) implementation in TypeScript.

• DAGraph
  • Features
  • Usage
    • Basic
    • Custom Objects
  • 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

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