Expand description
In-memory graph algorithms operating on a loaded Subgraph (§5.4).
Pure CPU, synchronous, no external dependencies (D-039).
§Determinism
Every function here is a deterministic function of the Subgraph value:
the same graph yields the same answer, byte for byte, on every run and every
platform. That is not automatic, and it is the reason this module reaches for
BTreeMap/BTreeSet in places where a HashMap would be the reflexive
choice:
Subgraph’s maps are ordered, so node iteration order is the ULID order.- Returns are ordered too. A
HashSet<String>return would push the nondeterminism onto the caller — Rust’s default hasher is seeded per process, so a caller iterating the result to write it back would emit rows in a different order on every run. - Ties are broken explicitly, never by iteration order. Two heap entries with equal distance are ordered by node id; two communities with equal modularity gain resolve to the lower community index.
Without all three, FakeClock fixes the clock and the analytics still drift.
§Edge weights must be non-negative
dijkstra and astar assume weight >= 0; that is what makes a settled
node final. The schema does not enforce it (weight REAL NOT NULL, no
CHECK), so a negative weight is storable today and would yield a silently
wrong shortest path. Both functions therefore bound their own work and
[Subgraph::load] refuses to build a graph containing one, so the failure is
loud at the boundary rather than quiet in the result.
Functions§
- astar
- A* search from
starttogoal(§5.4). - dijkstra
- Dijkstra’s algorithm for shortest path distances (§5.4).
- k_core
- k-core decomposition: the maximal induced subgraph in which every node has
degree at least
k(§5.4). - louvain
- Louvain community detection, local-moving phase (§5.4).
- modularity
- Newman-Girvan modularity of a partition, treating the graph as undirected.
- scc
- Strongly connected components by Kosaraju’s algorithm (§5.4).