problemreductions/models/graph/
partition_into_forests.rs

1//! Partition Into Forests problem implementation.
2//!
3//! Given a graph G = (V, E) and a positive integer K, determine whether the
4//! vertex set can be partitioned into K subsets such that the subgraph induced
5//! by each subset is a forest (acyclic graph).
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::variant::VariantParam;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "PartitionIntoForests",
16        display_name: "Partition into Forests",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Partition vertices into K classes each inducing an acyclic subgraph",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26            FieldInfo { name: "num_forests", type_name: "usize", description: "num_forests: number of forest classes K (>= 1)" },
27        ],
28    }
29}
30
31/// The Partition Into Forests problem.
32///
33/// Given a graph G = (V, E) and a positive integer K, determine whether the
34/// vertices can be partitioned into K classes V_1, ..., V_K such that the
35/// subgraph induced by each V_i is a forest (contains no cycle).
36///
37/// # Type Parameters
38///
39/// * `G` - Graph type (e.g., SimpleGraph)
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::graph::PartitionIntoForests;
45/// use problemreductions::topology::SimpleGraph;
46/// use problemreductions::{Problem, BruteForce};
47///
48/// // Graph containing two triangles; K=2 forests suffice
49/// let graph = SimpleGraph::new(6, vec![(0,1),(1,2),(2,0),(2,3),(3,4),(4,5),(5,3)]);
50/// let problem = PartitionIntoForests::new(graph, 2);
51///
52/// let solver = BruteForce::new();
53/// let solution = solver.solve(&problem).unwrap();
54/// assert!(solution.is_some());
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
58pub struct PartitionIntoForests<G> {
59    /// The underlying graph.
60    graph: G,
61    /// Number of forest classes.
62    num_forests: usize,
63}
64
65impl<G: Graph> PartitionIntoForests<G> {
66    /// Create a new Partition Into Forests instance.
67    ///
68    /// # Panics
69    /// Panics if `num_forests` is zero.
70    pub fn new(graph: G, num_forests: usize) -> Self {
71        assert!(num_forests >= 1, "num_forests must be at least 1");
72        Self { graph, num_forests }
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 forest classes.
81    pub fn num_forests(&self) -> usize {
82        self.num_forests
83    }
84
85    /// Get the number of vertices in the underlying graph.
86    pub fn num_vertices(&self) -> usize {
87        self.graph.num_vertices()
88    }
89
90    /// Get the number of edges in the underlying graph.
91    pub fn num_edges(&self) -> usize {
92        self.graph.num_edges()
93    }
94}
95
96impl<G> Problem for PartitionIntoForests<G>
97where
98    G: Graph + VariantParam,
99{
100    const NAME: &'static str = "PartitionIntoForests";
101    type Solution = Vec<usize>;
102    type Value = crate::types::Or;
103
104    crate::problem_parameters![
105        ("num_vertices", num_vertices),
106        ("num_edges", num_edges),
107        ("num_forests", num_forests),
108    ];
109
110    fn variant() -> Vec<(&'static str, &'static str)> {
111        crate::variant_params![G]
112    }
113
114    fn evaluate(
115        &self,
116        config: &Self::Solution,
117    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
118        if config.len() != self.graph.num_vertices() {
119            return Err(crate::traits::EvaluationError::InvalidConfiguration(
120                "partition assignment length does not match the graph vertices".into(),
121            ));
122        }
123        if config.iter().any(|&part| part >= self.num_forests) {
124            return Err(crate::traits::EvaluationError::InvalidConfiguration(
125                "partition assignment contains an out-of-range forest".into(),
126            ));
127        }
128        Ok({
129            crate::types::Or(is_valid_forest_partition(
130                &self.graph,
131                self.num_forests,
132                config,
133            ))
134        })
135    }
136}
137
138impl<G> crate::solvers::BruteForceProblem for PartitionIntoForests<G>
139where
140    G: Graph + VariantParam,
141{
142    fn dimensions(&self) -> Vec<usize> {
143        vec![self.num_forests; self.graph.num_vertices()]
144    }
145}
146
147/// Check whether `config` is a valid K-forest partition of `graph`.
148fn is_valid_forest_partition<G: Graph>(graph: &G, num_forests: usize, config: &[usize]) -> bool {
149    let n = graph.num_vertices();
150
151    // Basic validity checks
152    if config.len() != n {
153        return false;
154    }
155    if config.iter().any(|&c| c >= num_forests) {
156        return false;
157    }
158
159    // For each forest class, verify the induced subgraph is acyclic using union-find.
160    // An undirected graph is acyclic iff union-find never sees an edge (u, v) where
161    // u and v already share a component.
162    let mut parent: Vec<usize> = (0..n).collect();
163
164    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
165        if parent[x] != x {
166            parent[x] = find(parent, parent[x]);
167        }
168        parent[x]
169    }
170
171    for (u, v) in graph.edges() {
172        if config[u] != config[v] {
173            // Edge crosses classes — not in any induced subgraph
174            continue;
175        }
176        // Both u and v are in the same class; check for cycle
177        let ru = find(&mut parent, u);
178        let rv = find(&mut parent, v);
179        if ru == rv {
180            return false; // Cycle detected
181        }
182        parent[ru] = rv; // Union
183    }
184
185    true
186}
187
188crate::declare_variants! {
189    default PartitionIntoForests<SimpleGraph> => "num_forests^num_vertices",
190}
191
192crate::register_brute_force! {
193    PartitionIntoForests<SimpleGraph>,
194}
195
196#[cfg(feature = "example-db")]
197pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
198    vec![crate::example_db::specs::ModelExampleSpec {
199        id: "partition_into_forests_simplegraph",
200        instance: Box::new(PartitionIntoForests::new(
201            SimpleGraph::new(
202                6,
203                vec![(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)],
204            ),
205            2,
206        )),
207        // V0={0,3}: edges from graph in class 0: none among {0,3} → forest
208        // V1={1,2,4,5}: edges (1,2),(3,4) but 3∉V1; edges among V1: (1,2),(4,5) → path forest
209        optimal_config: serde_json::json!(vec![0, 1, 1, 0, 1, 1]),
210        optimal_value: serde_json::json!(true),
211    }]
212}
213
214#[cfg(test)]
215#[path = "../../unit_tests/models/graph/partition_into_forests.rs"]
216mod tests;
problemreductions/models/graph/partition_into_forests.rs

problemreductions/models/graph/
partition_into_forests.rs
