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::{FieldInfo, 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        module_path: module_path!(),
18        description: "Determine whether a graph contains a clique of size at least k",
19        fields: &[
20            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
21            FieldInfo { name: "k", type_name: "usize", description: "Minimum clique size threshold" },
22        ],
23    }
24}
25
26/// The k-Clique decision problem.
27///
28/// Given a graph `G = (V, E)` and a positive integer `k`, determine whether
29/// there exists a subset `K ⊆ V` of size at least `k` such that every pair of
30/// distinct vertices in `K` is adjacent.
31#[derive(Debug, Clone, Serialize, Deserialize)]
32pub struct KClique<G> {
33    graph: G,
34    k: usize,
35}
36
37impl<G: Graph> KClique<G> {
38    /// Create a new k-Clique problem instance.
39    pub fn new(graph: G, k: usize) -> Self {
40        assert!(k > 0, "k must be positive");
41        assert!(k <= graph.num_vertices(), "k must be <= graph num_vertices");
42        Self { graph, k }
43    }
44
45    /// Get a reference to the underlying graph.
46    pub fn graph(&self) -> &G {
47        &self.graph
48    }
49
50    /// Get the clique-size threshold.
51    pub fn k(&self) -> usize {
52        self.k
53    }
54
55    /// Get the number of vertices in the underlying graph.
56    pub fn num_vertices(&self) -> usize {
57        self.graph.num_vertices()
58    }
59
60    /// Get the number of edges in the underlying graph.
61    pub fn num_edges(&self) -> usize {
62        self.graph.num_edges()
63    }
64
65    /// Check whether a configuration is a valid witness.
66    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
67        is_kclique_config(&self.graph, config, self.k)
68    }
69
70    /// Build a binary selection config from the listed vertices.
71    pub fn config_from_vertices(num_vertices: usize, selected_vertices: &[usize]) -> Vec<usize> {
72        let mut config = vec![0; num_vertices];
73        for &vertex in selected_vertices {
74            config[vertex] = 1;
75        }
76        config
77    }
78
79    /// Convenience wrapper around [`Self::config_from_vertices`] using `self.num_vertices()`.
80    pub fn config_from_selected_vertices(&self, selected_vertices: &[usize]) -> Vec<usize> {
81        Self::config_from_vertices(self.num_vertices(), selected_vertices)
82    }
83}
84
85impl<G> Problem for KClique<G>
86where
87    G: Graph + crate::variant::VariantParam,
88{
89    const NAME: &'static str = "KClique";
90    type Value = crate::types::Or;
91
92    fn variant() -> Vec<(&'static str, &'static str)> {
93        crate::variant_params![G]
94    }
95
96    fn dims(&self) -> Vec<usize> {
97        vec![2; self.graph.num_vertices()]
98    }
99
100    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
101        crate::types::Or(is_kclique_config(&self.graph, config, self.k))
102    }
103}
104
105fn is_kclique_config<G: Graph>(graph: &G, config: &[usize], k: usize) -> bool {
106    if config.len() != graph.num_vertices() {
107        return false;
108    }
109
110    let selected: Vec<usize> = match config
111        .iter()
112        .enumerate()
113        .map(|(index, &value)| match value {
114            0 => Ok(None),
115            1 => Ok(Some(index)),
116            _ => Err(()),
117        })
118        .collect::<Result<Vec<_>, _>>()
119    {
120        Ok(values) => values.into_iter().flatten().collect(),
121        Err(()) => return false,
122    };
123
124    if selected.len() < k {
125        return false;
126    }
127
128    for i in 0..selected.len() {
129        for j in (i + 1)..selected.len() {
130            if !graph.has_edge(selected[i], selected[j]) {
131                return false;
132            }
133        }
134    }
135    true
136}
137
138crate::declare_variants! {
139    default KClique<SimpleGraph> => "1.1996^num_vertices",
140}
141
142#[cfg(feature = "example-db")]
143pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
144    vec![crate::example_db::specs::ModelExampleSpec {
145        id: "kclique_simplegraph",
146        instance: Box::new(KClique::new(
147            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
148            3,
149        )),
150        optimal_config: vec![0, 0, 1, 1, 1],
151        optimal_value: serde_json::json!(true),
152    }]
153}
154
155#[cfg(test)]
156#[path = "../../unit_tests/models/graph/kclique.rs"]
157mod tests;
problemreductions/models/graph/kclique.rs

problemreductions/models/graph/
kclique.rs
