Skip to main content

Crate feral_kahip

Crate feral_kahip 

Source
Expand description

KaHIP-style flow-based nested-dissection fill-reducing ordering.

Status: phases K1-K6 complete. kahip_order produces a contract-conforming permutation via the full pipeline: K1 data reduction (degree-1 / degree-2 / twin / subset), then K2-K6 multilevel flow-based nested dissection on the reduced graph (coarsen → initial bisect → uncoarsen with K3 flow refinement → K4 boundary-bipartite node separator → recurse), then K1 expansion to lift the reduced-graph permutation back to original indices.

Plan. dev/plans/ordering-kahip.md tracks the six implementation phases:

  • K1: Data reduction (degree-1 / degree-2 / twin / neighborhood- subset rules, fixed-point loop, expansion permutation stack).
  • K2: Push-relabel max-flow (with gap relabeling).
  • K3: Flow-based edge refinement (band extraction, super-source/ sink construction, Most Balanced Min Cut).
  • K4: Flow-based node separator (vertex-capacitated max-flow).
  • K5: V-cycle / F-cycle controller (cut-edge-preserving re-coarsening for monotone quality improvement).
  • K6: Driver and Fast / Eco / Strong modes.

Reference papers (published, public-domain algorithms — the implementation must be clean-room from these sources, not from KaHIP’s C++ codebase):

  • Sanders & Schulz, “Engineering Multilevel Graph Partitioning Algorithms” (2011) — the kaffpa framework.
  • Ost, Schulz & Strash, “Engineering Data Reduction for Nested Dissection” (2021) — the K1 reduction rules.

The public surface conforms to the FERAL ordering-crate contract (dev/plans/ordering-crate-contract.md): CscPattern, OrderingStats, OrderingError, and CONTRACT_VERSION are re-exported from feral-ordering-core.

Structs§

CscPattern
Borrowed symmetric sparsity pattern in CSC form.
KahipOptions
Tunable parameters for KaHIP nested-dissection ordering.
KahipStats
Crate-specific diagnostic statistics.
OrderingStats
Diagnostic counters shared by every ordering producer.

Enums§

KahipMode
Quality / speed tradeoff modes for the KaHIP driver.
OrderingError
Shared error shape for the ordering-crate contract.

Constants§

CONTRACT_VERSION
Version of the shared ordering-crate contract.

Functions§

kahip_order
Compute a fill-reducing KaHIP nested-dissection ordering.
kahip_order_full
Contract-conforming ordering producer.