Struct LocalKCut 

pub struct LocalKCut { /* private fields */ }

Deterministic Local K-Cut algorithm

Implementations

impl LocalKCut

pub fn new(graph: Arc<DynamicGraph>, k: usize) -> Self

Create new LocalKCut finder for cuts up to size k

Arguments

• graph - The graph to search in
• k - Maximum cut size to find

Returns

A new LocalKCut instance with deterministic edge colorings

pub fn find_cut(&self, v: VertexId) -> Option<LocalCutResult>

Find local minimum cut near vertex v with value ≤ k

Algorithm

1. Enumerate all 4^depth color combinations
2. For each combination, perform color-constrained BFS
3. Check if reachable set forms a valid cut
4. Return the minimum cut found

Arguments

• v - Starting vertex

Returns

Some(LocalCutResult) if a cut ≤ k is found, None otherwise

pub fn enumerate_paths( &self, v: VertexId, depth: usize, ) -> Vec<HashSet<VertexId>>

Enumerate all color-constrained paths from vertex up to depth

This generates all possible reachable sets for different color combinations, which is the core of the deterministic enumeration.

Arguments

• v - Starting vertex
• depth - Maximum path depth

Returns

Vector of reachable vertex sets, one per color combination

pub fn edge_color(&self, edge_id: EdgeId) -> Option<EdgeColor>

Get the color of an edge

pub fn radius(&self) -> usize

Get current search radius

pub fn max_cut_size(&self) -> usize

Get maximum cut size