problemreductions/models/graph/
kclique.rs

1//! KClique problem implementation.
2//!
3//! KClique is the decision version of Clique: determine whether a graph
4//! contains a clique of size at least `k`.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "KClique",
14        display_name: "k-Clique",
15        aliases: &["Clique"],
16        dimensions: &[VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"])],
17        category: crate::registry::ProblemCategory::Graph,
18        module_path: module_path!(),
19        description: "Determine whether a graph contains a clique of size at least k",
20        fields: KCliqueCreateSpec::FIELDS,
21    }
22}
23
24/// The k-Clique decision problem.
25///
26/// Given a graph `G = (V, E)` and a positive integer `k`, determine whether
27/// there exists a subset `K ⊆ V` of size at least `k` such that every pair of
28/// distinct vertices in `K` is adjacent.
29#[derive(Debug, Clone, Serialize, Deserialize)]
30#[serde(try_from = "KCliqueData<G>")]
31#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
32pub struct KClique<G> {
33    graph: G,
34    k: usize,
35}
36
37#[derive(Deserialize)]
38#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
39struct KCliqueData<G> {
40    graph: G,
41    k: usize,
42}
43
44impl<G> TryFrom<KCliqueData<G>> for KClique<G>
45where
46    G: Graph,
47{
48    type Error = crate::registry::ConstructionError;
49
50    fn try_from(data: KCliqueData<G>) -> Result<Self, Self::Error> {
51        Self::try_new(data.graph, data.k)
52    }
53}
54
55#[derive(Debug, Deserialize, crate::CreateSpec)]
56struct KCliqueCreateSpec {
57    #[create(codec = "edge-list")]
58    graph: Vec<(usize, usize)>,
59    num_vertices: Option<usize>,
60    k: usize,
61}
62
63impl TryFrom<KCliqueCreateSpec> for KClique<SimpleGraph> {
64    type Error = crate::registry::ConstructionError;
65    fn try_from(spec: KCliqueCreateSpec) -> Result<Self, Self::Error> {
66        if spec.graph.is_empty() && spec.num_vertices.is_none() {
67            return Err("num_vertices is required for an empty graph".into());
68        }
69        for &(u, v) in &spec.graph {
70            if u == v {
71                return Err(format!("self-loop {u}-{v} is not allowed").into());
72            }
73        }
74        let inferred = spec
75            .graph
76            .iter()
77            .flat_map(|&(u, v)| [u, v])
78            .max()
79            .map(|v| v.checked_add(1).ok_or("vertex count overflows usize"))
80            .transpose()?
81            .unwrap_or(0);
82        let count = spec.num_vertices.unwrap_or(inferred);
83        if count < inferred {
84            return Err("num_vertices is too small for graph endpoints".into());
85        }
86        Self::try_new(SimpleGraph::new(count, spec.graph), spec.k)
87    }
88}
89
90impl<G: Graph> KClique<G> {
91    /// Create a new k-Clique problem instance.
92    pub fn new(graph: G, k: usize) -> Self {
93        Self::try_new(graph, k).unwrap_or_else(|error| panic!("{error}"))
94    }
95
96    fn try_new(graph: G, k: usize) -> Result<Self, crate::registry::ConstructionError> {
97        if k == 0 {
98            return Err("k must be positive".into());
99        }
100        if k > graph.num_vertices() {
101            return Err("k must be <= graph num_vertices".into());
102        }
103        Ok(Self { graph, k })
104    }
105
106    /// Get a reference to the underlying graph.
107    pub fn graph(&self) -> &G {
108        &self.graph
109    }
110
111    /// Get the clique-size threshold.
112    pub fn k(&self) -> usize {
113        self.k
114    }
115
116    /// Get the number of vertices in the underlying graph.
117    pub fn num_vertices(&self) -> usize {
118        self.graph.num_vertices()
119    }
120
121    /// Get the number of edges in the underlying graph.
122    pub fn num_edges(&self) -> usize {
123        self.graph.num_edges()
124    }
125
126    /// Check whether a configuration is a valid witness.
127    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
128        is_kclique_config(&self.graph, config, self.k)
129    }
130
131    /// Build a binary selection config from the listed vertices.
132    pub fn config_from_vertices(num_vertices: usize, selected_vertices: &[usize]) -> Vec<bool> {
133        let mut config = vec![false; num_vertices];
134        for &vertex in selected_vertices {
135            config[vertex] = true;
136        }
137        config
138    }
139
140    /// Convenience wrapper around [`Self::config_from_vertices`] using `self.num_vertices()`.
141    pub fn config_from_selected_vertices(&self, selected_vertices: &[usize]) -> Vec<bool> {
142        Self::config_from_vertices(self.num_vertices(), selected_vertices)
143    }
144}
145
146impl<G> Problem for KClique<G>
147where
148    G: Graph + crate::variant::VariantParam,
149{
150    const NAME: &'static str = "KClique";
151    type Solution = Vec<bool>;
152    type Value = crate::types::Or;
153
154    crate::problem_parameters![
155        ("k", k),
156        ("num_edges", num_edges),
157        ("num_vertices", num_vertices),
158    ];
159
160    fn variant() -> Vec<(&'static str, &'static str)> {
161        crate::variant_params![G]
162    }
163
164    fn evaluate(
165        &self,
166        config: &Self::Solution,
167    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
168        if config.len() != self.graph.num_vertices() {
169            return Err(crate::traits::EvaluationError::InvalidConfiguration(
170                "vertex-selection length does not match the graph".into(),
171            ));
172        }
173        Ok(crate::types::Or(is_kclique_config(
174            &self.graph,
175            config,
176            self.k,
177        )))
178    }
179}
180
181impl<G> crate::solvers::BruteForceProblem for KClique<G>
182where
183    G: Graph + crate::variant::VariantParam,
184{
185    fn dimensions(&self) -> Vec<usize> {
186        vec![2; self.graph.num_vertices()]
187    }
188}
189
190fn is_kclique_config<G: Graph>(graph: &G, config: &[bool], k: usize) -> bool {
191    if config.len() != graph.num_vertices() {
192        return false;
193    }
194
195    let selected: Vec<usize> = config
196        .iter()
197        .enumerate()
198        .filter_map(|(index, &selected)| selected.then_some(index))
199        .collect();
200
201    if selected.len() < k {
202        return false;
203    }
204
205    for i in 0..selected.len() {
206        for j in (i + 1)..selected.len() {
207            if !graph.has_edge(selected[i], selected[j]) {
208                return false;
209            }
210        }
211    }
212    true
213}
214
215crate::impl_random_generate!(
216    KClique<SimpleGraph>,
217    crate::random::CliqueRandomSpec,
218    |spec| {
219        if spec.k == 0 || spec.k > spec.num_vertices {
220            return Err(format!(
221                "k must be between 1 and num_vertices ({})",
222                spec.num_vertices
223            )
224            .into());
225        }
226        Ok(KClique::new(spec.graph()?, spec.k))
227    }
228);
229
230crate::declare_variants! {
231    default KClique<SimpleGraph> => "1.1996^num_vertices" create KCliqueCreateSpec random,
232}
233
234crate::register_brute_force! {
235    KClique<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
236}
237
238#[cfg(feature = "example-db")]
239pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
240    vec![crate::example_db::specs::ModelExampleSpec {
241        id: "kclique_simplegraph",
242        instance: Box::new(KClique::new(
243            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
244            3,
245        )),
246        optimal_config: serde_json::json!(vec![false, false, true, true, true]),
247        optimal_value: serde_json::json!(true),
248    }]
249}
250
251#[cfg(test)]
252#[path = "../../unit_tests/models/graph/kclique.rs"]
253mod tests;
problemreductions/models/graph/kclique.rs

problemreductions/models/graph/
kclique.rs
