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

problemreductions/models/graph/
graph_partitioning.rs
