Struct MinCutWrapper 

pub struct MinCutWrapper { /* private fields */ }

The main wrapper managing O(log n) bounded instances

Implementations

impl MinCutWrapper

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

Create a new wrapper with default instance factory

Arguments

• graph - Shared reference to the dynamic graph

Examples

let graph = Arc::new(DynamicGraph::new());
let wrapper = MinCutWrapper::new(graph);

pub fn with_factory<F>(graph: Arc<DynamicGraph>, factory: F) -> Self

where F: Fn(&DynamicGraph, u64, u64) -> Box<dyn ProperCutInstance> + Send + Sync + 'static,

Create a wrapper with a custom instance factory

Arguments

• graph - Shared reference to the dynamic graph
• factory - Function to create instances for a given range

Examples

let graph = Arc::new(DynamicGraph::new());
let wrapper = MinCutWrapper::with_factory(graph, |g, min, max| {
    Box::new(CustomInstance::init(g, min, max))
});

pub fn insert_edge(&mut self, edge_id: EdgeId, u: VertexId, v: VertexId)

Handle edge insertion event

Arguments

• edge_id - Unique identifier for the edge
• u - First endpoint
• v - Second endpoint

Examples

wrapper.insert_edge(0, 1, 2);

pub fn delete_edge(&mut self, edge_id: EdgeId, u: VertexId, v: VertexId)

Handle edge deletion event

Arguments

• edge_id - Unique identifier for the edge
• u - First endpoint
• v - Second endpoint

Examples

wrapper.delete_edge(0, 1, 2);

pub fn query(&mut self) -> MinCutResult

Query current minimum cut

Processes all buffered updates and returns the minimum cut value. Checks connectivity first for fast path when graph is disconnected.

Returns

MinCutResult indicating if graph is disconnected or providing the cut value

Examples

let result = wrapper.query();
match result {
    MinCutResult::Disconnected => println!("Min cut is 0"),
    MinCutResult::Value { cut_value, .. } => println!("Min cut is {}", cut_value),
}

pub fn num_instances(&self) -> usize

Get the number of instantiated instances

pub fn current_time(&self) -> u64

Get the current time counter

pub fn pending_updates(&self) -> usize

Get the number of pending updates

pub fn batch_insert_edges(&mut self, edges: &[(EdgeId, VertexId, VertexId)])

Batch insert multiple edges efficiently

Performance

O(k) where k = number of edges, vs O(k) individual calls with more overhead. Connectivity updates are batched, and updates are lazily evaluated on query.

Arguments

• edges - Slice of (edge_id, u, v) tuples

Examples

wrapper.batch_insert_edges(&[
    (0, 1, 2),
    (1, 2, 3),
    (2, 3, 4),
]);

pub fn batch_delete_edges(&mut self, edges: &[(EdgeId, VertexId, VertexId)])

Batch delete multiple edges efficiently

Performance

O(k) where k = number of edges, with lazy evaluation on query.

Arguments

• edges - Slice of (edge_id, u, v) tuples

Examples

wrapper.batch_delete_edges(&[
    (0, 1, 2),
    (1, 2, 3),
]);

pub fn batch_update( &mut self, inserts: &[(EdgeId, VertexId, VertexId)], deletes: &[(EdgeId, VertexId, VertexId)], )

Apply batch update with both insertions and deletions

Performance

Processes insertions first (as per paper), then deletions. All updates are lazily evaluated on the next query.

Arguments

• inserts - Edges to insert: (edge_id, u, v)
• deletes - Edges to delete: (edge_id, u, v)

Examples

wrapper.batch_update(
    &[(0, 1, 2), (1, 2, 3)],  // inserts
    &[(2, 3, 4)],              // deletes
);

pub fn flush_updates(&mut self)

Flush pending updates without querying

Forces all pending updates to be applied to instances without performing a min-cut query. Useful for preloading updates.

Performance

O(k log n) where k = pending updates, n = graph size

pub fn min_cut_value(&mut self) -> u64

Get the minimum cut value without full query overhead

Returns cached value if no pending updates, otherwise performs full query. This is a lazy query optimization.

Returns

The minimum cut value (0 if disconnected)

pub fn query_with_local_kcut(&mut self, source: VertexId) -> (u64, bool)

Query with LocalKCut certification

Uses DeterministicLocalKCut to verify/certify the minimum cut result. This provides additional confidence in the result by cross-checking with the paper’s LocalKCut algorithm (Theorem 4.1).

Arguments

• source - Source vertex for LocalKCut query

Returns

A tuple of (min_cut_value, certified) where certified is true if LocalKCut confirms the result.

pub fn local_cuts( &self, source: VertexId, lambda_max: u64, ) -> Vec<(f64, Vec<VertexId>)>

Get LocalKCut-based cuts from a vertex

Uses DeterministicLocalKCut to find all small cuts near a vertex. This is useful for identifying vulnerable parts of the graph.

Arguments

• source - Source vertex for the query
• lambda_max - Maximum cut value to consider

Returns

Vector of (cut_value, vertex_set) pairs for discovered cuts

pub fn build_hierarchy(&self) -> ThreeLevelHierarchy

Get the hierarchy decomposition for the current graph

Builds a ThreeLevelHierarchy (expander→precluster→cluster) for the current graph state. This is useful for understanding the graph structure and for certified mirror cut queries.

pub fn connectivity_curve( &self, ranked_edges: &[(VertexId, VertexId, f64)], k_max: usize, ) -> Vec<(usize, u64)>

Compute edge-connectivity degradation curve

Removes the top-K ranked edges and computes the min-cut after each removal. This validates that boundary detection is working correctly:

• Sharp early drops indicate good ranking (edges are on the true cut)
• Flat/noisy curves suggest poor boundary detection

Arguments

• ranked_edges - Edges ranked by their “cut-likelihood” score, highest first. Each entry is (source, target, score).
• k_max - Maximum number of edges to remove

Returns

Vector of (k, min_cut_value) pairs showing how min-cut degrades. An ideal detector shows an elbow early (near true min-cut boundary).

Example

let mut wrapper = MinCutWrapper::new(graph);
// ... insert edges ...

// Rank edges by boundary likelihood (from your detector)
let ranked = vec![(1, 2, 0.95), (2, 3, 0.8), (3, 4, 0.6)];

let curve = wrapper.connectivity_curve(&ranked, 5);
// curve[0] = (0, initial_min_cut)
// curve[1] = (1, min_cut_after_removing_top_edge)
// ...
// Early sharp drop = good detector

pub fn find_elbow(curve: &[(usize, u64)]) -> Option<(usize, u64)>

Detect elbow point in connectivity curve

Finds where the curve has the sharpest drop, indicating the boundary between cut-critical edges and interior edges.

Arguments

• curve - Output from connectivity_curve()

Returns

(elbow_k, drop_magnitude) - The k value where the biggest drop occurs and how much the min-cut dropped.

pub fn detector_quality( &self, ranked_edges: &[(VertexId, VertexId, f64)], true_cut_size: usize, ) -> f64

Validate boundary detector quality

Computes a quality score for a boundary detector based on how quickly its ranked edges reduce the min-cut.

Arguments

• ranked_edges - Edges ranked by detector, highest score first
• true_cut_size - Known size of true minimum cut (if available)

Returns

Quality score from 0.0 (poor) to 1.0 (perfect). Perfect means top-k edges exactly match the true cut.