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        module_path: module_path!(),
22        description: "Partition vertices into K groups each inducing a clique",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
25            FieldInfo { name: "num_cliques", type_name: "usize", description: "num_cliques: maximum number of clique groups K (>= 1)" },
26        ],
27    }
28}
29
30/// The Partition Into Cliques problem.
31///
32/// Given a graph G = (V, E) and a positive integer K <= |V|, determine whether
33/// the vertices can be partitioned into k <= K groups V_1, ..., V_k such that
34/// the subgraph induced by each V_i is a complete subgraph (clique).
35///
36/// # Type Parameters
37///
38/// * `G` - Graph type (e.g., SimpleGraph)
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::graph::PartitionIntoCliques;
44/// use problemreductions::topology::SimpleGraph;
45/// use problemreductions::{Problem, Solver, BruteForce};
46///
47/// // Two triangles: 0-1-2-0 and 3-4-5-3
48/// let graph = SimpleGraph::new(6, vec![(0,1),(0,2),(1,2),(3,4),(3,5),(4,5)]);
49/// let problem = PartitionIntoCliques::new(graph, 3);
50///
51/// let solver = BruteForce::new();
52/// let solution = solver.find_witness(&problem);
53/// assert!(solution.is_some());
54/// ```
55#[derive(Debug, Clone, Serialize, Deserialize)]
56#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
57pub struct PartitionIntoCliques<G> {
58    /// The underlying graph.
59    graph: G,
60    /// Maximum number of clique groups.
61    num_cliques: usize,
62}
63
64impl<G: Graph> PartitionIntoCliques<G> {
65    /// Create a new Partition Into Cliques instance.
66    ///
67    /// # Panics
68    /// Panics if `num_cliques` is zero or greater than `graph.num_vertices()`.
69    pub fn new(graph: G, num_cliques: usize) -> Self {
70        assert!(num_cliques >= 1, "num_cliques must be at least 1");
71        assert!(
72            num_cliques <= graph.num_vertices(),
73            "num_cliques must be at most num_vertices"
74        );
75        Self { graph, num_cliques }
76    }
77
78    /// Get a reference to the underlying graph.
79    pub fn graph(&self) -> &G {
80        &self.graph
81    }
82
83    /// Get the maximum number of clique groups.
84    pub fn num_cliques(&self) -> usize {
85        self.num_cliques
86    }
87
88    /// Get the number of vertices in the underlying graph.
89    pub fn num_vertices(&self) -> usize {
90        self.graph.num_vertices()
91    }
92
93    /// Get the number of edges in the underlying graph.
94    pub fn num_edges(&self) -> usize {
95        self.graph.num_edges()
96    }
97}
98
99impl<G> Problem for PartitionIntoCliques<G>
100where
101    G: Graph + VariantParam,
102{
103    const NAME: &'static str = "PartitionIntoCliques";
104    type Value = crate::types::Or;
105
106    fn variant() -> Vec<(&'static str, &'static str)> {
107        crate::variant_params![G]
108    }
109
110    fn dims(&self) -> Vec<usize> {
111        vec![self.num_cliques; self.graph.num_vertices()]
112    }
113
114    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
115        crate::types::Or(is_valid_clique_partition(
116            &self.graph,
117            self.num_cliques,
118            config,
119        ))
120    }
121}
122
123/// Check whether `config` is a valid K-clique partition of `graph`.
124fn is_valid_clique_partition<G: Graph>(graph: &G, num_cliques: usize, config: &[usize]) -> bool {
125    let n = graph.num_vertices();
126
127    // Basic validity checks
128    if config.len() != n {
129        return false;
130    }
131    if config.iter().any(|&c| c >= num_cliques) {
132        return false;
133    }
134
135    // For each group, collect the vertices and check all pairs are adjacent.
136    for group in 0..num_cliques {
137        let members: Vec<usize> = (0..n).filter(|&v| config[v] == group).collect();
138        for i in 0..members.len() {
139            for j in (i + 1)..members.len() {
140                if !graph.has_edge(members[i], members[j]) {
141                    return false;
142                }
143            }
144        }
145    }
146
147    true
148}
149
150crate::declare_variants! {
151    default PartitionIntoCliques<SimpleGraph> => "2^num_vertices",
152}
153
154#[cfg(feature = "example-db")]
155pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
156    vec![crate::example_db::specs::ModelExampleSpec {
157        id: "partition_into_cliques_simplegraph",
158        instance: Box::new(PartitionIntoCliques::new(
159            SimpleGraph::new(
160                6,
161                vec![
162                    (0, 1),
163                    (0, 2),
164                    (1, 2),
165                    (3, 4),
166                    (3, 5),
167                    (4, 5),
168                    (0, 3),
169                    (1, 4),
170                    (2, 5),
171                ],
172            ),
173            3,
174        )),
175        optimal_config: vec![0, 0, 0, 1, 1, 1],
176        optimal_value: serde_json::json!(true),
177    }]
178}
179
180#[cfg(test)]
181#[path = "../../unit_tests/models/graph/partition_into_cliques.rs"]
182mod tests;
problemreductions/models/graph/partition_into_cliques.rs

problemreductions/models/graph/
partition_into_cliques.rs
