npm package: @justn/caerowa
Description: Graph data structures for node-based editors
Author: Justn
Latest version: 0.1.0

# 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

```bash
npm install @justn/caerowa
```

## Quick Start

```typescript
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.

```typescript
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

```typescript
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

```typescript
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

```typescript
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

```typescript
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:

```typescript
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

```typescript
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:

```typescript
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