Module tree

ruvector_mincut

Module tree 

Source
Expand description

Hierarchical Tree Decomposition for Dynamic Minimum Cut

Maintains a hierarchy of graph partitions where each level contains increasingly refined cuts. Enables subpolynomial update time.

§Overview

This module implements a hierarchical decomposition of graphs for efficient minimum cut maintenance. The key idea is to build a balanced binary tree over the graph vertices, where each node represents a potential partition of the graph.

§Features

  • Balanced Binary Tree: O(log n) height decomposition
  • Lazy Recomputation: Only recompute dirty nodes after updates
  • LCA-based Updates: Localize updates to affected subtrees
  • Multiple Cut Evaluation: Consider all possible tree-induced partitions

§Example

use std::sync::Arc;
use ruvector_mincut::graph::DynamicGraph;
use ruvector_mincut::tree::HierarchicalDecomposition;

// Create a graph
let graph = Arc::new(DynamicGraph::new());
graph.insert_edge(1, 2, 1.0).unwrap();
graph.insert_edge(2, 3, 1.0).unwrap();
graph.insert_edge(3, 1, 1.0).unwrap();

// Build hierarchical decomposition
let mut decomp = HierarchicalDecomposition::build(graph.clone()).unwrap();

// Get minimum cut
let min_cut = decomp.min_cut_value();
println!("Minimum cut: {}", min_cut);

// Get the partition
let (partition_a, partition_b) = decomp.min_cut_partition();
println!("Partition: {:?} vs {:?}", partition_a, partition_b);

// Handle dynamic updates
graph.insert_edge(1, 4, 2.0).unwrap();
let new_min_cut = decomp.insert_edge(1, 4, 2.0).unwrap();
println!("New minimum cut: {}", new_min_cut);

§Algorithm

  1. Build Phase: Construct a balanced binary tree over graph vertices
  2. Compute Phase: For each node, compute the cut value (edges crossing between node’s vertices and all other vertices)
  3. Query Phase: Return minimum cut over all nodes
  4. Update Phase: Mark affected nodes dirty, recompute only dirty subtrees

§Complexity

  • Build: O(n log n + m) where n = vertices, m = edges
  • Query: O(1)
  • Update: O(log n) nodes recomputed, O(m’) edges examined per node

§Limitations

The balanced binary partitioning may not find the true minimum cut if it requires a partition not represented in the tree structure. For guaranteed minimum cut finding, use the exact algorithm in the algorithm module.

Structs§

DecompositionNode
A node in the hierarchical decomposition tree
HierarchicalDecomposition
The hierarchical decomposition tree
LevelInfo
Level information for the decomposition