Skip to main content

Metric

feral_ordering_core::quotient_graph

Trait Metric 

Source 
pub trait Metric {
    type Score: Copy + Ord + Default;

    // Required methods
    fn n_buckets(n: usize) -> usize;
    fn init_score(len: i32) -> Self::Score;
    fn bucket(score: Self::Score, n: usize) -> usize;
    fn coarse_bucket(idx: usize, n: usize) -> bool;
    fn merge_supervariable(parent: &mut Self::Score, child: Self::Score);
    fn run_elimination(
        ws: &mut Workspace,
        aggressive: bool,
    ) -> Result<StepFlops, OrderingError>;
}
Expand description

Selection metric for an AMD-family bottom-up ordering.

All methods are zero-overhead #[inline(always)] no-ops or identity functions in the AMD case; AMF (MinFill) provides non-trivial implementations. The trait is consumed at the run_elimination dispatch point and at the bucket-allocation dispatch in crate::quotient_graph::order; the metric-specific inner-loop sites are inlined into the concrete run_elimination_* functions in algo.rs.

Required Associated Types§

Source

type Score: Copy + Ord + Default

Bucket key produced by the selection metric. AMD uses i32 (the running degree); AMF will also use i32 (quantized RMF).

Required Methods§

Source

fn n_buckets(n: usize) -> usize

Length of the bucket head array Workspace::head. AMD: n (indexed up to n - 1 by select_pivot’s while deg < n). AMF: 2 * n + 2.

Source

fn init_score(len: i32) -> Self::Score

Initial score for a freshly-loaded variable with adjacency length len. AMD and AMF both seed len.

Source

fn bucket(score: Self::Score, n: usize) -> usize

Bucket index for the given score. AMD: identity. AMF: identity for s ≤ n, coarse-stride above.

Source

fn coarse_bucket(idx: usize, n: usize) -> bool

Whether idx falls in the “coarse” bucket region — i.e. select_pivot must linear-scan the bucket chain to pick the minimum-score entry, rather than just taking the head. AMD always returns false; AMF returns idx > n.

Source

fn merge_supervariable(parent: &mut Self::Score, child: Self::Score)

Update parent’s score on supervariable merge of child into parent. AMD: no-op. AMF: *parent = max(*parent, child).

Source

fn run_elimination( ws: &mut Workspace, aggressive: bool, ) -> Result<StepFlops, OrderingError>

Run the metric’s elimination loop on a freshly initialised Workspace. Returns the accumulated flop counters.

MinDegree dispatches to run_elimination (the AMD-specific loop); MinFill dispatches to run_elimination_amf.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§