Dependency Graph

A simple dependency graph with the following features:

• Node Management:

  • Add nodes with unique string identifiers
  • Check if a node exists

• Dependency Management:

  • Add dependencies between nodes
  • Prevent circular dependencies automatically

• Query Capabilities:

  • Get direct dependencies of a node
  • Get all dependencies (direct and indirect)
  • Get all nodes that depend on a specific node
  • Generate a topological sort of the graph

• Error Handling:

  • Validation for node existence
  • Detection and prevention of circular dependencies

Examples

Basic usage

import { DependencyGraph } from '@mattbenton/dependency-graph';

const graph = new DependencyGraph();

// Add nodes
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addNode('D');

// Define dependencies between nodes
graph.addDependency('A', 'B'); // A depends on B
graph.addDependency('A', 'C'); // A depends on C
graph.addDependency('B', 'D'); // B depends on D

// Get all the nodes with the dependent ones sorted first
const result = graph.getTopologicalSort('dependents_first');
// => D, B, C, A

With node data

You can associate structed data with nodes and query them back:

import { DependencyGraph } from '@mattbenton/dependency-graph';

const graph = new DependencyGraph<{ name: string }>();

// Add nodes
graph.addNode('A', { name: 'Apple' });
graph.addNode('B', { name: 'Banana' });
graph.addNode('C', { name: 'Carrot' });
graph.addNode('D', { name: 'Date' });

// Define dependencies between nodes
graph.addDependency('A', 'B'); // A depends on B
graph.addDependency('A', 'C'); // A depends on C
graph.addDependency('B', 'D'); // B depends on D

// Get all the nodes with the dependent ones sorted first
const result = graph.getTopologicalSortWithData('dependents_first');
/* =>
[
  { id: 'D', data: { name: 'Date' } },
  { id: 'B', data: { name: 'Banana' } },
  { id: 'C', data: { name: 'Carrot' } },
  { id: 'A', data: { name: 'Apple' } }
]
*/