Crate ruvector_mincut 

RuVector MinCut

Subpolynomial-time dynamic minimum cut algorithm with real-time monitoring.

This crate provides efficient algorithms for maintaining minimum cuts in dynamic graphs with edge insertions and deletions.

Features

• Exact Algorithm: O(n^{o(1)}) amortized update time for cuts up to 2^{O((log n)^{3/4})}
• Approximate Algorithm: (1+ε)-approximate cuts via graph sparsification
• Real-Time Monitoring: Event-driven notifications with configurable thresholds
• Thread-Safe: Concurrent reads with exclusive writes

Quick Start

use ruvector_mincut::{MinCutBuilder, DynamicMinCut};

// Create a dynamic minimum cut structure
let mut mincut = MinCutBuilder::new()
    .exact()
    .with_edges(vec![(1, 2, 1.0), (2, 3, 1.0), (3, 1, 1.0)])
    .build()
    .expect("Failed to build");

// Query the minimum cut
println!("Min cut: {}", mincut.min_cut_value());

// Insert a new edge
mincut.insert_edge(3, 4, 1.0).expect("Insert failed");

// Delete an existing edge
let _ = mincut.delete_edge(2, 3);

Architecture

The crate is organized into several modules:

• graph: Dynamic graph representation with efficient operations
• algorithm: Core minimum cut algorithms (exact and approximate)
• tree: Hierarchical decomposition for subpolynomial updates
• linkcut: Link-cut trees for dynamic connectivity
• euler: Euler tour trees for tree operations
• sparsify: Graph sparsification for approximate cuts
• expander: Expander decomposition for subpolynomial updates
• monitoring: Real-time event monitoring (feature-gated)

Feature Flags

• exact - Exact minimum cut algorithm (enabled by default)
• approximate - (1+ε)-approximate algorithm (enabled by default)
• monitoring - Real-time monitoring with callbacks (optional)
• integration - GraphDB integration (optional)
• simd - SIMD optimizations (optional)

Examples

Basic Usage

use ruvector_mincut::prelude::*;

let mut mincut = MinCutBuilder::new()
    .with_edges(vec![
        (1, 2, 1.0),
        (2, 3, 1.0),
        (3, 1, 1.0),
    ])
    .build()
    .unwrap();

assert_eq!(mincut.min_cut_value(), 2.0);

Approximate Algorithm

use ruvector_mincut::prelude::*;

let mincut = MinCutBuilder::new()
    .approximate(0.1) // 10% approximation
    .with_edges(vec![(1, 2, 1.0), (2, 3, 1.0)])
    .build()
    .unwrap();

let result = mincut.min_cut();
assert!(!result.is_exact);
assert_eq!(result.approximation_ratio, 1.1);

Real-Time Monitoring

#[cfg(feature = "monitoring")]
use ruvector_mincut::{MinCutBuilder, MonitorBuilder, EventType};

let mut mincut = MinCutBuilder::new()
    .with_edges(vec![(1, 2, 1.0)])
    .build()
    .unwrap();

let monitor = MonitorBuilder::new()
    .threshold("low", 0.5, true)
    .on_event(|event| {
        println!("Cut changed: {:?}", event.event_type);
    })
    .build();

// Monitor will fire callbacks on updates
mincut.insert_edge(2, 3, 1.0).unwrap();

Re-exports

pub use error::MinCutError;

pub use error::Result;

pub use graph::DynamicGraph;

pub use graph::Edge;

pub use graph::GraphStats;

pub use graph::VertexId;

pub use graph::EdgeId;

pub use graph::Weight;

pub use algorithm::DynamicMinCut;

pub use algorithm::MinCutBuilder;

pub use algorithm::MinCutConfig;

pub use algorithm::MinCutResult;

pub use algorithm::AlgorithmStats;

pub use algorithm::approximate::ApproxMinCut;

pub use algorithm::approximate::ApproxMinCutConfig;

pub use algorithm::approximate::ApproxMinCutResult;

pub use algorithm::approximate::ApproxMinCutStats;

pub use tree::HierarchicalDecomposition;

pub use tree::DecompositionNode;

pub use tree::LevelInfo;

pub use witness::WitnessTree;

pub use witness::LazyWitnessTree;

pub use witness::EdgeWitness;

pub use linkcut::LinkCutTree;

pub use euler::EulerTourTree;

pub use sparsify::SparseGraph;

pub use sparsify::SparsifyConfig;

pub use expander::ExpanderDecomposition;

pub use expander::ExpanderComponent;

pub use expander::Conductance;

pub use localkcut::LocalKCut;

pub use localkcut::LocalCutResult;

pub use localkcut::EdgeColor;

pub use localkcut::ColorMask;

pub use localkcut::ForestPacking;

pub use localkcut::LocalKCutQuery;

pub use localkcut::LocalKCutResult as PaperLocalKCutResult;

pub use localkcut::LocalKCutOracle;

pub use localkcut::DeterministicLocalKCut;

pub use localkcut::DeterministicFamilyGenerator;

pub use connectivity::DynamicConnectivity;

pub use connectivity::polylog::PolylogConnectivity;

pub use connectivity::polylog::PolylogStats;

pub use instance::ProperCutInstance;

pub use instance::InstanceResult;

pub use instance::WitnessHandle;

pub use instance::StubInstance;

pub use instance::BoundedInstance;

pub use wrapper::MinCutWrapper;

pub use certificate::CutCertificate;

pub use certificate::CertificateError;

pub use certificate::CertLocalKCutQuery;

pub use certificate::LocalKCutResponse;

pub use certificate::LocalKCutResultSummary;

pub use certificate::UpdateTrigger;

pub use certificate::UpdateType;

pub use certificate::AuditLogger;

pub use certificate::AuditEntry;

pub use certificate::AuditEntryType;

pub use certificate::AuditData;

pub use cluster::ClusterHierarchy;

pub use cluster::Cluster;

pub use cluster::hierarchy::ThreeLevelHierarchy;

pub use cluster::hierarchy::Expander;

pub use cluster::hierarchy::Precluster;

pub use cluster::hierarchy::HierarchyCluster;

pub use cluster::hierarchy::MirrorCut;

pub use cluster::hierarchy::HierarchyConfig;

pub use cluster::hierarchy::HierarchyStats;

pub use fragment::Fragment;

pub use fragment::FragmentResult;

pub use fragment::FragmentingAlgorithm;

pub use fragmentation::Fragmentation;

pub use fragmentation::FragmentationConfig;

pub use fragmentation::TrimResult;

pub use fragmentation::Fragment as FragmentationFragment;

pub use compact::BitSet256;

pub use compact::CompactEdge;

pub use compact::CompactWitness;

pub use compact::CompactAdjacency;

pub use compact::CompactCoreState;

pub use compact::CoreResult;

pub use compact::CompactVertexId;

pub use compact::CompactEdgeId;

pub use compact::MAX_VERTICES_PER_CORE;

pub use compact::MAX_EDGES_PER_CORE;

pub use parallel::NUM_CORES;

pub use parallel::RANGES_PER_CORE;

pub use parallel::TOTAL_RANGES;

pub use parallel::RANGE_FACTOR;

pub use parallel::CoreStrategy;

pub use parallel::CoreMessage;

pub use parallel::WorkItem;

pub use parallel::SharedCoordinator;

pub use parallel::CoreDistributor;

pub use parallel::CoreExecutor;

pub use parallel::ResultAggregator;

pub use parallel::compute_core_range;

pub use integration::RuVectorGraphAnalyzer;

pub use integration::CommunityDetector;

pub use integration::GraphPartitioner;

pub use snn::LIFNeuron;

pub use snn::NeuronState;

pub use snn::NeuronConfig;

pub use snn::SpikeTrain;

pub use snn::Synapse;

pub use snn::STDPConfig;

pub use snn::SynapseMatrix;

pub use snn::SpikingNetwork;

pub use snn::NetworkConfig;

pub use snn::LayerConfig;

pub use snn::AttractorDynamics;

pub use snn::EnergyLandscape;

pub use snn::AttractorConfig;

pub use snn::MetaCognitiveMinCut;

pub use snn::MetaAction;

pub use snn::MetaLevel;

pub use snn::StrangeLoopConfig;

pub use snn::CausalDiscoverySNN;

pub use snn::CausalGraph;

pub use snn::CausalRelation;

pub use snn::CausalConfig;

pub use snn::TimeCrystalCPG;

pub use snn::OscillatorNeuron;

pub use snn::PhaseTopology;

pub use snn::CPGConfig;

pub use snn::MorphogeneticSNN;

pub use snn::GrowthRules;

pub use snn::TuringPattern;

pub use snn::MorphConfig;

pub use snn::NeuralGraphOptimizer;

pub use snn::PolicySNN;

pub use snn::ValueNetwork;

pub use snn::OptimizerConfig;

pub use snn::OptimizationResult;

pub use snn::CognitiveMinCutEngine;

pub use snn::EngineConfig;

pub use snn::EngineMetrics;

pub use snn::Spike;

pub use snn::SimTime;

pub use snn::SNNMinCutConfig;

Modules

algorithm

Core Dynamic Minimum Cut Algorithm

certificate

Certificate system for cut verification

cluster

Multi-level Cluster Hierarchy for Dynamic Minimum Cut

compact

Compact data structures for 8KB WASM cores

connectivity

Dynamic Connectivity for minimum cut wrapper

error

Error types for the dynamic minimum cut algorithm

euler

Euler Tour Trees for dynamic tree operations

expander

Expander Decomposition for Subpolynomial Dynamic Min-Cut

fragment

Fragmenting Algorithm for Dynamic Minimum Cut

fragmentation

Fragmentation Algorithm for Graph Decomposition

graph

Graph representation for dynamic minimum cut

instance

Instance module for bounded-range minimum cut

integration

RuVector Integration Layer

linkcut

Link-Cut Trees for dynamic tree operations

localkcut

Deterministic Local K-Cut Algorithm

parallel

Parallel distribution for 256-core agentic chip

pool

Memory pools for BFS and graph traversal allocations

prelude

Prelude module for convenient imports

snn

Spiking Neural Network integration for deep MinCut optimization.

sparsify

Graph Sparsification for Approximate Minimum Cuts

tree

Hierarchical Tree Decomposition for Dynamic Minimum Cut

witness

Witness Trees for Dynamic Minimum Cut

wrapper

Instance Manager for Bounded-Range Dynamic Minimum Cut

Constants

NAME

Crate name

VERSION

Crate version