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::{FieldInfo, 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", "i32"]),
21        ],
22        module_path: module_path!(),
23        description: "Find maximum weight clique in a graph",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26            FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
27        ],
28    }
29}
30
31/// The MaximumClique problem.
32///
33/// Given a graph G = (V, E) and weights w_v for each vertex,
34/// find a subset S ⊆ V such that:
35/// - All vertices in S are pairwise adjacent (clique constraint)
36/// - The total weight Σ_{v ∈ S} w_v is maximized
37///
38/// # Type Parameters
39///
40/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`, `UnitDiskGraph`)
41/// * `W` - The weight type (e.g., `i32`, `f64`, `One`)
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::graph::MaximumClique;
47/// use problemreductions::topology::SimpleGraph;
48/// use problemreductions::{Problem, Solver, BruteForce};
49///
50/// // Create a triangle graph (3 vertices, 3 edges - complete graph)
51/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
52/// let problem = MaximumClique::new(graph, vec![1; 3]);
53///
54/// // Solve with brute force
55/// let solver = BruteForce::new();
56/// let solutions = solver.find_all_witnesses(&problem);
57///
58/// // Maximum clique in a triangle (K3) is size 3
59/// assert!(solutions.iter().all(|s| s.iter().sum::<usize>() == 3));
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62pub struct MaximumClique<G, W> {
63    /// The underlying graph.
64    graph: G,
65    /// Weights for each vertex.
66    weights: Vec<W>,
67}
68
69impl<G: Graph, W: Clone + Default> MaximumClique<G, W> {
70    /// Create a MaximumClique problem from a graph with given weights.
71    pub fn new(graph: G, weights: Vec<W>) -> Self {
72        assert_eq!(
73            weights.len(),
74            graph.num_vertices(),
75            "weights length must match graph num_vertices"
76        );
77        Self { graph, weights }
78    }
79
80    /// Get a reference to the underlying graph.
81    pub fn graph(&self) -> &G {
82        &self.graph
83    }
84
85    /// Get a reference to the weights.
86    pub fn weights(&self) -> &[W] {
87        &self.weights
88    }
89
90    /// Check if the problem uses a non-unit weight type.
91    pub fn is_weighted(&self) -> bool
92    where
93        W: WeightElement,
94    {
95        !W::IS_UNIT
96    }
97
98    /// Check if a configuration is a valid clique.
99    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
100        is_clique_config(&self.graph, config)
101    }
102}
103
104impl<G: Graph, W: WeightElement> MaximumClique<G, W> {
105    /// Get the number of vertices in the underlying graph.
106    pub fn num_vertices(&self) -> usize {
107        self.graph().num_vertices()
108    }
109
110    /// Get the number of edges in the underlying graph.
111    pub fn num_edges(&self) -> usize {
112        self.graph().num_edges()
113    }
114}
115
116impl<G, W> Problem for MaximumClique<G, W>
117where
118    G: Graph + crate::variant::VariantParam,
119    W: WeightElement + crate::variant::VariantParam,
120{
121    const NAME: &'static str = "MaximumClique";
122    type Value = Max<W::Sum>;
123
124    fn variant() -> Vec<(&'static str, &'static str)> {
125        crate::variant_params![G, W]
126    }
127
128    fn dims(&self) -> Vec<usize> {
129        vec![2; self.graph.num_vertices()]
130    }
131
132    fn evaluate(&self, config: &[usize]) -> Max<W::Sum> {
133        if !is_clique_config(&self.graph, config) {
134            return Max(None);
135        }
136        let mut total = W::Sum::zero();
137        for (i, &selected) in config.iter().enumerate() {
138            if selected == 1 {
139                total += self.weights[i].to_sum();
140            }
141        }
142        Max(Some(total))
143    }
144}
145
146/// Check if a configuration forms a valid clique.
147fn is_clique_config<G: Graph>(graph: &G, config: &[usize]) -> bool {
148    // Collect all selected vertices
149    let selected: Vec<usize> = config
150        .iter()
151        .enumerate()
152        .filter(|(_, &v)| v == 1)
153        .map(|(i, _)| i)
154        .collect();
155
156    // Check all pairs of selected vertices are adjacent
157    for i in 0..selected.len() {
158        for j in (i + 1)..selected.len() {
159            if !graph.has_edge(selected[i], selected[j]) {
160                return false;
161            }
162        }
163    }
164    true
165}
166
167crate::declare_variants! {
168    MaximumClique<SimpleGraph, i32> => "1.1996^num_vertices",
169    default MaximumClique<SimpleGraph, One> => "1.1996^num_vertices",
170}
171
172#[cfg(feature = "example-db")]
173pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
174    vec![crate::example_db::specs::ModelExampleSpec {
175        id: "maximum_clique_simplegraph_i32",
176        instance: Box::new(MaximumClique::new(
177            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
178            vec![1i32; 5],
179        )),
180        optimal_config: vec![0, 0, 1, 1, 1],
181        optimal_value: serde_json::json!(3),
182    }]
183}
184
185/// Check if a set of vertices forms a clique.
186///
187/// # Arguments
188/// * `graph` - The graph
189/// * `selected` - Boolean slice indicating which vertices are selected
190///
191/// # Panics
192/// Panics if `selected.len() != graph.num_vertices()`.
193#[cfg(test)]
194pub(crate) fn is_clique<G: Graph>(graph: &G, selected: &[bool]) -> bool {
195    assert_eq!(
196        selected.len(),
197        graph.num_vertices(),
198        "selected length must match num_vertices"
199    );
200
201    // Collect selected vertices
202    let selected_vertices: Vec<usize> = selected
203        .iter()
204        .enumerate()
205        .filter(|(_, &s)| s)
206        .map(|(i, _)| i)
207        .collect();
208
209    // Check all pairs of selected vertices are adjacent
210    for i in 0..selected_vertices.len() {
211        for j in (i + 1)..selected_vertices.len() {
212            if !graph.has_edge(selected_vertices[i], selected_vertices[j]) {
213                return false;
214            }
215        }
216    }
217    true
218}
219
220#[cfg(test)]
221#[path = "../../unit_tests/models/graph/maximum_clique.rs"]
222mod tests;
problemreductions/models/graph/maximum_clique.rs

problemreductions/models/graph/
maximum_clique.rs
