Skip to main content

finalize_permutation

feral_ordering_core::quotient_graph

Function finalize_permutation 

Source 
pub fn finalize_permutation(ws: &mut Workspace) -> Vec<i32>
Expand description

Consume the post-elimination state and produce the final permutation.

On entry ws must have completed run_elimination. Performs, in order:

  1. Un-flip pe and elen (faer amd.rs:567-572) so pe[i] holds the parent pivot and elen[i] holds the frontal size.
  2. Path compression (amd.rs:573-590): each absorbed supervariable i (nv[i] == 0) has its pe chain walked until a pivot is found, then all intermediates are rewritten to point at that pivot directly. Inert in Slice A — becomes active once supervariable detection (Slice B) lands.
  3. Assembly-tree postorder with big-child-last heuristic (amd.rs:5-49, amd.rs:51-124, amd.rs:593-599). Reuses head/next/last as child/sibling/stack scratch; writes the postorder index into w.
  4. Invert w into head[k] = pivot at postorder k (amd.rs:600-606).
  5. Assign starting positions to each pivot’s block (amd.rs:607-615): next[e] = nel, then nel += nv[e].
  6. Expand absorbed supervariables + place dense-deferred variables at the tail (amd.rs:617-629).
  7. Emit perm: perm[next[i]] = i for every i (amd.rs:631-633).

Returns a permutation perm of length n where perm[k] is the column of the original matrix to be eliminated at step k.