Struct WitnessHandle 

pub struct WitnessHandle { /* private fields */ }

Handle to a witness (cheap to clone)

This is the primary type for passing witnesses around. It uses an Arc internally so cloning is O(1) and witnesses can be shared across threads.

Examples

use ruvector_mincut::instance::witness::WitnessHandle;
use roaring::RoaringBitmap;

let mut membership = RoaringBitmap::new();
membership.insert(1);
membership.insert(2);
membership.insert(3);

let witness = WitnessHandle::new(1, membership, 4);
assert!(witness.contains(1));
assert!(witness.contains(2));
assert!(!witness.contains(5));
assert_eq!(witness.boundary_size(), 4);

Implementations

impl WitnessHandle

pub fn new( seed: VertexId, membership: RoaringBitmap, boundary_size: u64, ) -> Self

Create a new witness handle

Arguments

• seed - The seed vertex defining this cut (must be in membership)
• membership - Bitmap of vertices in the cut set U
• boundary_size - The size of the boundary |δ(U)|

Panics

Panics if the seed vertex is not in the membership set (debug builds only)

Examples

use ruvector_mincut::instance::witness::WitnessHandle;
use roaring::RoaringBitmap;

let mut membership = RoaringBitmap::new();
membership.insert(0);
membership.insert(1);

let witness = WitnessHandle::new(0, membership, 5);
assert_eq!(witness.seed(), 0);

pub fn contains(&self, v: VertexId) -> bool

Check if vertex is in the cut set U

Time Complexity

O(1) via bitmap lookup

Examples

use ruvector_mincut::instance::witness::WitnessHandle;
use roaring::RoaringBitmap;

let mut membership = RoaringBitmap::new();
membership.insert(5);
membership.insert(10);

let witness = WitnessHandle::new(5, membership, 3);
assert!(witness.contains(5));
assert!(witness.contains(10));
assert!(!witness.contains(15));

pub fn boundary_size(&self) -> u64

Get boundary size |δ(U)|

Returns the pre-computed boundary size for O(1) access.

Examples

use ruvector_mincut::instance::witness::WitnessHandle;
use roaring::RoaringBitmap;

let witness = WitnessHandle::new(1, RoaringBitmap::from_iter([1, 2, 3]), 7);
assert_eq!(witness.boundary_size(), 7);

pub fn seed(&self) -> VertexId

Get the seed vertex

Examples

use ruvector_mincut::instance::witness::WitnessHandle;
use roaring::RoaringBitmap;

let witness = WitnessHandle::new(42, RoaringBitmap::from_iter([42u32]), 1);
assert_eq!(witness.seed(), 42);

pub fn hash(&self) -> u64

Get the witness hash

Used for fast equality checks without comparing full membership sets.

pub fn materialize_partition(&self) -> (HashSet<VertexId>, HashSet<VertexId>)

Materialize full partition (U, V \ U)

This is an expensive operation (O(|V|)) that converts the implicit representation into explicit sets. Use sparingly, primarily for debugging or verification.

Returns

A tuple (U, V_minus_U) where:

• U is the set of vertices in the cut
• V_minus_U is the complement set

Note

This method assumes vertices are numbered 0..max_vertex. For sparse graphs, V \ U may contain vertex IDs that don’t exist in the graph.

Examples

use ruvector_mincut::instance::witness::WitnessHandle;
use roaring::RoaringBitmap;
use std::collections::HashSet;

let mut membership = RoaringBitmap::new();
membership.insert(1);
membership.insert(2);

let witness = WitnessHandle::new(1, membership, 3);
let (u, _v_minus_u) = witness.materialize_partition();

assert!(u.contains(&1));
assert!(u.contains(&2));
assert!(!u.contains(&3));

pub fn cardinality(&self) -> u64

Get the cardinality of the cut set U

Examples

use ruvector_mincut::instance::witness::WitnessHandle;
use roaring::RoaringBitmap;

let witness = WitnessHandle::new(1, RoaringBitmap::from_iter([1u32, 2u32, 3u32]), 5);
assert_eq!(witness.cardinality(), 3);

Trait Implementations

impl Clone for WitnessHandle

fn clone(&self) -> WitnessHandle

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for WitnessHandle

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

Formats the value using the given formatter.

impl PartialEq for WitnessHandle

fn eq(&self, other: &Self) -> bool

Fast equality check using hash

First compares hashes (O(1)), then falls back to full comparison if needed.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Witness for WitnessHandle

fn contains(&self, v: VertexId) -> bool

Check if vertex is in the cut set U

fn boundary_size(&self) -> u64

Get boundary size |δ(U)|

fn materialize_partition(&self) -> (HashSet<VertexId>, HashSet<VertexId>)

Materialize full partition (expensive)

fn seed(&self) -> VertexId

Get the seed vertex

fn cardinality(&self) -> u64

Get cardinality of U

impl Eq for WitnessHandle