Struct ForestPacking 

pub struct ForestPacking { /* private fields */ }

Forest packing for witness guarantees

A forest packing consists of multiple edge-disjoint spanning forests. Each forest witnesses certain cuts - a cut that cuts many edges in a forest is likely to be important.

Witness Property

A cut (S, V\S) is witnessed by a forest F if |F ∩ δ(S)| ≥ 1, where δ(S) is the set of edges crossing the cut.

Implementations

impl ForestPacking

pub fn greedy_packing( graph: &DynamicGraph, lambda_max: usize, epsilon: f64, ) -> Self

Create greedy forest packing with ⌈λ_max · log(m) / ε²⌉ forests

Algorithm

Greedy algorithm:

1. Start with empty forests
2. For each forest, greedily add edges that don’t create cycles
3. Continue until we have enough forests for witness guarantees

Arguments

• graph - The graph to pack
• lambda_max - Upper bound on maximum cut value
• epsilon - Approximation parameter

Returns

A forest packing with witness guarantees

pub fn witnesses_cut(&self, cut_edges: &[(VertexId, VertexId)]) -> bool

Check if a cut respects all forests (witness property)

A cut is witnessed if it cuts at least one edge from each forest. This ensures that important cuts are not missed.

Arguments

• cut_edges - Edges crossing the cut

Returns

true if the cut is witnessed by all forests

pub fn num_forests(&self) -> usize

Get number of forests

pub fn forest(&self, index: usize) -> Option<&HashSet<(VertexId, VertexId)>>

Get a specific forest