Trait ProperCutInstance 

pub trait ProperCutInstance: Send + Sync {
    // Required methods
    fn init(graph: &DynamicGraph, lambda_min: u64, lambda_max: u64) -> Self
       where Self: Sized;
    fn apply_inserts(&mut self, edges: &[(EdgeId, VertexId, VertexId)]);
    fn apply_deletes(&mut self, edges: &[(EdgeId, VertexId, VertexId)]);
    fn query(&mut self) -> InstanceResult;
    fn bounds(&self) -> (u64, u64);
}

A bounded-range proper cut instance

This trait defines the interface for maintaining minimum proper cuts over a dynamic graph, assuming the cut value λ remains within a bounded range [λ_min, λ_max].

Proper Cuts

A proper cut is a partition (U, V \ U) where both U and V \ U induce connected subgraphs. This is stricter than a general cut.

Bounded Range Assumption

The instance assumes λ ∈ [λ_min, λ_max]:

• If λ < λ_min: Undefined behavior
• If λ ∈ [λ_min, λ_max]: Returns ValueInRange with witness
• If λ > λ_max: Returns AboveRange

Update Protocol

Updates must follow this order:

1. Call apply_inserts() with batch of insertions
2. Call apply_deletes() with batch of deletions
3. Call query() to get updated result

Thread Safety

Implementations must be Send + Sync for use in parallel algorithms.

Required Methods

fn init(graph: &DynamicGraph, lambda_min: u64, lambda_max: u64) -> Self

where Self: Sized,

Initialize instance on graph with given bounds

Creates a new instance that maintains minimum proper cuts for the given graph, assuming λ ∈ [λ_min, λ_max].

Arguments

• graph - The dynamic graph to operate on
• lambda_min - Minimum bound on the cut value
• lambda_max - Maximum bound on the cut value

Panics

May panic if λ_min > λ_max or if the graph is invalid.

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

Apply batch of edge insertions

Inserts a batch of edges into the maintained structure. Must be called before apply_deletes() in each update round.

Arguments

• edges - Slice of (edge_id, source, target) tuples to insert

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

Apply batch of edge deletions

Deletes a batch of edges from the maintained structure. Must be called after apply_inserts() in each update round.

Arguments

• edges - Slice of (edge_id, source, target) tuples to delete

fn query(&mut self) -> InstanceResult

Query current minimum proper cut

Returns the current minimum proper cut value and witness, or indicates that the cut value exceeds the maximum bound.

Returns

• ValueInRange { value, witness } if λ ∈ [λ_min, λ_max]
• AboveRange if λ > λ_max

Complexity

Typically O(1) to O(log n) depending on the data structure.

fn bounds(&self) -> (u64, u64)

Get the lambda bounds for this instance

Returns the [λ_min, λ_max] bounds this instance was initialized with.

Returns

A tuple (λ_min, λ_max)

Implementors

impl ProperCutInstance for BoundedInstance

impl ProperCutInstance for StubInstance