Caerowa

Graph data structures and algorithms optimized for node-based editors like React Flow.

Features

• GraphStore - Directed graph with parent/child relationships
• Traversal - BFS, DFS, path finding, ancestors/descendants
• Cycle Detection - Check cycles before adding edges
• Topological Sort - Multiple algorithms (Kahn's, DFS)
• Undo/Redo - Command pattern with full history
• React Flow - Built-in format conversion

Installation

npm install @justn/caerowa

Quick Start

import { GraphStore, bfs, hasCycle, topologicalSort } from '@justn/caerowa';

// Create a graph
const graph = new GraphStore();

graph.addNode('a', { id: 'a', label: 'Start' });
graph.addNode('b', { id: 'b', label: 'Process' });
graph.addNode('c', { id: 'c', label: 'End' });

graph.addEdge('a', 'b');
graph.addEdge('b', 'c');

// Traverse
bfs(graph, 'a', (node, depth) => {
  console.log(`${node.id} at depth ${depth}`);
});

// Check for cycles
console.log(hasCycle(graph)); // false

// Topological sort
console.log(topologicalSort(graph)); // ['a', 'b', 'c']

API

GraphStore

Core graph data structure with O(1) node/edge operations.

const graph = new GraphStore<MyNodeType>();

// Node operations
graph.addNode(id, data);
graph.removeNode(id);
graph.getNode(id);
graph.hasNode(id);
graph.getAllNodes();
graph.getNodeCount();

// Edge operations
graph.addEdge(from, to);
graph.removeEdge(from, to);
graph.hasEdge(from, to);
graph.getEdgeCount();

// Relationships
graph.getChildren(id);
graph.getParents(id);
graph.getRoots();      // Nodes with no parents
graph.getLeaves();     // Nodes with no children

// Utilities
graph.clone();
graph.clear();

Traversal

import { bfs, dfs, getDescendants, getAncestors, findPath, findAllPaths } from '@justn/caerowa';

// BFS/DFS with callback
bfs(graph, startId, (node, depth) => {
  console.log(node.id, depth);
  return false; // Return false to stop
});

// Get all descendants/ancestors
getDescendants(graph, nodeId);
getAncestors(graph, nodeId);

// Find paths
findPath(graph, fromId, toId);        // Shortest path
findAllPaths(graph, fromId, toId);    // All paths (max 100)

Cycle Detection

import { hasCycle, wouldCreateCycle, canReach, findCycleNodes } from '@justn/caerowa';

hasCycle(graph);                    // Check if graph has cycles
wouldCreateCycle(graph, from, to);  // Check before adding edge
canReach(graph, from, to);          // Check reachability
findCycleNodes(graph);              // Get nodes in cycle (for debugging)

Topological Sort

import { topologicalSort, topologicalSortDFS, partialTopologicalSort } from '@justn/caerowa';

topologicalSort(graph);              // Kahn's algorithm
topologicalSortDFS(graph);           // DFS-based
partialTopologicalSort(graph, id);   // Sort from specific node

Undo/Redo

import {
  CommandStack,
  createCommand,
  batchCommands,
  createAddNodeCommand,
  createRemoveNodeCommand,
  createAddEdgeCommand,
  createMoveNodeCommand
} from '@justn/caerowa';

const stack = new CommandStack({ maxSize: 100 });

// Execute commands
stack.execute(createAddNodeCommand(graph, 'a', { id: 'a' }));
stack.execute(createAddEdgeCommand(graph, 'a', 'b'));

// Undo/Redo
stack.undo();
stack.redo();

// Check state
stack.canUndo;
stack.canRedo;
stack.undoSize;
stack.redoSize;

// Batch multiple commands
stack.execute(batchCommands([
  createMoveNodeCommand(graph, 'a', { x: 100, y: 200 }),
  createMoveNodeCommand(graph, 'b', { x: 300, y: 200 }),
], 'Move multiple nodes'));

React Flow Integration

Convert between Caerowa and React Flow formats:

import { GraphStore } from '@justn/caerowa';

// From React Flow
const nodes = [
  { id: '1', position: { x: 0, y: 0 }, data: { label: 'Node 1' } },
  { id: '2', position: { x: 100, y: 100 }, data: { label: 'Node 2' } },
];
const edges = [
  { id: 'e1-2', source: '1', target: '2' },
];

const graph = GraphStore.fromReactFlowFormat(nodes, edges);

// To React Flow
const { nodes: rfNodes, edges: rfEdges } = graph.toReactFlowFormat();

Example: Prevent Cycles in React Flow

import { useCallback } from 'react';
import { useReactFlow } from '@xyflow/react';
import { GraphStore, wouldCreateCycle } from '@justn/caerowa';

function useConnectionValidator() {
  const { getNodes, getEdges } = useReactFlow();

  const isValidConnection = useCallback((connection) => {
    const nodes = getNodes();
    const edges = getEdges();
    const graph = GraphStore.fromReactFlowFormat(nodes, edges);

    // Prevent cycles
    return !wouldCreateCycle(graph, connection.source, connection.target);
  }, [getNodes, getEdges]);

  return isValidConnection;
}

TypeScript

Full TypeScript support with generics:

interface MyNode {
  id: string;
  label: string;
  position: { x: number; y: number };
}

const graph = new GraphStore<MyNode>();
graph.addNode('1', { id: '1', label: 'Test', position: { x: 0, y: 0 } });

const node = graph.getNode('1'); // MyNode | undefined

License

MIT