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

problemreductions/models/graph/
partition_into_forests.rs
