v2.4.0

Minor Changes

• #36 e1ef7bc Thanks @davidkpiano! - Add unweighted-distance and explicit connectivity APIs. Harden weighted arithmetic, low-link traversal, transform callbacks, and bulk deletion.

v2.3.0

Minor Changes

• #34 5a8eef6 Thanks @davidkpiano! - Large performance overhaul of the algorithm hot paths:

  • getStronglyConnectedComponents is now an iterative typed-array Tarjan over the CSR (stack-safe, ~15x faster).
  • getTopologicalSort is a CSR Kahn's pass with cached in-degrees (~4x faster, no more O(n²) queue).
  • isBipartite/getMaximumBipartiteMatching 2-color directly over the cached CSR with no per-call adjacency rebuild (~60x faster on repeated queries).
  • Bellman-Ford (algorithm: 'bellman-ford') relaxes cached compact arc arrays; single-pair queries skip tie-predecessor bookkeeping entirely (~15x faster).
  • Floyd-Warshall all-pairs uses a flat distance matrix with copy-on-write tie-predecessor lists and O(length) path materialization (~4x faster).
  • genBFS/genDFS/genPostorder are hand-rolled chunked iterators (identical order and laziness semantics, no generator resume machinery; ~1.5-2x faster full traversals), and traversal snapshots now reuse the CSR's node snapshot instead of copying graph.nodes per call.
  • Dijkstra / A* / bidirectional search read default edge weights from a cached per-arc Float64Array instead of loading edge objects in the inner loop.
  • getDegree serves from a per-version degree map (one hashed lookup per call), and repeated indexed queries against the same graph skip the WeakMap via a one-entry memo.
  • All-targets shortest-path reconstruction (genShortestPaths) materializes each path once via a shared backtracking buffer instead of per-level array spreads.

v2.2.0

Minor Changes

• #32 3baa78c Thanks @davidkpiano! - Add lazy, multi-source, directional, radius-limited postorder traversal. Keep
  active traversal structure stable across graph mutations and reject non-finite
  A-star heuristic values.

• e4a800e Thanks @davidkpiano! - Add immutable counterparts for graph CRUD, patch application, and layout geometry updates. These helpers return updated graph copies while leaving their input graphs untouched.

• 7b5ac38 Thanks @davidkpiano! - Add graph-generic path-set and coverage utilities: path inspection and
  containment, coverage targets and coverage-preserving reduction, edge-covering
  path planning, ordered shortest simple paths, Eulerian paths/circuits, and line
  graph construction.

• #31 0bd1016 Thanks @davidkpiano! - Add multi-source, directional, radius-limited BFS and DFS; induced neighborhood subgraphs; and graph union, intersection, difference, symmetric difference, disjoint union, and complement operations.

• 97622b1 Thanks @davidkpiano! - New algorithms, public kernel, cancellation, and format fidelity:

  • New algorithms: isPlanar (left-right planarity test), getTSPTour
    (nearest-neighbor + 2-opt), getSteinerTree (metric-closure
    2-approximation), getGraphColoring/isValidColoring (Welsh–Powell and
    DSatur), genAllPairsShortestPaths (lazy gen twin of
    getAllPairsShortestPaths).
  • New generators: createWattsStrogatzGraph, createBarabasiAlbertGraph.
  • New @statelyai/graph/kernel subpath: getIndex, getCSR,
    invalidateIndex, and memoizeByGraph — the fast-path primitives for
    large graphs and third-party algorithm plugins.
  • Cancellation: expensive algorithms (centrality, community detection,
    max-flow, all-pairs paths, isomorphism, dominators) accept
    options.signal: AbortSignal.
  • Round-trip fidelity: DOT preserves graph attributes, node/edge
    defaults, rank=same, HTML labels, and compass points; Mermaid preserves
    %%{init}%% directives, click handlers, linkStyle (now index-stable),
    state notes, mindmap ::icon(), and block arrow tokens.
  • Fix: getAllPairsShortestPaths no longer overflows the call stack on
    graphs with a few hundred nodes.
  • Benchmarks: reproducible via pnpm bench:compare (--quick variant,
    JSON results, generated docs tables, fairness notes).

• #33 66b3828 Thanks @davidkpiano! - Add getMappedGraph() and getFilteredGraph() structural transforms. getMappedGraph() returns a new graph with node/edge data transformed by mapping functions while preserving all structure; getFilteredGraph() returns a new graph keeping only nodes and edges that pass the given predicates, dropping incident edges of removed nodes. getSubgraph(), getReversedGraph(), and the new transforms now also preserve graph-level direction and style.

v2.1.0

Minor Changes

• #28 0498d52 Thanks @davidkpiano! - Layout suite round two: transitions, geometry utilities, portable constraints, and four more engines.

  • genLayoutTransition(from, to, options?) (@statelyai/graph/layout, zero-dep) — tween between two layouts of the same graph: yields interpolated LayoutFrames (drive with applyLayoutFrame, one per animation frame) and returns the target layout. Lay out with one engine, re-lay out with another, morph live. Options: steps (default 30), ease (default smoothstep).
  • Geometry utilities (@statelyai/graph/layout) — translateGraph(graph, dx, dy) and centerGraph(graph, rect) (mutable, in place): shift/center node positions, edge route points, and edge label rects. Hierarchy-aware — parent-relative children and container-relative edge routes are left alone.
  • LayoutOptions.constraints — portable, advisory layout constraints. First constraint: layer(node) assigns nodes to ordered layers along the flow axis. ELK maps it to partitions (elk.partitioning.partition); the Graphviz dot engine maps it to { rank=same; … } groups; engines without a layer concept ignore it.
  • @statelyai/graph/layout/forceatlas2 — getForceAtlas2Layout (sync; optional peers graphology + graphology-layout-forceatlas2): seeded determinism, native pinning via isFixed, edge weight influence.
  • @statelyai/graph/layout/d3-hierarchy — getTidyTreeLayout (sync; optional peer d3-hierarchy): Reingold–Tilford tidy tree. Root from rootId → initialNodeId → unique source; forests supported; non-tree extra edges preserved (spanning-tree layout).
  • @statelyai/graph/layout/webcola — getColaLayout (sync; optional peer webcola): constraint-based layout with overlap avoidance, seeded determinism, isFixed pinning, DAG flow via direction.
  • @statelyai/graph/layout/cytoscape — getCytoscapeLayout (async; optional peer cytoscape, headless): bridges cytoscape's layout ecosystem (grid, circle, concentric, breadthfirst, cose, plus caller-registered extensions via the injectable cy option). Compound nodes map to cytoscape parents.

  The package smoke test exercises all nine layout entry points against the packed tarball.

• #28 0498d52 Thanks @davidkpiano! - Analytical coverage tail: cores, Katz, bipartite matching, min-cut, seeded label propagation, and graph generators.

  • k-core — getCoreNumbers(graph) (Batagelj–Zaveršnik, O(m)) and getKCore(graph, k); degrees are undirected per the standard definition.
  • Katz centrality — getKatzCentrality(graph, { alpha, beta, getWeight, ... }); throws a descriptive error when alpha exceeds the spectral bound and iteration diverges.
  • Eigenvector centrality hardened — (A+I)-shifted power iteration (no more bipartite oscillation), getWeight support, descriptive non-convergence error. Differentially tested against graphology.
  • Bipartite — isBipartite(graph) and getMaximumBipartiteMatching(graph) (Hopcroft–Karp, O(m√n)); the non-bipartite error names the edge that closes the odd cycle.
  • Min-cut — getMinCut(graph, { source, sink, getCapacity? }) → { value, cutEdges, partition }, sharing the max-flow solver (value always equals getMaxFlow(...) by construction).
  • Seeded label propagation — getLabelPropagationCommunities gains seed: asynchronous LPA with seeded shuffling/tie-breaking, deterministic per seed.
  • Generators — createCompleteGraph(n), createGridGraph(rows, cols), createRandomGraph(n, p, { seed }) (G(n,p), deterministic per seed) in the root export.

• #25 e1e2107 Thanks @davidkpiano! - Pluggable layout: a renderer-agnostic layout contract with adapters for ELK, Graphviz, dagre, and d3-force — no layout algorithms of our own, just typed plug-and-play over the plain-JSON graph.

  • Model: edges gain points?: {x,y}[] (route waypoints incl. endpoints, tail→head) and routing?: 'polyline' | 'orthogonal' | 'splines' (splines = Graphviz 3n+1 bezier control-point convention). Both round-trip through every full-fidelity format, diff/patch, and LAYOUT_KEYS. Edge x/y/width/height are now canonically the edge-label rect (top-left + size) — engines read width/height as label dimensions and write computed label positions back; this matches dagre's own convention and was previously undefined.
  • @statelyai/graph/layout (zero-dep): LayoutFn/IterativeLayoutFn/LayoutFrame/LayoutOptions (direction, spacing, measure for renderer-owned text measurement, isFixed pinning, seed), plus applyLayoutFrame (per-animation-frame position writes, safe under the index contract), getLayoutBounds, getNodeSize.
  • @statelyai/graph/layout/elk — getElkLayout (async; optional peer elkjs): hierarchy + ports first-class, orthogonal edge routes captured into points, computed edge label rects, all ELK algorithms via algorithm/layoutOptions, injectable ELK instance for web workers. (fromELK now also captures routed sections and label geometry for anyone running ELK manually.)
  • @statelyai/graph/layout/dagre — getDagreLayout (sync; optional peer @dagrejs/dagre): polyline routes, label rects, multigraph parallel edges, compound support.
  • @statelyai/graph/layout/d3-force — genForceLayout generator (one simulation tick per next(), caller owns pacing/cancellation; yields LayoutFrames, returns the settled VisualGraph) + getForceLayout; seeded determinism (same seed ⇒ same layout), isFixed pinning; optional peer d3-force.
  • @statelyai/graph/layout/graphviz — getGraphvizLayout (async WASM; optional peer @hpcc-js/wasm-graphviz): all eight Graphviz engines (dot, neato, fdp, sfdp, circo, twopi, osage, patchwork), spline control points into points/routing: 'splines', label positions, y-flip/center→top-left conversion handled.

  The package smoke test exercises every adapter against the packed tarball.

• #28 0e5982a Thanks @davidkpiano! - xyflow: labels now land where the renderers actually read them. toXYFlow emits edge labels as the top-level edge.label (the prop React Flow / Svelte Flow render — previously the label went to edge.data.label, which built-in edges ignore) and node labels as data.label (what React Flow's default node renders). fromXYFlow reads both spots back for external React Flow input, and full-fidelity round-tripping via the __statelyai metadata is unchanged. If you relied on edge.data.label in toXYFlow output, read edge.label instead.

Patch Changes

• #28 0e5982a Thanks @davidkpiano! - getDegree is now O(1) per call: |out| + |in| corrected by a cached per-node count of non-directed self-loops (revalidated by index version + graph mode, like the CSR snapshot). A full degree sweep over a 100k-node/300k-edge graph drops from ~148 ms to ~10 ms — at parity with ngraph and graphology, which was the one benchmark cell this library lost across the board.

• a9d5a4b Thanks @davidkpiano! - Allow nullable initialNodeId config inputs in TypeScript, mark the package as side-effect free for bundlers, and add repo-wide type/convention checks to the verification gate.

• #28 0498d52 Thanks @davidkpiano! - Pathfinding internals: lazy path materialization and a typed-array heap. genShortestPaths now reconstructs a path only when it is actually yielded (abandoning the generator early skips the work), and the Dijkstra/A*/bidirectional hot loops use a Float64Array/Int32Array binary heap instead of object nodes. Same API, same results — measured −70% on first-path-then-stop, −41% on all-targets, −71% on single-target early exit (10k-node graph).

• af77e3f Thanks @davidkpiano! - Validate node initialNodeId references in addNode, updateNode, and batch node additions.

  Add prefixed canonical exports for traversal, transforms, diff patching, path joining, and walk stop helpers while preserving the old names as deprecated aliases.

v2.0.0

Major Changes

• #22 6bead2c Thanks @davidkpiano! - Correctness, performance, and API-honesty overhaul.

  Migration notes (the two changes most likely to require action):

  1. In-place field mutation is no longer auto-detected. edge.sourceId = 'x' / node.parentId = 'y' now require invalidateIndex(graph) afterwards (or use updateEdge/updateNode, or immutable-style array replacement — both auto-detected). Code relying on the old per-read deep scan gets stale query results. This trade bought O(1) reads: a 10k-node query sweep dropped from 17.3 s to 14 ms.
  2. Errors instead of silently wrong results: Dijkstra/A* throw on negative weights (use { algorithm: 'bellman-ford' }); Floyd-Warshall throws on negative cycles; GraphML/GEXF/GML importers throw on non-numeric numeric fields; updateNode/updateEdge reject orphaned port references and hierarchy-cycle-creating reparents.

  Full changes:

  • updateNode/updateEdge now apply every declared field. Previously x/y/width/height/shape/color/style (and edge mode/weight) were silently dropped. New NodeUpdate/EdgeUpdate types; optional fields accept null to unset (JSON-safe), making diff → patch → apply converge.
  • Mode-aware queries. getSuccessors, getPredecessors, getDegree, getInDegree, getOutDegree, getSources, getSinks now honor effective edge directedness (graph mode + per-edge overrides). getInEdges/getOutEdges remain structural (authored direction) and are documented as such.
  • Indexing is now O(1) per read (was O(nodes+edges) on every query — a 10k-node getSuccessors sweep dropped from 17.3 s to 14 ms). The index auto-rebuilds when graph.nodes/graph.edges are replaced or change length; in-place field mutations now require invalidateIndex() (previously auto-detected at the cost above). Also fixes stale-index results after immutable-style array replacement.
  • Algorithm fixes: zero-weight-cycle stack overflow in shortest paths/hasPath (now BFS-based); Dijkstra/A* throw on negative weights instead of silently returning wrong paths; isTree edge-count check; undirected cycle dedup no longer drops distinct cycles; biconnected components split correctly at DFS-root articulation points; SCC honors undirected/bidirectional edges; getTopologicalSort returns null for non-directed edges; isIsomorphic compares self-loop edges; Prim returns a spanning forest on disconnected graphs (matching Kruskal); undirected self-loops are reported by getCycles.
  • Mutation safety: updateEdge validates port references when endpoints change; updateNode rejects port removals that would orphan edge port refs and parent changes that would create hierarchy cycles.
  • Diff: getDiff now covers ports, weight, mode, sourcePort, targetPort; invertDiff no longer aliases its input.
  • Transforms: reverseGraph swaps sourcePort/targetPort and preserves edge mode and node ports; getSubgraph preserves ports/per-edge mode and strips dangling initialNodeId; flatten preserves authored leaf self-loops, edge weight/mode, node fields, and resolves the graph initialNodeId.
  • Walks: mode-aware traversal (undirected edges walk both ways); genQuickRandomWalk detours honor filter and no longer depend on shortest-path reconstruction; takeUntil*Coverage yield nothing when the target is already met.
  • Formats: toD2 no longer crashes on graphs not produced by fromD2; xyflow round-trips data: undefined without leaking metadata; per-edge mode round-trips in cytoscape/d3/jgf/gml/elk/xyflow; GraphML no longer mutates numeric-looking labels or trims whitespace and synthesizes collision-safe edge ids; GEXF preserves empty labels; DOT escapes newlines and quotes reserved keywords; mermaid escapes | in labels; fromAdjacencyList materializes referenced nodes; the format support matrix now matches actual converter behavior.

Minor Changes

• #22 e48bbda Thanks @davidkpiano! - CSR pathfinding, polynomial mixed-graph acyclicity, and malformed-input hardening:

  • Pathfinding on the CSR core. Dijkstra/BFS shortest paths and A* now run on the compressed-sparse-row snapshot. Measured on 50k nodes / 200k edges: single-target getShortestPath 329 → 58 ms (5.7×), getAStarPath 27 → 7 ms (3.8×), all-targets getShortestPaths 514 → 342 ms (reconstruction-bound). Results unchanged (validated by the differential Dijkstra oracle).
  • isAcyclic on mixed graphs is now polynomial in practice: cycles among directed edges alone, cycles among non-directed edges alone (union-find), and the all-singleton-SCC case resolve without enumeration; only ambiguous multi-node SCCs fall back to exact simple-cycle search, restricted to that SCC. A 30-diamond acyclic mixed graph (2^30 simple paths) that previously hung now resolves instantly.
  • New getGraphIssues(graph) (core export, zod-free): structural invariant checking — duplicate ids, dangling edge endpoints, missing parents, parent cycles (reported once per cycle), missing initial nodes, duplicate port names, invalid port references — with entity-naming messages and machine-readable codes. The recommended gate for untrusted/imported graphs; @statelyai/graph/schemas' validateGraph now delegates its invariant portion to it.
  • Hierarchy queries terminate on malformed parent cycles: getAncestors, getDescendants, getDepth, and getLCA previously hung forever on authored parentId cycles; each now stops at the first repeated node (documented convention).
  • mermaid/state: user nodes whose ids merely contain _region_ (e.g. foo_region_bar) are no longer mistaken for parallel-region markers and dropped — region detection now requires the exact structural pattern under a parallel parent.

• #22 6bead2c Thanks @davidkpiano! - Mode unification, standard-GraphML import, and follow-up fixes:

  • Per-edge mode overrides now work everywhere. isAcyclic/getCycles dispatch on effective edge modes — genuinely mixed graphs (directed + non-directed edges) use an exact simple-cycle search (correct, may be expensive on large dense mixed graphs); centrality (degree/in/out, closeness, PageRank, HITS, eigenvector), Prim MST, and isIsomorphic all honor per-edge modes. isIsomorphic no longer requires equal graph-level mode (effective edge modes are what's structural). Two parallel undirected edges are now correctly reported as a 2-cycle by getCycles (consistent with isAcyclic).
  • MST output preserves entity fields (node ports/shape/visual props; edge mode/ports/color) instead of stripping them.
  • Floyd-Warshall detects negative cycles and throws a descriptive error instead of crashing during path reconstruction.
  • Standard-GraphML import: nested <graph> elements → parentId hierarchy, native <port> elements → ports, sourceport/targetport attributes → edge port refs; multi-graph documents import the first graph. The format-support matrix is legitimately back to full hierarchy/ports for GraphML. Numeric <data> values that aren't numbers now throw a descriptive error (also in GEXF/GML) instead of silently poisoning the graph with NaN.
  • ELK port ids are document-unique (nodeId__portName) as ELK requires; original port names round-trip via metadata; external ELK input with ports resolves to correct endpoints.
  • mermaid/state emit: isolated plain states are emitted; node labels emit via state "label" as id (and parse back into label); graph.initialNodeId round-trips as a top-level [*] --> transition.
  • xyflow: parents are ordered before children in toXYFlow output, as React Flow requires.
  • Fixes from re-auditing the previous release: updateNode no longer hangs when reparenting onto a graph with a pre-existing authored parent cycle; invertDiff deep-copies nested values (ports/style/data) instead of sharing them with the input.
  • New perf regression test guards the O(1) index read path.

• #22 c482fcd Thanks @davidkpiano! - Performance core, new algorithms, and a differential-testing correctness moat:

  • CSR algorithm core. Hot algorithm loops now run on an internal compressed-sparse-row snapshot (Int32Array arcs, integer node indices — no string hashing in inner loops), cached per index and invalidated by the same transparent contract as the index (API mutations, array replacement, length changes; invalidateIndex() for in-place field mutation). Measured on a 2k-node/6k-edge graph: closeness 2,575 → 73 ms (35×), betweenness 4,597 → 169 ms (27×), HITS 202 → 4 ms (50×), PageRank 26 → 2 ms (13×); connected components on 100k nodes/100k edges 379 → 7 ms (54×). Head-to-head on identical graphs this is now faster than graphology for betweenness (1.7×), PageRank (1.3×), and components (2×). Public API and results are unchanged (validated by the new differential suite); a thresholded perf regression test guards the CSR path in CI.
  • New algorithms: getLouvainCommunities (deterministic Louvain modularity optimization), getMaxFlow (Edmonds–Karp max-flow with min-cut edges, capacities from weight), getDominatorTree (Cooper–Harvey–Kennedy immediate dominators — for statecharts: which states every path from the initial...

v1.0.0

Major Changes

• 5acd7c3 Thanks @davidkpiano! - Add graph and edge mode directedness, replacing graph type, and add D2 format support.

  Graphs now use mode: 'directed' | 'undirected' | 'bidirectional' as the graph-level default, and edges may override it with their own mode. Traversal, path, and query logic resolves effective edge mode so mixed directedness works consistently.

  Adds @statelyai/graph/d2 with parsing and emitting for D2 syntax, including hierarchy, ports, styles, comments, classes, imports, and connector directedness.

v0.13.0

Minor Changes

• aeedcc0 Thanks @davidkpiano! - Add semantic graph validation via validateGraph(), covering shape plus graph
  invariants such as duplicate ids, dangling edges, missing parents, invalid
  initial nodes, duplicate ports, invalid port references, and parent cycles.

  Default missing graph, node, edge, and port data values to null when
  creating resolved graph objects.

  Refresh format fidelity claims and conformance tests for ELK, xyflow, and
  Mermaid state round-tripping, and expand algorithm benchmarks across sparse,
  dense, compound, multi-edge, and port-heavy graphs.

v0.12.0

Minor Changes

• 09fe970 Thanks @davidkpiano! - Add runtime schema validation helpers, improve port round-tripping across
  structured format adapters, extend package smoke coverage to type-check public
  subpath imports, and document format support and validation usage in the README.

Patch Changes

• b4b2195 Thanks @davidkpiano! - Preserve graph metadata in GEXF, round-trip DOT edge port references, tighten
  structured format parity tests, and derive package smoke coverage from the
  published export map.

v0.11.1

Patch Changes

• 1480565 Thanks @davidkpiano! - Add Mermaid Ishikawa conversion and improve Mermaid v11.13 sequence and ER parsing.

• 18588bd Thanks @davidkpiano! - Preserve ports and edge port references in GraphML round-trips, allow nullable
  node labels in GraphSchema

v0.11.0

Minor Changes

• 88d0dbd Thanks @davidkpiano! - Add format support metadata as a published subpath, tighten schema drift checks,
  and modularize the algorithms entrypoint. This also adds benchmark coverage and
  CI checks for generated schema artifacts across multiple Node versions.