problemreductions/models/graph/
partition_into_cliques.rs

1//! Partition Into Cliques problem implementation.
2//!
3//! Given a graph G = (V, E) and a positive integer K <= |V|, determine whether
4//! the vertex set can be partitioned into k <= K groups such that the subgraph
5//! induced by each group is a complete subgraph (clique).
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: "PartitionIntoCliques",
16        display_name: "Partition into Cliques",
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 groups each inducing a clique",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26            FieldInfo { name: "num_cliques", type_name: "usize", description: "num_cliques: maximum number of clique groups K (>= 1)" },
27        ],
28    }
29}
30
31/// The Partition Into Cliques problem.
32///
33/// Given a graph G = (V, E) and a positive integer K <= |V|, determine whether
34/// the vertices can be partitioned into k <= K groups V_1, ..., V_k such that
35/// the subgraph induced by each V_i is a complete subgraph (clique).
36///
37/// # Type Parameters
38///
39/// * `G` - Graph type (e.g., SimpleGraph)
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::graph::PartitionIntoCliques;
45/// use problemreductions::topology::SimpleGraph;
46/// use problemreductions::{Problem, BruteForce};
47///
48/// // Two triangles: 0-1-2-0 and 3-4-5-3
49/// let graph = SimpleGraph::new(6, vec![(0,1),(0,2),(1,2),(3,4),(3,5),(4,5)]);
50/// let problem = PartitionIntoCliques::new(graph, 3);
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(try_from = "PartitionIntoCliquesData<G>")]
58#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
59pub struct PartitionIntoCliques<G> {
60    /// The underlying graph.
61    graph: G,
62    /// Maximum number of clique groups.
63    num_cliques: usize,
64}
65
66#[derive(Deserialize)]
67#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
68struct PartitionIntoCliquesData<G> {
69    graph: G,
70    num_cliques: usize,
71}
72
73impl<G> TryFrom<PartitionIntoCliquesData<G>> for PartitionIntoCliques<G>
74where
75    G: Graph,
76{
77    type Error = crate::registry::ConstructionError;
78
79    fn try_from(data: PartitionIntoCliquesData<G>) -> Result<Self, Self::Error> {
80        Self::try_new(data.graph, data.num_cliques)
81    }
82}
83
84impl<G: Graph> PartitionIntoCliques<G> {
85    /// Create a new Partition Into Cliques instance.
86    ///
87    /// # Panics
88    /// Panics if `num_cliques` is zero or greater than `graph.num_vertices()`.
89    pub fn new(graph: G, num_cliques: usize) -> Self {
90        Self::try_new(graph, num_cliques).unwrap_or_else(|error| panic!("{error}"))
91    }
92
93    fn try_new(graph: G, num_cliques: usize) -> Result<Self, crate::registry::ConstructionError> {
94        if num_cliques == 0 {
95            return Err("num_cliques must be at least 1".into());
96        }
97        if num_cliques > graph.num_vertices() {
98            return Err("num_cliques must be at most num_vertices".into());
99        }
100        Ok(Self { graph, num_cliques })
101    }
102
103    /// Get a reference to the underlying graph.
104    pub fn graph(&self) -> &G {
105        &self.graph
106    }
107
108    /// Get the maximum number of clique groups.
109    pub fn num_cliques(&self) -> usize {
110        self.num_cliques
111    }
112
113    /// Get the number of vertices in the underlying graph.
114    pub fn num_vertices(&self) -> usize {
115        self.graph.num_vertices()
116    }
117
118    /// Get the number of edges in the underlying graph.
119    pub fn num_edges(&self) -> usize {
120        self.graph.num_edges()
121    }
122}
123
124impl<G> Problem for PartitionIntoCliques<G>
125where
126    G: Graph + VariantParam,
127{
128    const NAME: &'static str = "PartitionIntoCliques";
129    type Solution = Vec<usize>;
130    type Value = crate::types::Or;
131
132    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
133
134    fn variant() -> Vec<(&'static str, &'static str)> {
135        crate::variant_params![G]
136    }
137
138    fn evaluate(
139        &self,
140        config: &Self::Solution,
141    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
142        if config.len() != self.graph.num_vertices() {
143            return Err(crate::traits::EvaluationError::InvalidConfiguration(
144                "partition assignment length does not match the graph vertices".into(),
145            ));
146        }
147        if config.iter().any(|&part| part >= self.num_cliques) {
148            return Err(crate::traits::EvaluationError::InvalidConfiguration(
149                "partition assignment contains an out-of-range clique".into(),
150            ));
151        }
152        Ok({
153            crate::types::Or(is_valid_clique_partition(
154                &self.graph,
155                self.num_cliques,
156                config,
157            ))
158        })
159    }
160}
161
162impl<G> crate::solvers::BruteForceProblem for PartitionIntoCliques<G>
163where
164    G: Graph + VariantParam,
165{
166    fn dimensions(&self) -> Vec<usize> {
167        vec![self.num_cliques; self.graph.num_vertices()]
168    }
169}
170
171/// Check whether `config` is a valid K-clique partition of `graph`.
172fn is_valid_clique_partition<G: Graph>(graph: &G, num_cliques: usize, config: &[usize]) -> bool {
173    let n = graph.num_vertices();
174
175    // Basic validity checks
176    if config.len() != n {
177        return false;
178    }
179    if config.iter().any(|&c| c >= num_cliques) {
180        return false;
181    }
182
183    // For each group, collect the vertices and check all pairs are adjacent.
184    for group in 0..num_cliques {
185        let members: Vec<usize> = (0..n).filter(|&v| config[v] == group).collect();
186        for i in 0..members.len() {
187            for j in (i + 1)..members.len() {
188                if !graph.has_edge(members[i], members[j]) {
189                    return false;
190                }
191            }
192        }
193    }
194
195    true
196}
197
198crate::declare_variants! {
199    default PartitionIntoCliques<SimpleGraph> => "2^num_vertices",
200}
201
202crate::register_brute_force! {
203    PartitionIntoCliques<SimpleGraph>,
204}
205
206#[cfg(feature = "example-db")]
207pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
208    vec![crate::example_db::specs::ModelExampleSpec {
209        id: "partition_into_cliques_simplegraph",
210        instance: Box::new(PartitionIntoCliques::new(
211            SimpleGraph::new(
212                6,
213                vec![
214                    (0, 1),
215                    (0, 2),
216                    (1, 2),
217                    (3, 4),
218                    (3, 5),
219                    (4, 5),
220                    (0, 3),
221                    (1, 4),
222                    (2, 5),
223                ],
224            ),
225            3,
226        )),
227        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
228        optimal_value: serde_json::json!(true),
229    }]
230}
231
232#[cfg(test)]
233#[path = "../../unit_tests/models/graph/partition_into_cliques.rs"]
234mod tests;
problemreductions/models/graph/partition_into_cliques.rs

problemreductions/models/graph/
partition_into_cliques.rs
