Struct DeterministicLocalKCut 

pub struct DeterministicLocalKCut { /* private fields */ }

Deterministic Local K-Cut algorithm

Implements the LocalKCutOracle trait using a deterministic BFS-based exploration strategy. The algorithm:

1. Starts BFS from seed vertices
2. Explores outward layer by layer
3. Tracks boundary size at each layer
4. Returns the smallest cut found ≤ budget

Determinism

The algorithm is completely deterministic:

• BFS order determined by vertex ID ordering
• Seed selection based on deterministic family generator
• No random sampling or probabilistic choices

Time Complexity

O(radius * (|V| + |E|)) for a single query in the worst case, but typically much faster due to early termination.

Implementations

impl DeterministicLocalKCut

pub fn new(max_radius: usize) -> Self

Create a new deterministic local k-cut oracle

Arguments

• max_radius - Maximum search radius (BFS depth)

Returns

A new oracle instance

Examples

use ruvector_mincut::localkcut::paper_impl::DeterministicLocalKCut;

let oracle = DeterministicLocalKCut::new(10);

pub fn with_family_generator( max_radius: usize, family_generator: DeterministicFamilyGenerator, ) -> Self

Create with custom family generator

Arguments

• max_radius - Maximum search radius
• family_generator - Custom family generator

Returns

A new oracle with custom configuration

Trait Implementations

impl Clone for DeterministicLocalKCut

fn clone(&self) -> DeterministicLocalKCut

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DeterministicLocalKCut

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for DeterministicLocalKCut

fn default() -> Self

Returns the “default value” for a type.

impl LocalKCutOracle for DeterministicLocalKCut

fn search(&self, graph: &DynamicGraph, query: LocalKCutQuery) -> LocalKCutResult

Search for a local minimum cut satisfying the query