ruvector_mincut/localkcut/

paper_impl.rs

//! Paper-Compliant Local K-Cut Implementation
//!
//! This module implements the exact API specified in the December 2024 paper
//! "Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size"
//! (arxiv:2512.13105)
//!
//! # Key Properties
//!
//! - **Deterministic**: No randomness - same input always produces same output
//! - **Bounded Range**: Searches for cuts with value ≤ budget_k
//! - **Local Exploration**: BFS-based exploration within bounded radius
//! - **Witness-Based**: Returns witnesses that certify found cuts
//!
//! # Algorithm Overview
//!
//! The algorithm performs deterministic BFS from seed vertices:
//! 1. Start from seed vertices
//! 2. Expand outward layer by layer (BFS)
//! 3. Track boundary edges at each layer
//! 4. If boundary ≤ budget at any layer, create witness
//! 5. Return smallest cut found or NoneInLocality

use crate::graph::{DynamicGraph, VertexId};
use crate::instance::WitnessHandle;
use roaring::RoaringBitmap;
use std::collections::{HashSet, VecDeque};

/// Query parameters for local k-cut search
///
/// Specifies the search parameters for finding a local minimum cut:
/// - Where to start (seed vertices)
/// - Maximum cut size to accept (budget)
/// - How far to search (radius)
#[derive(Debug, Clone)]
pub struct LocalKCutQuery {
    /// Seed vertices defining the search region
    ///
    /// The algorithm starts BFS from these vertices. Multiple seeds
    /// allow searching from different starting points.
    pub seed_vertices: Vec<VertexId>,

    /// Maximum acceptable cut value
    ///
    /// The algorithm only returns cuts with value ≤ budget_k.
    /// This bounds the search space and ensures polynomial time.
    pub budget_k: u64,

    /// Maximum search radius (BFS depth)
    ///
    /// Limits how far from the seed vertices to explore.
    /// Larger radius = more thorough search but higher cost.
    pub radius: usize,
}

/// Result of a local k-cut search
///
/// Either finds a cut within budget or reports that no such cut
/// exists in the local region around the seed vertices.
#[derive(Debug, Clone)]
pub enum LocalKCutResult {
    /// Found a cut with value ≤ budget_k
    ///
    /// The witness certifies the cut and can be used to verify
    /// correctness or reconstruct the partition.
    Found {
        /// Handle to the witness certifying this cut
        witness: WitnessHandle,
        /// The actual cut value |δ(U)|
        cut_value: u64,
    },

    /// No cut ≤ budget_k found in the local region
    ///
    /// This does not mean no such cut exists globally, only that
    /// none was found within the search radius from the seeds.
    NoneInLocality,
}

/// Oracle trait for local k-cut queries
///
/// Implementations of this trait can answer local k-cut queries
/// deterministically. The trait is thread-safe to support parallel
/// queries across multiple regions.
pub trait LocalKCutOracle: Send + Sync {
    /// Search for a local minimum cut satisfying the query
    ///
    /// # Arguments
    ///
    /// * `graph` - The graph to search in
    /// * `query` - Query parameters (seeds, budget, radius)
    ///
    /// # Returns
    ///
    /// Either a witness for a cut ≤ budget_k, or NoneInLocality
    ///
    /// # Determinism
    ///
    /// For the same graph and query, this method MUST always return
    /// the same result. No randomness is allowed.
    fn search(&self, graph: &DynamicGraph, query: LocalKCutQuery) -> LocalKCutResult;
}

/// Deterministic family generator for seed selection
///
/// Generates deterministic families of vertex sets for the derandomized
/// local k-cut algorithm. Uses vertex ordering to ensure determinism.
#[derive(Debug, Clone)]
pub struct DeterministicFamilyGenerator {
    /// Maximum family size
    max_size: usize,
}

impl DeterministicFamilyGenerator {
    /// Create a new deterministic family generator
    ///
    /// # Arguments
    ///
    /// * `max_size` - Maximum size of generated families
    ///
    /// # Returns
    ///
    /// A new generator with deterministic properties
    pub fn new(max_size: usize) -> Self {
        Self { max_size }
    }

    /// Generate deterministic seed vertices from a vertex
    ///
    /// Uses the vertex ID and its neighbors to generate a deterministic
    /// set of seed vertices for exploration.
    ///
    /// # Arguments
    ///
    /// * `graph` - The graph
    /// * `v` - Starting vertex
    ///
    /// # Returns
    ///
    /// A deterministic set of seed vertices including v
    pub fn generate_seeds(&self, graph: &DynamicGraph, v: VertexId) -> Vec<VertexId> {
        let mut seeds = vec![v];

        // Deterministically select neighbors based on vertex ID ordering
        let mut neighbors: Vec<_> = graph.neighbors(v)
            .into_iter()
            .map(|(neighbor, _)| neighbor)
            .collect();

        // Sort for determinism
        neighbors.sort_unstable();

        // Take up to max_size seeds
        for &neighbor in neighbors.iter().take(self.max_size.saturating_sub(1)) {
            seeds.push(neighbor);
        }

        seeds
    }
}

impl Default for DeterministicFamilyGenerator {
    fn default() -> Self {
        Self::new(4)
    }
}

/// Deterministic Local K-Cut algorithm
///
/// Implements the LocalKCutOracle trait using a deterministic BFS-based
/// exploration strategy. The algorithm:
///
/// 1. Starts BFS from seed vertices
/// 2. Explores outward layer by layer
/// 3. Tracks boundary size at each layer
/// 4. Returns the smallest cut found ≤ budget
///
/// # Determinism
///
/// The algorithm is completely deterministic:
/// - BFS order determined by vertex ID ordering
/// - Seed selection based on deterministic family generator
/// - No random sampling or probabilistic choices
///
/// # Time Complexity
///
/// O(radius * (|V| + |E|)) for a single query in the worst case,
/// but typically much faster due to early termination.
#[derive(Debug, Clone)]
pub struct DeterministicLocalKCut {
    /// Maximum radius for local search
    max_radius: usize,

    /// Deterministic family generator for seed selection
    #[allow(dead_code)]
    family_generator: DeterministicFamilyGenerator,
}

impl DeterministicLocalKCut {
    /// Create a new deterministic local k-cut oracle
    ///
    /// # Arguments
    ///
    /// * `max_radius` - Maximum search radius (BFS depth)
    ///
    /// # Returns
    ///
    /// A new oracle instance
    ///
    /// # Examples
    ///
    /// ```
    /// use ruvector_mincut::localkcut::paper_impl::DeterministicLocalKCut;
    ///
    /// let oracle = DeterministicLocalKCut::new(10);
    /// ```
    pub fn new(max_radius: usize) -> Self {
        Self {
            max_radius,
            family_generator: DeterministicFamilyGenerator::default(),
        }
    }

    /// Create with custom family generator
    ///
    /// # Arguments
    ///
    /// * `max_radius` - Maximum search radius
    /// * `family_generator` - Custom family generator
    ///
    /// # Returns
    ///
    /// A new oracle with custom configuration
    pub fn with_family_generator(
        max_radius: usize,
        family_generator: DeterministicFamilyGenerator,
    ) -> Self {
        Self {
            max_radius,
            family_generator,
        }
    }

    /// Perform deterministic BFS exploration from seeds
    ///
    /// Explores the graph layer by layer, tracking the boundary size
    /// at each step. Returns early if a cut within budget is found.
    ///
    /// # Arguments
    ///
    /// * `graph` - The graph to explore
    /// * `seeds` - Starting vertices
    /// * `budget` - Maximum acceptable boundary size
    /// * `radius` - Maximum BFS depth
    ///
    /// # Returns
    ///
    /// Option containing (vertices in cut, boundary size) if found
    fn deterministic_bfs(
        &self,
        graph: &DynamicGraph,
        seeds: &[VertexId],
        budget: u64,
        radius: usize,
    ) -> Option<(HashSet<VertexId>, u64)> {
        if seeds.is_empty() {
            return None;
        }

        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        let mut best_cut: Option<(HashSet<VertexId>, u64)> = None;

        // Initialize BFS with seeds
        for &seed in seeds {
            if graph.has_vertex(seed) {
                visited.insert(seed);
                queue.push_back((seed, 0));
            }
        }

        if visited.is_empty() {
            return None;
        }

        // Track vertices at each layer for deterministic expansion
        let mut current_layer = visited.clone();

        // BFS exploration
        for depth in 0..=radius {
            // Calculate boundary for current visited set
            let boundary_size = self.calculate_boundary(graph, &visited);

            // Check if this is a valid cut within budget
            if boundary_size <= budget && !visited.is_empty() {
                // Ensure it's a proper partition (not all vertices)
                if visited.len() < graph.num_vertices() {
                    // Update best cut if this is better
                    let should_update = match &best_cut {
                        None => true,
                        Some((_, prev_boundary)) => boundary_size < *prev_boundary,
                    };

                    if should_update {
                        best_cut = Some((visited.clone(), boundary_size));
                    }
                }
            }

            // Early termination if we found a perfect cut
            if let Some((_, boundary)) = &best_cut {
                if *boundary == 0 {
                    break;
                }
            }

            // Don't expand beyond radius
            if depth >= radius {
                break;
            }

            // Expand to next layer deterministically
            let mut next_layer = HashSet::new();
            let mut layer_vertices: Vec<_> = current_layer.iter().copied().collect();
            layer_vertices.sort_unstable(); // Deterministic ordering

            for v in layer_vertices {
                // Get neighbors and sort for determinism
                let mut neighbors: Vec<_> = graph.neighbors(v)
                    .into_iter()
                    .map(|(neighbor, _)| neighbor)
                    .filter(|neighbor| !visited.contains(neighbor))
                    .collect();

                neighbors.sort_unstable();

                for neighbor in neighbors {
                    if visited.insert(neighbor) {
                        next_layer.insert(neighbor);
                        queue.push_back((neighbor, depth + 1));
                    }
                }
            }

            current_layer = next_layer;

            // No more vertices to explore
            if current_layer.is_empty() {
                break;
            }
        }

        best_cut
    }

    /// Calculate the boundary size for a vertex set
    ///
    /// Counts edges crossing from the vertex set to its complement.
    ///
    /// # Arguments
    ///
    /// * `graph` - The graph
    /// * `vertex_set` - Set of vertices on one side
    ///
    /// # Returns
    ///
    /// Number of edges crossing the cut
    fn calculate_boundary(&self, graph: &DynamicGraph, vertex_set: &HashSet<VertexId>) -> u64 {
        let mut boundary_edges = HashSet::new();

        for &v in vertex_set {
            for (neighbor, edge_id) in graph.neighbors(v) {
                if !vertex_set.contains(&neighbor) {
                    // Edge crosses the cut
                    boundary_edges.insert(edge_id);
                }
            }
        }

        boundary_edges.len() as u64
    }

    /// Create a witness handle from a cut
    ///
    /// # Arguments
    ///
    /// * `seed` - Seed vertex in the cut
    /// * `vertices` - Vertices in the cut set
    /// * `boundary_size` - Size of the boundary
    ///
    /// # Returns
    ///
    /// A witness handle certifying the cut
    fn create_witness(
        &self,
        seed: VertexId,
        vertices: &HashSet<VertexId>,
        boundary_size: u64,
    ) -> WitnessHandle {
        let mut membership = RoaringBitmap::new();

        for &v in vertices {
            if v <= u32::MAX as u64 {
                membership.insert(v as u32);
            }
        }

        WitnessHandle::new(seed, membership, boundary_size)
    }
}

impl LocalKCutOracle for DeterministicLocalKCut {
    fn search(&self, graph: &DynamicGraph, query: LocalKCutQuery) -> LocalKCutResult {
        // Validate query parameters
        if query.seed_vertices.is_empty() {
            return LocalKCutResult::NoneInLocality;
        }

        // Use query radius, but cap at max_radius
        let radius = query.radius.min(self.max_radius);

        // Perform deterministic BFS exploration
        let result = self.deterministic_bfs(
            graph,
            &query.seed_vertices,
            query.budget_k,
            radius,
        );

        match result {
            Some((vertices, boundary_size)) => {
                // Pick the first seed that's in the vertex set
                let seed = query.seed_vertices.iter()
                    .find(|&&s| vertices.contains(&s))
                    .copied()
                    .unwrap_or(query.seed_vertices[0]);

                let witness = self.create_witness(seed, &vertices, boundary_size);

                LocalKCutResult::Found {
                    witness,
                    cut_value: boundary_size,
                }
            }
            None => LocalKCutResult::NoneInLocality,
        }
    }
}

impl Default for DeterministicLocalKCut {
    fn default() -> Self {
        Self::new(10)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::Arc;

    fn create_simple_graph() -> Arc<DynamicGraph> {
        let graph = DynamicGraph::new();

        // Create a simple path: 1 - 2 - 3 - 4
        graph.insert_edge(1, 2, 1.0).unwrap();
        graph.insert_edge(2, 3, 1.0).unwrap();
        graph.insert_edge(3, 4, 1.0).unwrap();

        Arc::new(graph)
    }

    fn create_triangle_graph() -> Arc<DynamicGraph> {
        let graph = DynamicGraph::new();

        // Triangle: 1 - 2 - 3 - 1
        graph.insert_edge(1, 2, 1.0).unwrap();
        graph.insert_edge(2, 3, 1.0).unwrap();
        graph.insert_edge(3, 1, 1.0).unwrap();

        Arc::new(graph)
    }

    fn create_dumbbell_graph() -> Arc<DynamicGraph> {
        let graph = DynamicGraph::new();

        // Two triangles connected by a bridge
        // Triangle 1: {1, 2, 3}
        graph.insert_edge(1, 2, 1.0).unwrap();
        graph.insert_edge(2, 3, 1.0).unwrap();
        graph.insert_edge(3, 1, 1.0).unwrap();

        // Bridge: 3 - 4
        graph.insert_edge(3, 4, 1.0).unwrap();

        // Triangle 2: {4, 5, 6}
        graph.insert_edge(4, 5, 1.0).unwrap();
        graph.insert_edge(5, 6, 1.0).unwrap();
        graph.insert_edge(6, 4, 1.0).unwrap();

        Arc::new(graph)
    }

    #[test]
    fn test_local_kcut_query_creation() {
        let query = LocalKCutQuery {
            seed_vertices: vec![1, 2, 3],
            budget_k: 10,
            radius: 5,
        };

        assert_eq!(query.seed_vertices.len(), 3);
        assert_eq!(query.budget_k, 10);
        assert_eq!(query.radius, 5);
    }

    #[test]
    fn test_deterministic_family_generator() {
        let graph = create_simple_graph();
        let generator = DeterministicFamilyGenerator::new(3);

        let seeds1 = generator.generate_seeds(&graph, 1);
        let seeds2 = generator.generate_seeds(&graph, 1);

        // Should be deterministic - same input produces same output
        assert_eq!(seeds1, seeds2);

        // Should include the original vertex
        assert!(seeds1.contains(&1));
    }

    #[test]
    fn test_deterministic_local_kcut_creation() {
        let oracle = DeterministicLocalKCut::new(10);
        assert_eq!(oracle.max_radius, 10);

        let default_oracle = DeterministicLocalKCut::default();
        assert_eq!(default_oracle.max_radius, 10);
    }

    #[test]
    fn test_simple_path_cut() {
        let graph = create_simple_graph();
        let oracle = DeterministicLocalKCut::new(5);

        let query = LocalKCutQuery {
            seed_vertices: vec![1],
            budget_k: 2,
            radius: 2,
        };

        let result = oracle.search(&graph, query);

        match result {
            LocalKCutResult::Found { cut_value, witness } => {
                assert!(cut_value <= 2);
                assert!(witness.contains(1));
                assert_eq!(witness.boundary_size(), cut_value);
            }
            LocalKCutResult::NoneInLocality => {
                // Also acceptable - depends on exploration
            }
        }
    }

    #[test]
    fn test_triangle_no_cut() {
        let graph = create_triangle_graph();
        let oracle = DeterministicLocalKCut::new(5);

        // Triangle has min cut = 2, so budget = 1 should fail
        let query = LocalKCutQuery {
            seed_vertices: vec![1],
            budget_k: 1,
            radius: 3,
        };

        let result = oracle.search(&graph, query);

        match result {
            LocalKCutResult::NoneInLocality => {
                // Expected - triangle has no cut with value 1
            }
            LocalKCutResult::Found { cut_value, .. } => {
                // If found, must be within budget
                assert!(cut_value <= 1);
            }
        }
    }

    #[test]
    fn test_dumbbell_bridge_cut() {
        let graph = create_dumbbell_graph();
        let oracle = DeterministicLocalKCut::new(10);

        // Should find the bridge (cut value = 1)
        let query = LocalKCutQuery {
            seed_vertices: vec![1],
            budget_k: 3,
            radius: 10,
        };

        let result = oracle.search(&graph, query);

        match result {
            LocalKCutResult::Found { cut_value, witness } => {
                // Should find bridge with value 1
                assert_eq!(cut_value, 1);
                assert!(witness.contains(1));

                // One triangle should be in the cut
                let cardinality = witness.cardinality();
                assert!(cardinality == 3 || cardinality == 4);
            }
            LocalKCutResult::NoneInLocality => {
                panic!("Should find the bridge cut");
            }
        }
    }

    #[test]
    fn test_determinism() {
        let graph = create_dumbbell_graph();
        let oracle = DeterministicLocalKCut::new(10);

        let query = LocalKCutQuery {
            seed_vertices: vec![1, 2],
            budget_k: 5,
            radius: 5,
        };

        // Run the same query twice
        let result1 = oracle.search(&graph, query.clone());
        let result2 = oracle.search(&graph, query);

        // Results should be identical (deterministic)
        match (result1, result2) {
            (
                LocalKCutResult::Found { cut_value: v1, witness: w1 },
                LocalKCutResult::Found { cut_value: v2, witness: w2 },
            ) => {
                assert_eq!(v1, v2);
                assert_eq!(w1.seed(), w2.seed());
                assert_eq!(w1.boundary_size(), w2.boundary_size());
                assert_eq!(w1.cardinality(), w2.cardinality());
            }
            (LocalKCutResult::NoneInLocality, LocalKCutResult::NoneInLocality) => {
                // Both none - deterministic
            }
            _ => {
                panic!("Non-deterministic results!");
            }
        }
    }

    #[test]
    fn test_empty_seeds() {
        let graph = create_simple_graph();
        let oracle = DeterministicLocalKCut::new(5);

        let query = LocalKCutQuery {
            seed_vertices: vec![],
            budget_k: 10,
            radius: 5,
        };

        let result = oracle.search(&graph, query);

        assert!(matches!(result, LocalKCutResult::NoneInLocality));
    }

    #[test]
    fn test_invalid_seed() {
        let graph = create_simple_graph();
        let oracle = DeterministicLocalKCut::new(5);

        // Seed vertex doesn't exist in graph
        let query = LocalKCutQuery {
            seed_vertices: vec![999],
            budget_k: 10,
            radius: 5,
        };

        let result = oracle.search(&graph, query);

        assert!(matches!(result, LocalKCutResult::NoneInLocality));
    }

    #[test]
    fn test_zero_radius() {
        let graph = create_simple_graph();
        let oracle = DeterministicLocalKCut::new(5);

        let query = LocalKCutQuery {
            seed_vertices: vec![1],
            budget_k: 10,
            radius: 0,
        };

        let result = oracle.search(&graph, query);

        // With radius 0, should only consider the seed vertex
        match result {
            LocalKCutResult::Found { witness, .. } => {
                assert_eq!(witness.cardinality(), 1);
                assert!(witness.contains(1));
            }
            LocalKCutResult::NoneInLocality => {
                // Also acceptable
            }
        }
    }

    #[test]
    fn test_boundary_calculation() {
        let graph = create_dumbbell_graph();
        let oracle = DeterministicLocalKCut::new(5);

        // Triangle vertices {1, 2, 3}
        let mut vertices = HashSet::new();
        vertices.insert(1);
        vertices.insert(2);
        vertices.insert(3);

        let boundary = oracle.calculate_boundary(&graph, &vertices);

        // Should have exactly 1 boundary edge (the bridge 3-4)
        assert_eq!(boundary, 1);
    }

    #[test]
    fn test_witness_creation() {
        let oracle = DeterministicLocalKCut::new(5);

        let mut vertices = HashSet::new();
        vertices.insert(1);
        vertices.insert(2);
        vertices.insert(3);

        let witness = oracle.create_witness(1, &vertices, 5);

        assert_eq!(witness.seed(), 1);
        assert_eq!(witness.boundary_size(), 5);
        assert_eq!(witness.cardinality(), 3);
        assert!(witness.contains(1));
        assert!(witness.contains(2));
        assert!(witness.contains(3));
        assert!(!witness.contains(4));
    }

    #[test]
    fn test_multiple_seeds() {
        let graph = create_dumbbell_graph();
        let oracle = DeterministicLocalKCut::new(10);

        let query = LocalKCutQuery {
            seed_vertices: vec![1, 2, 3],
            budget_k: 5,
            radius: 5,
        };

        let result = oracle.search(&graph, query);

        match result {
            LocalKCutResult::Found { witness, .. } => {
                // Witness should contain at least one of the seeds
                let contains_seed = witness.contains(1)
                    || witness.contains(2)
                    || witness.contains(3);
                assert!(contains_seed);
            }
            LocalKCutResult::NoneInLocality => {
                // Acceptable
            }
        }
    }

    #[test]
    fn test_budget_enforcement() {
        let graph = create_triangle_graph();
        let oracle = DeterministicLocalKCut::new(5);

        let query = LocalKCutQuery {
            seed_vertices: vec![1],
            budget_k: 1,
            radius: 5,
        };

        let result = oracle.search(&graph, query);

        // If a cut is found, it MUST respect the budget
        if let LocalKCutResult::Found { cut_value, .. } = result {
            assert!(cut_value <= 1);
        }
    }

    #[test]
    fn test_large_radius() {
        let graph = create_simple_graph();
        let oracle = DeterministicLocalKCut::new(5);

        // Request radius larger than max_radius
        let query = LocalKCutQuery {
            seed_vertices: vec![1],
            budget_k: 10,
            radius: 100,
        };

        // Should not panic, should cap at max_radius
        let _result = oracle.search(&graph, query);
    }

    #[test]
    fn test_witness_properties() {
        let graph = create_dumbbell_graph();
        let oracle = DeterministicLocalKCut::new(10);

        let query = LocalKCutQuery {
            seed_vertices: vec![1],
            budget_k: 5,
            radius: 5,
        };

        if let LocalKCutResult::Found { witness, cut_value } = oracle.search(&graph, query) {
            // Witness boundary size should match cut value
            assert_eq!(witness.boundary_size(), cut_value);

            // Witness should be non-empty
            assert!(witness.cardinality() > 0);

            // Seed should be in witness
            assert!(witness.contains(witness.seed()));
        }
    }
}