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

problemreductions/models/graph/
graph_partitioning.rs
