Skip to content

num::graph_distance_levels

Defined in header <linear/graph/levels.hpp>

array<idx> graph_distance_levels(const spmat &A, view<const idx> seeds);  // (1)

array<idx> graph_distance_levels(const spmat &A, idx seed);  // (2)

(1) Label each row by its graph distance from a seed set.

An edge joins rows whose distances differ by at most one, so grouping by distance makes the matrix block-tridiagonal, as build_block_order and factor_block_lu need. A component no seed reaches restarts at distance zero from its own search. With L balanced levels, elimination costs \(O(n^3/L^2)\).

(2) The same labels from a single seed row.

Parameters

  • A: Square CSR matrix whose undirected support graph is traversed.
  • seeds: Rows at distance zero. Empty means every component starts from its lowest-numbered row.

Return value

One level label per row.

Exceptions

  • std::invalid_argument: If A is not square or a seed is out of range.