Graph Base Class

Overview

The Graph class is a pure data structure implementation for managing nodes and edges in a graph. It provides fundamental graph operations without any business rules or validation logic, following the Repository pattern from Domain-Driven Design (DDD).

Recent Updates (v0.1.0)

🎯 Type-Safe Events Without Index Signatures

The EventEmitter now supports strict type safety for events without requiring index signatures:

// Events are strictly typed - no index signature needed!
interface MyEvents {
  nodeAdded: (node: Node) => void;
  nodeRemoved: (id: string, node: Node) => void;
  // No [key: string]: ... required!
}

const emitter = new EventEmitter<MyEvents>();
emitter.on('nodeAdded', handler); // ✅ Type-safe
emitter.on('wrongEvent', handler); // ❌ TypeScript error!

This follows the pattern used by modern libraries like Vue.js and mitt, using conditional types for maximum type safety.

🎉 Composition over Inheritance

Graph uses composition for event handling instead of extending EventEmitter:

// New way (composition)
graph.events.on('nodeAdded', handler);
graph.events.emit('nodeAdded', node);

// Legacy way (still supported via proxy methods)
graph.on('nodeAdded', handler); // @deprecated

📊 Enhanced Events

• nodeRemoved now includes the removed node: (nodeId, node)
• edgeRemoved now includes the removed edge: (edgeId, edge)
• New beforeClear event with statistics
• graphCleared now includes statistics

Philosophy

The Graph base class is designed to be:

• Pure: No business rules, just data structure operations
• Fast: O(1) lookups via optimized indices
• Extensible: Can be extended for specific use cases (DAG, State Machine, Flow, etc.)
• Unopinionated: No assumptions about graph usage or constraints
• Cycle-Agnostic: Supports graphs with cycles (state machines, flow graphs, neural networks)
• Composable: Uses composition over inheritance for better flexibility

Core Responsibilities

✅ What Graph Base DOES

1. Node Management

   • Add, remove, update nodes
   • Track nodes by type via indices
   • Maintain node metadata

2. Edge Management

   • Add, remove edges
   • Maintain source/target indices for O(1) lookups
   • Track edge connections

3. Query Operations

   • Find nodes by type, ID
   • Get node dependencies/dependents
   • Traverse graph (ancestors, descendants)

4. Performance Optimization

   • Indexed lookups for nodes and edges
   • Caching of expensive operations
   • Efficient graph traversal

5. Serialization

   • Export graph structure as JSON
   • Clone graph instances

❌ What Graph Base DOES NOT DO

1. No Validation

   • No cycle prevention (cycles are allowed!)
   • No type checking
   • No connection rules

2. No Business Rules

   • No multiplicity constraints
   • No required connections
   • No domain-specific logic

3. No Execution

   • No dirty tracking
   • No data flow
   • No runtime behavior

Usage

Basic Graph Operations

import { Graph } from "@cook-step/graph";

// Create a pure graph
const graph = new Graph();

// Add nodes - no validation
graph.addNode({
  id: "node1",
  type: "processor",
  position: { x: 0, y: 0 },
});

graph.addNode({
  id: "node2",
  type: "processor",
  position: { x: 100, y: 0 },
});

// Add edges - no validation
graph.addEdge({
  id: "edge1",
  source: { nodeId: "node1", socketId: "out" },
  target: { nodeId: "node2", socketId: "in" },
});

// Query operations
const nodes = graph.getNodes();
const edges = graph.getEdges();
const processorNodes = graph.getNodesByType("processor");

Event Handling (New Composition API)

// Subscribe to events using the new composition API
graph.events.on('nodeAdded', (node) => {
  console.log('Node added:', node.id);
});

graph.events.on('nodeRemoved', (nodeId, node) => {
  console.log('Node removed:', nodeId);
  // Now you have access to the removed node for undo/logging!
});

graph.events.on('beforeClear', (stats) => {
  console.log(`Clearing graph with ${stats.nodeCount} nodes and ${stats.edgeCount} edges`);
});

// One-time listeners
graph.events.once('graphCleared', (stats) => {
  console.log(`Graph cleared. Removed ${stats.nodeCount} nodes`);
});

// Remove listeners
const handler = (node) => console.log(node);
graph.events.on('nodeAdded', handler);
graph.events.off('nodeAdded', handler);

Graph Queries

// Get node connections
const outputEdges = graph.getNodeOutputEdges("node1");
const inputEdges = graph.getNodeInputEdges("node2");

// Get dependencies (what a node depends on)
const deps = graph.getNodeDependencies("node2"); // ["node1"]

// Get dependents (what depends on a node)
const dependents = graph.getNodeDependents("node1"); // ["node2"]

// Get all ancestors (recursive traversal up the graph)
const ancestors = graph.getAncestors("node4"); // Set<NodeId> of all upstream nodes

// Get all descendants (recursive traversal down the graph)
const descendants = graph.getDescendants("node1"); // Set<NodeId> of all downstream nodes

// Topological sort (no cycle validation)
const order = graph.topologicalSort();

Extending Graph

For specific use cases, extend the Graph class:

// For Directed Acyclic Graphs (Blender/Houdini style)
import { DAGGraph } from "@cook-step/graph";
const dag = new DAGGraph(); // Adds cycle detection, validation

// For State Machines (with cycles)
class StateMachineGraph extends Graph {
  transition(event: string) {
    /* ... */
  }
}

// For Flow-based Programming (N8N/Node-RED style)
class FlowGraph extends Graph {
  execute(data: any) {
    /* ... */
  }
}

Architecture

Graph (Base Class)
├── Node Management
│   ├── addNode()
│   ├── removeNode()
│   ├── updateNode()
│   └── getNode()
├── Edge Management
│   ├── addEdge()
│   ├── removeEdge()
│   └── getEdge()
├── Query Operations
│   ├── getNodesByType()
│   ├── getNodeDependencies()
│   ├── getNodeDependents()
│   ├── getAncestors()
│   └── getDescendants()
└── Optimization
    ├── Indexed Lookups
    ├── Cache System
    └── Lazy Evaluation

Note: DAG-specific operations like topologicalSort(), detectCycles(), getSourceNodes(), and getSinkNodes() have been moved to the DAGGraph package as they don't apply to general graphs with cycles.

Performance Characteristics

| Operation | Time Complexity | Notes | | ---------------- | --------------- | --------------------------- | | addNode() | O(1) | Direct map insertion | | removeNode() | O(E) | Must remove connected edges | | addEdge() | O(1) | Updates indices | | removeEdge() | O(1) | Updates indices | | getNode() | O(1) | Direct lookup | | getNodesByType() | O(1) | Pre-indexed | | getNodeEdges() | O(1) | Pre-indexed | | getAncestors() | O(V+E) | Recursive traversal | | getDescendants() | O(V+E) | Recursive traversal |

Serialization & Loading

Save and Load Graph State

import { Graph } from "@cook-step/graph";

// Create and populate a graph
const graph = new Graph();
graph.addNode({ id: "n1", type: "input" });
graph.addNode({ id: "n2", type: "processor" });
graph.addEdge({
  id: "e1",
  source: { nodeId: "n1", socketId: "out" },
  target: { nodeId: "n2", socketId: "in" },
});

// Save graph state as JSON
const savedData = graph.serialize();
// Returns: { nodes: [...], edges: [...], metadata: {...} }

// Load into existing graph instance (replaces current content)
graph.load(savedData);

// Create new graph from saved data
const newGraph = Graph.import(savedData);

// Clear graph content
graph.clear();

Methods

• serialize(): SerializedGraph - Export current graph state as JSON
• load(data: SerializedGraph): void - Load data into current instance (replaces content)
• static import(data: SerializedGraph): Graph - Create new Graph from saved data
• clear(): void - Remove all nodes and edges

Design Patterns

Repository Pattern

Graph acts as a repository for nodes and edges, providing:

• Storage and retrieval
• Query capabilities
• No business logic

Index Pattern

Multiple indices for O(1) lookups:

• Nodes by ID
• Nodes by type
• Edges by source
• Edges by target

Cache Pattern

Expensive operations are cached:

• Topological sort
• Dependencies/dependents
• Complex queries

When to Use Graph vs DAGGraph

Use Graph Base When:

• Building state machines (cycles are normal)
• Implementing flow-based systems (Node-RED/n8n style with loops)
• Neural networks with feedback loops
• Social networks or web graphs
• Need maximum flexibility
• Performance is critical (no validation overhead)
• Building visualization-only tools

Use DAGGraph When:

• Building node editors (Blender/Houdini style)
• Need cycle prevention
• Want connection validation
• Building data pipelines
• Need topological sorting for execution order
• Require source/sink node identification
• Need dirty tracking for execution

Testing

The package has comprehensive test coverage with tests organized by functionality:

Test Organization

tests/
├── Graph.base.test.ts       # Pure Graph base tests
├── Graph.test.ts            # General graph operations
├── groups.test.ts           # Node grouping functionality
├── boundary-analysis.test.ts # Graph boundary analysis
├── graph-navigation.test.ts  # Graph traversal
├── cache-integration.test.ts # Cache system integration
├── history-integration.test.ts # History tracking
└── performance.test.ts      # Performance benchmarks

src/dag/tests/               # DAG-specific tests
├── validation.test.ts       # Validation system
├── edge-validation.test.ts  # Edge validation
├── dirty-tracking.test.ts   # Dirty state tracking
└── ... (other DAG tests)

Run tests with:

pnpm test              # Run all tests
pnpm test Graph.base   # Run only base Graph tests

API Reference

See the full API documentation for detailed method signatures.

Examples

Custom Graph Extension

class MyCustomGraph extends Graph {
  // Add domain-specific methods
  validateConnections(): boolean {
    // Custom validation logic
    return true;
  }

  // Override base methods if needed
  addEdge(edge: Edge): void {
    // Custom pre-processing
    console.log(`Adding edge: ${edge.id}`);

    // Call base implementation
    super.addEdge(edge);

    // Custom post-processing
    this.updateStatistics();
  }
}

Graph without Validation

const graph = new Graph();

// These operations will succeed even if they create cycles
// or invalid connections - Graph doesn't validate

graph.addNode({ id: "a", type: "node" });
graph.addNode({ id: "b", type: "node" });

// Create a cycle - Graph allows it
graph.addEdge({
  id: "e1",
  source: { nodeId: "a", socketId: "out" },
  target: { nodeId: "b", socketId: "in" },
});

graph.addEdge({
  id: "e2",
  source: { nodeId: "b", socketId: "out" },
  target: { nodeId: "a", socketId: "in" },
});

// Graph doesn't care about cycles!
const edges = graph.getEdges(); // Both edges exist

Migration from DAGGraph

If you're currently using DAGGraph but want the pure Graph:

// Before (with validation)
import { Graph } from "@cook-step/graph"; // This imports DAGGraph as Graph

// After (pure graph)
import { Graph } from "@cook-step/graph/base"; // Pure Graph class

// Or be explicit
import { Graph, DAGGraph } from "@cook-step/graph";
const pureGraph = new Graph(); // No validation
const dagGraph = new DAGGraph(); // With validation

Migration Guide

From v0.7 to v0.8

The main change is improved type safety for events:

// v0.7 - Required index signature
interface MyEvents {
  [key: string]: (...args: any[]) => void; // Had to include this
  nodeAdded: (node: Node) => void;
}

// v0.8 - No index signature needed!
interface MyEvents {
  nodeAdded: (node: Node) => void;
  // Clean, type-safe, no index signature!
}

From v0.6 to v0.7

The main change is moving from inheritance to composition for events:

// Old way (v0.6) - Still works but deprecated
graph.on('nodeAdded', handler);
graph.off('nodeAdded', handler);

// New way (v0.7+) - Recommended
graph.events.on('nodeAdded', handler);
graph.events.off('nodeAdded', handler);

Event signatures that changed:

// Old signatures
nodeRemoved: (nodeId: NodeId) => void;
edgeRemoved: (edgeId: EdgeId) => void;
graphCleared: () => void;

// New signatures (include more data)
nodeRemoved: (nodeId: NodeId, node: Node) => void;
edgeRemoved: (edgeId: EdgeId, edge: Edge) => void;
graphCleared: (stats: { nodeCount: number; edgeCount: number }) => void;
beforeClear: (stats: { nodeCount: number; edgeCount: number }) => void; // New event

Best Practices

1. Use Graph base for data structures, not business logic
2. Extend Graph for domain-specific behavior
3. Keep validation in extended classes, not in Graph
4. Use indices for performance, don't scan arrays
5. Cache expensive operations but invalidate appropriately
6. Prefer composition over inheritance - Use graph.events instead of extending
7. Leverage enhanced events - Use removed objects for undo/redo functionality