DAGGraph - Directed Acyclic Graph with Validation

🎯 Overview

DAGGraph is a powerful directed acyclic graph implementation that extends the base Graph class with comprehensive validation, type checking, and business rules. Built for node-based editors and data flow systems, it follows industry patterns from Blender, Houdini, and Unreal Engine.

What Makes DAGGraph Special

• 🚫 Automatic Cycle Prevention - Maintains acyclic property essential for execution order
• ✅ Two-Layer Validation - Type checking (Layer A) + Business rules (Layer B)
• 🔍 Smart Edge Finding - Discover valid connections with caching and async support
• 📦 Local Type System - Register types locally without polluting global registry
• 🏗️ Service Architecture - Clean separation between interface and implementation
• 📡 Unified Event System - Single EventEmitter for all graph and DAG events (can be shared with other components)

Two-Layer Validation Architecture

Inspired by Houdini and Blender, DAGGraph uses a two-layer validation system:

• Layer A (Type Checking): Fast, deterministic, cacheable type compatibility checks
• Layer B (Business Rules): Context-dependent validation (cycles, multiplicity, custom rules)

📚 Complete API Reference

Node Operations

| Method | Description | Returns | | ----------------------------- | --------------------------------- | ------------------- | | addNode(node) | Add a new node to the graph | void | | removeNode(nodeId) | Remove a node and its connections | boolean | | updateNode(nodeId, updates) | Update node properties | boolean | | getNode(nodeId) | Get a specific node | Node \| undefined | | getNodes() | Get all nodes | Node[] | | getNodesByType(type) | Get nodes of specific type | Node[] |

Edge Operations

| Method | Description | Returns | | ---------------------------------- | ----------------------------------------- | ------------------- | | addEdge(edge, skipValidation?) | Add edge with optional validation skip | void | | removeEdge(edgeId) | Remove an edge | boolean | | getEdge(edgeId) | Get a specific edge | Edge \| undefined | | getEdges() | Get all edges | Edge[] | | getNodeInputEdges(nodeId) | Get all edges coming INTO a node | Edge[] | | getNodeOutputEdges(nodeId) | Get all edges going OUT of a node | Edge[] | | getSocketEdges(nodeId, socketId) | Get edges connected to a specific socket | Edge[] | | getNodeDependencies(nodeId) | Get IDs of nodes this node depends on | NodeId[] | | getNodeDependents(nodeId) | Get IDs of nodes that depend on this node | NodeId[] |

Connection Validation

| Method | Description | Returns | | ---------------------------------------------------------------- | -------------------------------------------- | ---------------------- | | canConnect(sourceNode, sourceSocket, targetNode, targetSocket) | Check if connection is structurally possible | boolean | | validateConnection(...) | Check type compatibility (Layer A) | ValidationResult | | validateEdge(edgeId) | Validate existing edge (Layer B) | EdgeValidationResult | | validateAllEdges(options?) | Validate all edges with progress | Promise<Map> | | getEdgeValidation(edgeId) | Get current validation state | EdgeValidationResult | | getInvalidEdges() | Get all invalid edge IDs | EdgeId[] |

Edge Finding (UI Integration)

| Method | Description | Returns | | ---------------------------------------------- | ----------------------------- | ----------------------- | | findValidTargets(nodeId, socketId, options?) | Find valid connection targets | Promise<TargetInfo[]> | | findValidSources(nodeId, socketId, options?) | Find valid connection sources | Promise<SourceInfo[]> |

DAG Analysis Operations

| Method | Description | Returns | | --------------------- | ------------------------------------ | ------------------ | | topologicalSort() | Get execution order (null if cycles) | NodeId[] \| null | | getExecutionOrder() | Alias for topologicalSort | NodeId[] \| null | | detectCycles() | Check if graph has cycles | boolean | | isValidDAG() | Check if graph is valid DAG | boolean | | getSourceNodes() | Get nodes with NO incoming edges | Node[] | | getSinkNodes() | Get nodes with NO outgoing edges | Node[] |

Advanced Graph Analysis

| Method | Description | Returns | | ------------------ | ------------------------------------------------- | ----------- | | findIslands() | Find disconnected components | Node[][] | | organizeLayers() | Organize nodes into parallel execution layers | Layer[] | | findHubs() | Find highly connected nodes (>2x avg connections) | HubInfo[] |

Local Type Registry

| Method | Description | Returns | | --------------------------------- | -------------------------------------- | ----------------- | | registerLocal(type, definition) | Register local type definition | void | | removeLocal(type) | Remove local type | boolean | | getLocalTypes() | Get all local type names | string[] | | hasType(type) | Check if type exists (local or global) | boolean | | getRegistry() | Get the overlay registry | OverlayRegistry |

Serialization

| Method | Description | Returns | | ------------------------------ | ---------------------------------- | ----------------- | | serialize() | Export graph with local types | SerializedGraph | | load(data) | Load graph data (replaces current) | void | | clear() | Remove all nodes and edges | void | | static import(data, config?) | Create new DAGGraph from data | DAGGraph |

Events

| Method | Description | | ---------------------- | ----------------------- | | on(event, handler) | Subscribe to events | | off(event, handler?) | Unsubscribe from events | | once(event, handler) | Subscribe once |

Statistics

| Method | Description | Returns | | ------------ | -------------------- | ------------ | | getStats() | Get graph statistics | GraphStats |

🏗️ Architecture Overview

DAGGraph uses a service-oriented architecture with clean separation of concerns:

DAGGraph (Public Interface)
├── DAGQueries (Structural Analysis)
│   ├── topologicalSort()
│   ├── detectCycles()
│   ├── findIslands()
│   ├── organizeLayers()
│   └── findHubs()
├── CompatibilityValidator (Type Checking - Layer A)
│   └── Validates socket type compatibility
├── BusinessRuleValidator (Business Rules - Layer B)
│   ├── Multiplicity constraints
│   └── Cycle detection
├── EdgeFinder (Connection Discovery)
│   ├── findValidTargets()
│   └── findValidSources()
└── OverlayRegistry (Local Types)
    └── Local type definitions

💡 Core Concepts

Two-Layer Validation System

Layer A - Type Compatibility (Deterministic)

• Pure type/schema checking
• Cacheable forever
• Used by EdgeFinder for previews
• Checked BEFORE edge is added

Layer B - Business Rules (Contextual)

• Multiplicity constraints
• Cycle detection after edge exists
• Custom validators
• Checked AFTER edge is added

Invalid Edges Can Exist!

Just like an IDE allows you to write invalid code, DAGGraph allows invalid edges to exist but marks them:

// Edge added even if invalid
dag.addEdge(edge);

// Check validation state
const validation = dag.validateEdge(edge.id);
if (!validation.valid) {
  // Edge exists but is marked invalid
  if (validation.severity === "error") {
    // Type mismatch or cycle - show in red
  } else if (validation.severity === "restriction") {
    // Multiplicity violation - show in yellow
  }
}

📖 Usage Examples

Basic Setup

import { DAGGraph, NodeTypeRegistry, EventEmitter } from "@cook-step/dag-graph";

// Create registry with node types
const registry = new NodeTypeRegistry();
registry.register("number", {
  inputs: [{ id: "in", schema: { type: "number" } }],
  outputs: [{ id: "out", schema: { type: "number" } }],
});

// Create DAG - Basic
const dag = new DAGGraph({ registry });

// Create DAG - With custom EventEmitter (for integration with other systems)
const sharedEventEmitter = new EventEmitter();
const dag = new DAGGraph({ 
  registry,
  eventEmitter: sharedEventEmitter // Optional: share events with other components
});

Working with Nodes and Edges

// Add nodes
dag.addNode({ id: "n1", type: "number" });
dag.addNode({ id: "n2", type: "number" });

// Get edges for a node
const inputEdges = dag.getNodeInputEdges("n2"); // All incoming
const outputEdges = dag.getNodeOutputEdges("n1"); // All outgoing

// Get dependencies
const deps = dag.getNodeDependencies("n2"); // ["n1"]
const dependents = dag.getNodeDependents("n1"); // ["n2"]

Connection Validation

// Check BEFORE creating edge
const canConnect = dag.canConnect("n1", "out", "n2", "in");
if (!canConnect) {
  console.log("Structurally impossible!");
}

// Check type compatibility
const validation = dag.validateConnection("n1", "out", "n2", "in");
if (!validation.valid) {
  console.log(`Type mismatch: ${validation.reason}`);
}

// Add edge (works even if invalid!)
dag.addEdge({
  id: "e1",
  source: { nodeId: "n1", socketId: "out" },
  target: { nodeId: "n2", socketId: "in" },
});

Finding Valid Connections (UI)

// When user drags from output socket
const targets = await dag.findValidTargets("sourceNode", "output", {
  async: true,
  batchSize: 10,
  useCache: true,
});

// Highlight valid targets in UI
targets.forEach((target) => {
  if (target.valid) {
    highlightSocket(target.nodeId, target.socketId, "green");
  }
});

Graph Analysis

// Get execution order
const order = dag.topologicalSort();
if (!order) {
  console.error("Graph has cycles!");
}

// Find disconnected components
const islands = dag.findIslands();
console.log(`Found ${islands.length} disconnected components`);

// Organize into parallel layers
const layers = dag.organizeLayers();
layers.forEach((layer) => {
  console.log(`Layer ${layer.level}: ${layer.nodes.length} nodes`);
});

// Find hub nodes
const hubs = dag.findHubs();
hubs.forEach((hub) => {
  console.log(`Hub ${hub.node.id}: ${hub.connections} connections`);
});

Local Types (Groups/Templates)

// Register local type for a group
dag.registerLocal("group:calculator", {
  inputs: [
    { id: "a", schema: { type: "number" } },
    { id: "b", schema: { type: "number" } },
  ],
  outputs: [{ id: "sum", schema: { type: "number" } }],
});

// Use like any other type
dag.addNode({ id: "calc1", type: "group:calculator" });

// List local types
const localTypes = dag.getLocalTypes(); // ["group:calculator"]

Serialization

// Save graph
const data = dag.serialize();
localStorage.setItem("myGraph", JSON.stringify(data));

// Load graph
const savedData = JSON.parse(localStorage.getItem("myGraph"));
dag.load(savedData);

// Or create new instance
const newDag = DAGGraph.import(savedData);

Event System

DAGGraph uses a unified EventEmitter that combines both Graph base events and DAG-specific events. You can optionally provide your own EventEmitter for integration with other systems:

// Option 1: Use default EventEmitter
const dag = new DAGGraph({ registry });

// Option 2: Share EventEmitter with other components (e.g., Runtime)
const sharedEvents = new EventEmitter<DAGGraphEvents>();
const dag = new DAGGraph({ 
  registry,
  eventEmitter: sharedEvents // Share events across systems
});

// Structure change events (from base Graph)
dag.on("node:added", (node) => console.log(`Node ${node.id} added`));
dag.on("node:removed", (nodeId, node) => console.log(`Node ${nodeId} removed`));
dag.on("edge:added", (edge) => console.log(`Edge ${edge.id} added`));
dag.on("edge:removed", (edgeId, edge) => console.log(`Edge ${edgeId} removed`));

// DAG-specific events
dag.on("dag:cycle:detected", (edge, cyclePath) => {
  console.error(`Cycle detected: ${cyclePath.join(" -> ")}`);
});

dag.on("dag:validation:changed", (edgeId, result) => {
  if (!result.valid) {
    console.warn(`Edge ${edgeId} invalid: ${result.reason}`);
  }
});

dag.on("dag:topology:invalidated", () => {
  console.log("Graph structure changed, recalculating execution order");
});

// Validation lifecycle events
dag.on("dag:graphValidation:started", () => {
  showProgressBar();
});

dag.on("dag:graphValidation:progress", ({ current, total }) => {
  updateProgress(current, total);
});

dag.on("dag:graphValidation:completed", (results) => {
  hideProgressBar();
  const invalid = Array.from(results.values()).filter(r => !r.valid);
  if (invalid.length > 0) {
    console.warn(`${invalid.length} edges have validation issues`);
  }
});

// Batch validation events
dag.on("dag:validation:batch:completed", (results) => {
  console.log(`Batch validation completed for ${results.size} edges`);
});

🎯 Common Patterns

Safe Edge Creation with User Confirmation

function createEdgeSafely(dag: DAGGraph, source: any, target: any): boolean {
  const validation = dag.validateConnection(
    source.nodeId,
    source.socketId,
    target.nodeId,
    target.socketId,
  );

  if (!validation.valid) {
    if (validation.severity === "error") {
      alert(`Cannot connect: ${validation.reason}`);
      return false;
    }

    if (validation.severity === "restriction") {
      if (!confirm(`Warning: ${validation.reason}. Continue?`)) {
        return false;
      }
    }
  }

  dag.addEdge({
    id: generateId(),
    source,
    target,
  });

  return true;
}

Execution Pipeline

function executeGraph(dag: DAGGraph) {
  // Get execution order
  const order = dag.topologicalSort();
  if (!order) {
    throw new Error("Graph contains cycles!");
  }

  // Execute layer by layer for parallelization
  const layers = dag.organizeLayers();

  for (const layer of layers) {
    // All nodes in same layer can run in parallel
    await Promise.all(layer.nodes.map((node) => executeNode(node)));
  }
}

Highlighting Invalid Edges

// After loading or changes
const invalidEdges = dag.getInvalidEdges();

invalidEdges.forEach((edgeId) => {
  const validation = dag.getEdgeValidation(edgeId);

  const color = validation.severity === "error" ? "red" : "yellow";
  highlightEdge(edgeId, color);

  // Show tooltip on hover
  setEdgeTooltip(edgeId, validation.reason);
});

⚡ Performance

Operation Benchmarks

| Operation | Base Graph | DAGGraph | Notes | | --------------------- | ---------- | ------------------ | ------------------------- | | addNode() | ~0.01ms | ~0.02ms | History tracking overhead | | addEdge() | ~0.01ms | ~0.05ms | Validation + cycle check | | getNodeInputEdges() | ~0.01ms | ~0.01ms | Direct iteration | | findIslands() | N/A | ~5ms (1000 nodes) | BFS traversal | | organizeLayers() | N/A | ~10ms (1000 nodes) | Dependency analysis | | validateAllEdges() | N/A | ~50ms (1000 edges) | Async supported |

Optimization Tips

1. Bulk Loading: Skip validation during load, validate once at end

   edges.forEach((e) => dag.addEdge(e, true)); // Skip validation
   await dag.validateAllEdges(); // Validate all at once

2. Cache Edge Finding: Results cached for 60 seconds

   const targets = await dag.findValidTargets(node, socket, {
     useCache: true,
   });

3. Use Layers for Parallel Execution: Execute nodes in same layer simultaneously

   const layers = dag.organizeLayers();
   // All nodes in layer[i] can run in parallel

🏗️ Architecture Details

Two-Layer Validation System

Following industry leaders like Houdini and Blender, DAGGraph implements a sophisticated two-layer validation architecture:

Layer A - Type Compatibility (CompatibilityValidator)

• Purpose: Check if socket types are compatible
• Characteristics:
  • Deterministic (same inputs = same result)
  • Fast (uses caching)
  • Eternally cacheable
  • Used during edge finding for instant feedback

Layer B - Business Rules (BusinessRuleValidator)

• Purpose: Context-dependent validation
• Validates:
  • Type compatibility (delegates to Layer A)
  • Cycle detection (maintains DAG property)
  • Multiplicity constraints (single vs multiple connections)
  • Custom business rules
• Characteristics:
  • Context-aware (depends on graph state)
  • Not cacheable (state changes affect results)
  • Runs after edge creation

Service Architecture

DAGGraph uses a clean service-oriented architecture:

DAGGraph (Public API)
    ├── CompatibilityValidator (Layer A validation)
    ├── BusinessRuleValidator (Layer B validation)
    ├── DAGQueries (Graph analysis)
    ├── EdgeFinder (Connection discovery)
    └── OverlayRegistry (Local type system)

Each service is injected with dependencies, avoiding circular references and maintaining clean separation of concerns.

🚀 Best Practices

1. Always check getNodeInputEdges()/getNodeOutputEdges() before assuming connectivity
2. Use findIslands() to detect disconnected components that might not execute
3. Call organizeLayers() for optimal parallel execution strategy
4. Monitor hub nodes with findHubs() - they might be bottlenecks
5. Let invalid edges exist - users can fix them (Houdini/Blender pattern)
6. Cache validation results for responsive UI
7. Use local types for groups without polluting global registry
8. Subscribe to validation events for real-time UI updates
9. Validate all edges after deserialization - schemas may have changed
10. Use two-layer validation - quick type check during drag, full validation after drop

📄 License

MIT

See Also

• Graph Base Package - Pure graph implementation
• Edge Finding Guide - Deep dive into connection discovery
• Architecture Decisions - Why groups were removed