# Graph

Directed multigraph implementing the `Graph<K, N, E>` interface hierarchy. Nodes are keyed by `K` with data of type `N`; edges carry data of type `E`.

## Interface Hierarchy

- **`ReadonlyGraph<K, N, E>`** — read-only view: `getNode`, `hasNode`, `hasEdge`, `nodes`, `edges`, `inEdges`, `outEdges`, `inNeighbors`, `outNeighbors`, `inDegree`, `outDegree`. Extends `Keyed<K, GraphNode<K, N>>` so it supports `entries()` and `keys()`.
- **`Graph<K, N, E>`** — extends `ReadonlyGraph` with mutations: `addNode`, `addEdge`, `removeNode`, `removeEdges`.

Algorithm modules (`bfs`, `dijkstra`) depend on callback abstractions (`GetNeighbors<K>`, `GetWeightedNeighbors<K>`), not on these interfaces directly. Any graph-like data source can provide a neighbors callback.

## Implementation

### AdjacencyGraph

Adjacency-list directed multigraph backed by `Map<K, Map<K, E[]>>` for both in-edges and out-edges. The same `E[]` array is shared between `_inEdges` and `_outEdges`, halving memory and eliminating sync bugs.

Node data is stored as `GraphNode<K, N>` objects with stable reference identity — `getNode('a') === getNode('a')`.

| Operation                | Best      | Average   | Worst     |
| :----------------------- | :-------- | :-------- | :-------- |
| Space                    | O(V+E)    | O(V+E)    | O(V+E)    |
| `addNode`                | O(1)      | O(1)      | O(1)      |
| `addEdge`                | O(1)      | O(1)      | O(1)      |
| `getNode`                | O(1)      | O(1)      | O(1)      |
| `hasNode`                | O(1)      | O(1)      | O(1)      |
| `hasEdge`                | O(1)      | O(1)      | O(1)      |
| `removeNode`             | O(deg)    | O(deg)    | O(deg)    |
| `removeEdges`            | O(E_pair) | O(E_pair) | O(E_pair) |
| `inDegree` / `outDegree` | O(1)      | O(1)      | O(1)      |
| `inEdges` / `outEdges`   | O(deg)    | O(deg)    | O(deg)    |
| Iterate all nodes        | O(V)      | O(V)      | O(V)      |
| Iterate all edges        | O(E)      | O(E)      | O(E)      |

Where V = node count, E = edge count, deg = degree of the node, E_pair = edges between a specific pair.

**Strengths:** O(1) node/edge lookup and degree queries. Multigraph support (multiple edges between same pair). Filtered edge removal via predicate. Cascading node removal cleans up all incident edges and degree counts.

**Weaknesses:** Always directed — undirected graphs require adding edges in both directions manually. No built-in edge weights — use edge data `E` to carry weight.

## Key Design Decisions

- **`addEdge` throws if either node doesn't exist** — fail fast rather than auto-creating nodes. This prevents silent graph corruption from typos.
- **`removeNode` / `removeEdges` return count/boolean** — no-op on missing keys, consistent with the package's sentinel strategy.
- **Stable `GraphNode` references** — `getNode()` returns the stored object, not a copy. Updating via `addNode(key, newData)` mutates the existing node's `data` field in place, so references held by callers reflect the update.