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)]
60pub struct MaximumClique<G, W> {
61    /// The underlying graph.
62    graph: G,
63    /// Weights for each vertex.
64    weights: Vec<W>,
65}
66
67#[derive(Debug, Deserialize, crate::CreateSpec)]
68struct MaximumCliqueCreateSpec<W> {
69    /// The underlying graph G=(V,E).
70    graph: SimpleGraph,
71    /// Vertex weights w: V -> R.
72    weights: Vec<W>,
73}
74
75impl<W: Clone + Default> TryFrom<MaximumCliqueCreateSpec<W>> for MaximumClique<SimpleGraph, W> {
76    type Error = crate::registry::ConstructionError;
77    fn try_from(spec: MaximumCliqueCreateSpec<W>) -> Result<Self, Self::Error> {
78        if spec.weights.len() != spec.graph.num_vertices() {
79            return Err(format!(
80                "weights has {} entries, expected {}",
81                spec.weights.len(),
82                spec.graph.num_vertices()
83            )
84            .into());
85        }
86        Ok(Self::new(spec.graph, spec.weights))
87    }
88}
89
90impl<G: Graph, W: Clone + Default> MaximumClique<G, W> {
91    /// Create a MaximumClique problem from a graph with given weights.
92    pub fn new(graph: G, weights: Vec<W>) -> Self {
93        assert_eq!(
94            weights.len(),
95            graph.num_vertices(),
96            "weights length must match graph num_vertices"
97        );
98        Self { graph, weights }
99    }
100
101    /// Get a reference to the underlying graph.
102    pub fn graph(&self) -> &G {
103        &self.graph
104    }
105
106    /// Get a reference to the weights.
107    pub fn weights(&self) -> &[W] {
108        &self.weights
109    }
110
111    /// Check if the problem uses a non-unit weight type.
112    pub fn is_weighted(&self) -> bool
113    where
114        W: WeightElement,
115    {
116        !W::IS_UNIT
117    }
118
119    /// Check if a configuration is a valid clique.
120    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
121        is_clique_config(&self.graph, config)
122    }
123}
124
125impl<G: Graph, W: WeightElement> MaximumClique<G, W> {
126    /// Get the number of vertices in the underlying graph.
127    pub fn num_vertices(&self) -> usize {
128        self.graph().num_vertices()
129    }
130
131    /// Get the number of edges in the underlying graph.
132    pub fn num_edges(&self) -> usize {
133        self.graph().num_edges()
134    }
135}
136
137impl<G, W> Problem for MaximumClique<G, W>
138where
139    G: Graph + crate::variant::VariantParam,
140    W: WeightElement + crate::variant::VariantParam,
141{
142    const NAME: &'static str = "MaximumClique";
143    type Solution = Vec<bool>;
144    type Value = Max<W::Sum>;
145
146    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
147
148    fn variant() -> Vec<(&'static str, &'static str)> {
149        crate::variant_params![G, W]
150    }
151
152    fn evaluate(
153        &self,
154        config: &Self::Solution,
155    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
156        if config.len() != self.graph.num_vertices() {
157            return Err(crate::traits::EvaluationError::InvalidConfiguration(
158                "vertex-selection length does not match the graph".into(),
159            ));
160        }
161        Ok({
162            if !is_clique_config(&self.graph, config) {
163                return Ok(Max(None));
164            }
165            let mut total = W::Sum::zero();
166            for (i, &selected) in config.iter().enumerate() {
167                if selected {
168                    total = W::checked_add_to_sum(
169                        total,
170                        self.weights[i].to_sum(),
171                        "summing selected clique weights",
172                    )?;
173                }
174            }
175            Max(Some(total))
176        })
177    }
178}
179
180impl<G, W> crate::solvers::BruteForceProblem for MaximumClique<G, W>
181where
182    G: Graph + crate::variant::VariantParam,
183    W: WeightElement + crate::variant::VariantParam,
184{
185    fn dimensions(&self) -> Vec<usize> {
186        vec![2; self.graph.num_vertices()]
187    }
188}
189
190/// Check if a configuration forms a valid clique.
191fn is_clique_config<G: Graph>(graph: &G, config: &[bool]) -> bool {
192    // Collect all selected vertices
193    let selected: Vec<usize> = config
194        .iter()
195        .enumerate()
196        .filter(|(_, &v)| v)
197        .map(|(i, _)| i)
198        .collect();
199
200    // Check all pairs of selected vertices are adjacent
201    for i in 0..selected.len() {
202        for j in (i + 1)..selected.len() {
203            if !graph.has_edge(selected[i], selected[j]) {
204                return false;
205            }
206        }
207    }
208    true
209}
210
211crate::impl_random_generate!(MaximumClique<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
212    Ok(MaximumClique::new(spec.graph()?, vec![1; spec.num_vertices]))
213});
214crate::impl_random_generate!(MaximumClique<SimpleGraph, One>, crate::random::SimpleGraphRandomSpec, |spec| {
215    Ok(MaximumClique::new(spec.graph()?, vec![One; spec.num_vertices]))
216});
217
218#[derive(Debug, Deserialize, crate::CreateSpec)]
219struct MaximumCliqueOneCreateSpec {
220    /// The underlying graph.
221    graph: SimpleGraph,
222}
223
224impl TryFrom<MaximumCliqueOneCreateSpec> for MaximumClique<SimpleGraph, One> {
225    type Error = crate::registry::ConstructionError;
226    fn try_from(spec: MaximumCliqueOneCreateSpec) -> Result<Self, Self::Error> {
227        let weights = vec![One; spec.graph.num_vertices()];
228        Ok(Self::new(spec.graph, weights))
229    }
230}
231
232crate::declare_variants! {
233    MaximumClique<SimpleGraph, i64> => "1.1996^num_vertices" create MaximumCliqueCreateSpec<i64> random,
234    default MaximumClique<SimpleGraph, One> => "1.1996^num_vertices" create MaximumCliqueOneCreateSpec random,
235}
236
237crate::register_brute_force! {
238    MaximumClique<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
239    MaximumClique<SimpleGraph, One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
240}
241
242#[cfg(feature = "example-db")]
243pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
244    vec![crate::example_db::specs::ModelExampleSpec {
245        id: "maximum_clique_simplegraph",
246        instance: Box::new(MaximumClique::new(
247            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
248            vec![1i64; 5],
249        )),
250        optimal_config: serde_json::json!(vec![false, false, true, true, true]),
251        optimal_value: serde_json::json!(3),
252    }]
253}
254
255/// Check if a set of vertices forms a clique.
256///
257/// # Arguments
258/// * `graph` - The graph
259/// * `selected` - Boolean slice indicating which vertices are selected
260///
261/// # Panics
262/// Panics if `selected.len() != graph.num_vertices()`.
263#[cfg(test)]
264pub(crate) fn is_clique<G: Graph>(graph: &G, selected: &[bool]) -> bool {
265    assert_eq!(
266        selected.len(),
267        graph.num_vertices(),
268        "selected length must match num_vertices"
269    );
270
271    // Collect selected vertices
272    let selected_vertices: Vec<usize> = selected
273        .iter()
274        .enumerate()
275        .filter(|(_, &s)| s)
276        .map(|(i, _)| i)
277        .collect();
278
279    // Check all pairs of selected vertices are adjacent
280    for i in 0..selected_vertices.len() {
281        for j in (i + 1)..selected_vertices.len() {
282            if !graph.has_edge(selected_vertices[i], selected_vertices[j]) {
283                return false;
284            }
285        }
286    }
287    true
288}
289
290#[cfg(test)]
291#[path = "../../unit_tests/models/graph/maximum_clique.rs"]
292mod tests;
problemreductions/models/graph/maximum_clique.rs

problemreductions/models/graph/
maximum_clique.rs
