problemreductions/models/graph/
graph_partitioning.rs

1//! GraphPartitioning problem implementation.
2//!
3//! The Graph Partitioning (Minimum Bisection) problem asks for a balanced partition
4//! of vertices into two equal halves minimizing the number of crossing edges.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::{OptimizationProblem, Problem};
9use crate::types::{Direction, SolutionSize};
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "GraphPartitioning",
15        module_path: module_path!(),
16        description: "Find minimum cut balanced bisection of a graph",
17        fields: &[
18            FieldInfo { name: "graph", type_name: "G", description: "The undirected graph G=(V,E)" },
19        ],
20    }
21}
22
23/// The Graph Partitioning (Minimum Bisection) problem.
24///
25/// Given an undirected graph G = (V, E) with |V| = n (even),
26/// partition V into two disjoint sets A and B with |A| = |B| = n/2,
27/// minimizing the number of edges crossing the partition.
28///
29/// # Type Parameters
30///
31/// * `G` - The graph type (e.g., `SimpleGraph`)
32///
33/// # Example
34///
35/// ```
36/// use problemreductions::models::graph::GraphPartitioning;
37/// use problemreductions::topology::SimpleGraph;
38/// use problemreductions::types::SolutionSize;
39/// use problemreductions::{Problem, Solver, BruteForce};
40///
41/// // Square graph: 0-1, 1-2, 2-3, 3-0
42/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (3, 0)]);
43/// let problem = GraphPartitioning::new(graph);
44///
45/// let solver = BruteForce::new();
46/// let solutions = solver.find_all_best(&problem);
47///
48/// // Minimum bisection of a 4-cycle: cut = 2
49/// for sol in solutions {
50///     let size = problem.evaluate(&sol);
51///     assert_eq!(size, SolutionSize::Valid(2));
52/// }
53/// ```
54#[derive(Debug, Clone, Serialize, Deserialize)]
55pub struct GraphPartitioning<G> {
56    /// The underlying graph structure.
57    graph: G,
58}
59
60impl<G: Graph> GraphPartitioning<G> {
61    /// Create a GraphPartitioning problem from a graph.
62    ///
63    /// # Arguments
64    /// * `graph` - The undirected graph to partition
65    pub fn new(graph: G) -> Self {
66        Self { graph }
67    }
68
69    /// Get a reference to the underlying graph.
70    pub fn graph(&self) -> &G {
71        &self.graph
72    }
73
74    /// Get the number of vertices in the underlying graph.
75    pub fn num_vertices(&self) -> usize {
76        self.graph.num_vertices()
77    }
78
79    /// Get the number of edges in the underlying graph.
80    pub fn num_edges(&self) -> usize {
81        self.graph.num_edges()
82    }
83}
84
85impl<G> Problem for GraphPartitioning<G>
86where
87    G: Graph + crate::variant::VariantParam,
88{
89    const NAME: &'static str = "GraphPartitioning";
90    type Metric = SolutionSize<i32>;
91
92    fn variant() -> Vec<(&'static str, &'static str)> {
93        crate::variant_params![G]
94    }
95
96    fn dims(&self) -> Vec<usize> {
97        vec![2; self.graph.num_vertices()]
98    }
99
100    fn evaluate(&self, config: &[usize]) -> SolutionSize<i32> {
101        let n = self.graph.num_vertices();
102        if config.len() != n {
103            return SolutionSize::Invalid;
104        }
105        // Balanced bisection requires even n
106        if !n.is_multiple_of(2) {
107            return SolutionSize::Invalid;
108        }
109        // Check balanced: exactly n/2 vertices in partition 1
110        let count_ones = config.iter().filter(|&&x| x == 1).count();
111        if count_ones != n / 2 {
112            return SolutionSize::Invalid;
113        }
114        // Count crossing edges
115        let mut cut = 0i32;
116        for (u, v) in self.graph.edges() {
117            if config[u] != config[v] {
118                cut += 1;
119            }
120        }
121        SolutionSize::Valid(cut)
122    }
123}
124
125impl<G> OptimizationProblem for GraphPartitioning<G>
126where
127    G: Graph + crate::variant::VariantParam,
128{
129    type Value = i32;
130
131    fn direction(&self) -> Direction {
132        Direction::Minimize
133    }
134}
135
136crate::declare_variants! {
137    GraphPartitioning<SimpleGraph> => "2^num_vertices",
138}
139
140#[cfg(test)]
141#[path = "../../unit_tests/models/graph/graph_partitioning.rs"]
142mod tests;
problemreductions/models/graph/graph_partitioning.rs

problemreductions/models/graph/
graph_partitioning.rs
