Struct ExpanderChecker 

pub struct ExpanderChecker {
    pub graph: UndirectedGraph,
}

Checks expansion properties of a graph using an approximation of the Cheeger constant.

The Cheeger constant h(G) = min_{S: 0<|S|≤n/2} |∂S| / |S|. This checker approximates it by trying all subsets up to a given size limit.

Fields

graph: UndirectedGraph

The underlying undirected graph.

Implementations

impl ExpanderChecker

pub fn new(graph: UndirectedGraph) -> Self

Create from an existing undirected graph.

pub fn edge_boundary(&self, subset: &[usize]) -> usize

Compute the edge boundary |∂S| = edges with exactly one endpoint in S.

pub fn approximate_cheeger(&self) -> f64

Approximate Cheeger constant: try all subsets of size 1..=n/2 (only feasible for small n). Returns the approximate h(G) as a rational approximation (boundary/size).

pub fn is_expander(&self, threshold: f64) -> bool

Returns true if the graph is an h-vertex expander: h(G) ≥ threshold.