problemreductions/models/graph/
maximum_clique.rs

1//! MaximumClique problem implementation.
2//!
3//! The MaximumClique problem asks for a maximum weight subset of vertices
4//! such that all vertices in the subset are pairwise adjacent.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::{Max, One, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MaximumClique",
16        display_name: "Maximum Clique",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20            VariantDimension::new("weight", "One", &["One", "i64"]),
21        ],
22        category: crate::registry::ProblemCategory::Graph,
23        module_path: module_path!(),
24        description: "Find maximum weight clique in a graph",
25        fields: MaximumCliqueCreateSpec::<One>::FIELDS,
26    }
27}
28
29/// The MaximumClique problem.
30///
31/// Given a graph G = (V, E) and weights w_v for each vertex,
32/// find a subset S ⊆ V such that:
33/// - All vertices in S are pairwise adjacent (clique constraint)
34/// - The total weight Σ_{v ∈ S} w_v is maximized
35///
36/// # Type Parameters
37///
38/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`, `UnitDiskGraph`)
39/// * `W` - The weight type (e.g., `i64`, `f64`, `One`)
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::graph::MaximumClique;
45/// use problemreductions::topology::SimpleGraph;
46/// use problemreductions::{Problem, BruteForce};
47///
48/// // Create a triangle graph (3 vertices, 3 edges - complete graph)
49/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
50/// let problem = MaximumClique::new(graph, vec![1; 3]);
51///
52/// // Solve with brute force
53/// let solver = BruteForce::new();
54/// let solutions = solver.find_all_witnesses(&problem).unwrap();
55///
56/// // Maximum clique in a triangle (K3) is size 3
57/// assert!(solutions.iter().all(|s| s.iter().filter(|&&selected| selected).count() == 3));
58/// ```
59#[derive(Debug, Clone, Serialize, Deserialize)]
60#[serde(try_from = "MaximumCliqueData<G, W>")]
61#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
62pub struct MaximumClique<G, W> {
63    /// The underlying graph.
64    graph: G,
65    /// Weights for each vertex.
66    weights: Vec<W>,
67}
68
69#[derive(Deserialize)]
70struct MaximumCliqueData<G, W> {
71    graph: G,
72    weights: Vec<W>,
73}
74
75impl<G, W> TryFrom<MaximumCliqueData<G, W>> for MaximumClique<G, W>
76where
77    G: Graph,
78    W: Clone + Default,
79{
80    type Error = crate::registry::ConstructionError;
81
82    fn try_from(data: MaximumCliqueData<G, W>) -> Result<Self, Self::Error> {
83        Self::try_new(data.graph, data.weights)
84    }
85}
86
87#[derive(Debug, Deserialize, crate::CreateSpec)]
88struct MaximumCliqueCreateSpec<W> {
89    /// The underlying graph G=(V,E).
90    graph: SimpleGraph,
91    /// Vertex weights w: V -> R.
92    weights: Vec<W>,
93}
94
95impl<W: Clone + Default> TryFrom<MaximumCliqueCreateSpec<W>> for MaximumClique<SimpleGraph, W> {
96    type Error = crate::registry::ConstructionError;
97    fn try_from(spec: MaximumCliqueCreateSpec<W>) -> Result<Self, Self::Error> {
98        Self::try_new(spec.graph, spec.weights)
99    }
100}
101
102impl<G: Graph, W: Clone + Default> MaximumClique<G, W> {
103    /// Create a MaximumClique problem from a graph with given weights.
104    pub fn new(graph: G, weights: Vec<W>) -> Self {
105        Self::try_new(graph, weights).unwrap_or_else(|error| panic!("{error}"))
106    }
107
108    fn try_new(graph: G, weights: Vec<W>) -> Result<Self, crate::registry::ConstructionError> {
109        if weights.len() != graph.num_vertices() {
110            return Err(crate::registry::ConstructionError::length_mismatch(
111                "weights",
112                weights.len(),
113                graph.num_vertices(),
114            ));
115        }
116        Ok(Self { graph, weights })
117    }
118
119    /// Get a reference to the underlying graph.
120    pub fn graph(&self) -> &G {
121        &self.graph
122    }
123
124    /// Get a reference to the weights.
125    pub fn weights(&self) -> &[W] {
126        &self.weights
127    }
128
129    /// Check if the problem uses a non-unit weight type.
130    pub fn is_weighted(&self) -> bool
131    where
132        W: WeightElement,
133    {
134        !W::IS_UNIT
135    }
136
137    /// Check if a configuration is a valid clique.
138    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
139        is_clique_config(&self.graph, config)
140    }
141}
142
143impl<G: Graph, W: WeightElement> MaximumClique<G, W> {
144    /// Get the number of vertices in the underlying graph.
145    pub fn num_vertices(&self) -> usize {
146        self.graph().num_vertices()
147    }
148
149    /// Get the number of edges in the underlying graph.
150    pub fn num_edges(&self) -> usize {
151        self.graph().num_edges()
152    }
153}
154
155impl<G, W> Problem for MaximumClique<G, W>
156where
157    G: Graph + crate::variant::VariantParam,
158    W: WeightElement + crate::variant::VariantParam,
159{
160    const NAME: &'static str = "MaximumClique";
161    type Solution = Vec<bool>;
162    type Value = Max<W::Sum>;
163
164    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
165
166    fn variant() -> Vec<(&'static str, &'static str)> {
167        crate::variant_params![G, W]
168    }
169
170    fn evaluate(
171        &self,
172        config: &Self::Solution,
173    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
174        if config.len() != self.graph.num_vertices() {
175            return Err(crate::traits::EvaluationError::InvalidConfiguration(
176                "vertex-selection length does not match the graph".into(),
177            ));
178        }
179        Ok({
180            if !is_clique_config(&self.graph, config) {
181                return Ok(Max(None));
182            }
183            let mut total = W::Sum::zero();
184            for (i, &selected) in config.iter().enumerate() {
185                if selected {
186                    total = W::checked_add_to_sum(
187                        total,
188                        self.weights[i].to_sum(),
189                        "summing selected clique weights",
190                    )?;
191                }
192            }
193            Max(Some(total))
194        })
195    }
196}
197
198impl<G, W> crate::solvers::BruteForceProblem for MaximumClique<G, W>
199where
200    G: Graph + crate::variant::VariantParam,
201    W: WeightElement + crate::variant::VariantParam,
202{
203    fn dimensions(&self) -> Vec<usize> {
204        vec![2; self.graph.num_vertices()]
205    }
206}
207
208/// Check if a configuration forms a valid clique.
209fn is_clique_config<G: Graph>(graph: &G, config: &[bool]) -> bool {
210    // Collect all selected vertices
211    let selected: Vec<usize> = config
212        .iter()
213        .enumerate()
214        .filter(|(_, &v)| v)
215        .map(|(i, _)| i)
216        .collect();
217
218    // Check all pairs of selected vertices are adjacent
219    for i in 0..selected.len() {
220        for j in (i + 1)..selected.len() {
221            if !graph.has_edge(selected[i], selected[j]) {
222                return false;
223            }
224        }
225    }
226    true
227}
228
229crate::impl_random_generate!(MaximumClique<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
230    Ok(MaximumClique::new(spec.graph()?, vec![1; spec.num_vertices]))
231});
232crate::impl_random_generate!(MaximumClique<SimpleGraph, One>, crate::random::SimpleGraphRandomSpec, |spec| {
233    Ok(MaximumClique::new(spec.graph()?, vec![One; spec.num_vertices]))
234});
235
236#[derive(Debug, Deserialize, crate::CreateSpec)]
237struct MaximumCliqueOneCreateSpec {
238    /// The underlying graph.
239    graph: SimpleGraph,
240}
241
242impl TryFrom<MaximumCliqueOneCreateSpec> for MaximumClique<SimpleGraph, One> {
243    type Error = crate::registry::ConstructionError;
244    fn try_from(spec: MaximumCliqueOneCreateSpec) -> Result<Self, Self::Error> {
245        let weights = vec![One; spec.graph.num_vertices()];
246        Self::try_new(spec.graph, weights)
247    }
248}
249
250crate::declare_variants! {
251    MaximumClique<SimpleGraph, i64> => "1.1996^num_vertices" create MaximumCliqueCreateSpec<i64> random,
252    default MaximumClique<SimpleGraph, One> => "1.1996^num_vertices" create MaximumCliqueOneCreateSpec random,
253}
254
255crate::register_brute_force! {
256    MaximumClique<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
257    MaximumClique<SimpleGraph, One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
258}
259
260#[cfg(feature = "example-db")]
261pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
262    vec![crate::example_db::specs::ModelExampleSpec {
263        id: "maximum_clique_simplegraph",
264        instance: Box::new(MaximumClique::new(
265            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
266            vec![1i64; 5],
267        )),
268        optimal_config: serde_json::json!(vec![false, false, true, true, true]),
269        optimal_value: serde_json::json!(3),
270    }]
271}
272
273/// Check if a set of vertices forms a clique.
274///
275/// # Arguments
276/// * `graph` - The graph
277/// * `selected` - Boolean slice indicating which vertices are selected
278///
279/// # Panics
280/// Panics if `selected.len() != graph.num_vertices()`.
281#[cfg(test)]
282pub(crate) fn is_clique<G: Graph>(graph: &G, selected: &[bool]) -> bool {
283    assert_eq!(
284        selected.len(),
285        graph.num_vertices(),
286        "selected length must match num_vertices"
287    );
288
289    // Collect selected vertices
290    let selected_vertices: Vec<usize> = selected
291        .iter()
292        .enumerate()
293        .filter(|(_, &s)| s)
294        .map(|(i, _)| i)
295        .collect();
296
297    // Check all pairs of selected vertices are adjacent
298    for i in 0..selected_vertices.len() {
299        for j in (i + 1)..selected_vertices.len() {
300            if !graph.has_edge(selected_vertices[i], selected_vertices[j]) {
301                return false;
302            }
303        }
304    }
305    true
306}
307
308#[cfg(test)]
309#[path = "../../unit_tests/models/graph/maximum_clique.rs"]
310mod tests;
problemreductions/models/graph/maximum_clique.rs

problemreductions/models/graph/
maximum_clique.rs
