problemreductions/models/graph/
maximum_edge_weighted_k_clique.rs

1//! Maximum Edge-Weighted k-Clique problem implementation.
2//!
3//! Given a simple undirected graph G = (V, E), edge weights w: E -> R, and an
4//! integer k with 0 <= k <= |V|, find a subset S ⊆ V with |S| = k such that
5//! every two distinct vertices in S are adjacent in G and the total weight of
6//! the induced clique edges is maximized:
7//!
8//! maximize  Σ_{{u,v} ⊆ S, {u,v} ∈ E} w_{uv}.
9//!
10//! Edge weights may be positive, zero, or negative. Cliques of size 0 and 1
11//! are allowed when `k` takes those values, with objective value 0 because no
12//! pair of selected vertices is induced.
13
14use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry, VariantDimension};
15use crate::topology::{Graph, SimpleGraph};
16use crate::traits::Problem;
17use crate::types::{Max, WeightElement};
18use num_traits::Zero;
19use serde::{Deserialize, Serialize};
20
21inventory::submit! {
22    ProblemSchemaEntry {
23        name: "MaximumEdgeWeightedKClique",
24        display_name: "Maximum Edge-Weighted k-Clique",
25        aliases: &[],
26        dimensions: &[VariantDimension::new("weight", "i32", &["i32", "f64"])],
27        module_path: module_path!(),
28        description: "Select exactly k pairwise-adjacent vertices maximizing the total weight of induced clique edges",
29        fields: &[
30            FieldInfo { name: "graph", type_name: "SimpleGraph", description: "The underlying graph G=(V,E)" },
31            FieldInfo { name: "edge_weights", type_name: "Vec<W>", description: "Edge weights in graph edge order" },
32            FieldInfo { name: "k", type_name: "usize", description: "Required clique size" },
33        ],
34    }
35}
36
37inventory::submit! {
38    ProblemSizeFieldEntry {
39        name: "MaximumEdgeWeightedKClique",
40        fields: &["num_vertices", "num_edges"],
41    }
42}
43
44/// The Maximum Edge-Weighted k-Clique problem.
45///
46/// Given a simple undirected graph `G = (V, E)`, edge weights
47/// `w: E -> R`, and an integer `k` with `0 <= k <= |V|`, find a subset
48/// `S ⊆ V` with `|S| = k` such that every two distinct vertices in `S`
49/// are adjacent in `G` and the sum of induced edge weights is maximized.
50///
51/// # Type Parameters
52///
53/// * `W` - Edge weight type (e.g., `i32`, `f64`). The graph is fixed to
54///   [`SimpleGraph`] in the current registered variants.
55///
56/// # Example
57///
58/// ```
59/// use problemreductions::models::graph::MaximumEdgeWeightedKClique;
60/// use problemreductions::topology::SimpleGraph;
61/// use problemreductions::types::Max;
62/// use problemreductions::{BruteForce, Problem, Solver};
63///
64/// // Graph from issue #1020: 4 vertices, triangles {0,1,2} and {0,1,3}.
65/// let graph = SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (0, 3), (1, 3)]);
66/// let weights = vec![5_i32, 4, -1, 1, 0];
67/// let problem = MaximumEdgeWeightedKClique::new(graph, weights, 3);
68/// assert_eq!(BruteForce::new().solve(&problem), Max(Some(8)));
69/// ```
70#[derive(Debug, Clone, Serialize, Deserialize)]
71pub struct MaximumEdgeWeightedKClique<W: WeightElement> {
72    /// The underlying graph.
73    graph: SimpleGraph,
74    /// Edge weights, in the graph's edge iteration order.
75    edge_weights: Vec<W>,
76    /// Required clique size.
77    k: usize,
78}
79
80impl<W: WeightElement> MaximumEdgeWeightedKClique<W> {
81    /// Create a new MaximumEdgeWeightedKClique instance.
82    ///
83    /// # Panics
84    /// Panics if `edge_weights.len()` does not match `graph.num_edges()`, or
85    /// if `k > graph.num_vertices()`.
86    pub fn new(graph: SimpleGraph, edge_weights: Vec<W>, k: usize) -> Self {
87        assert_eq!(
88            edge_weights.len(),
89            graph.num_edges(),
90            "edge_weights length must match graph num_edges"
91        );
92        assert!(
93            k <= graph.num_vertices(),
94            "k = {} must be <= num_vertices = {}",
95            k,
96            graph.num_vertices()
97        );
98        Self {
99            graph,
100            edge_weights,
101            k,
102        }
103    }
104
105    /// Get a reference to the underlying graph.
106    pub fn graph(&self) -> &SimpleGraph {
107        &self.graph
108    }
109
110    /// Get a reference to the edge weights.
111    pub fn edge_weights(&self) -> &[W] {
112        &self.edge_weights
113    }
114
115    /// Get the required clique size.
116    pub fn k(&self) -> usize {
117        self.k
118    }
119
120    /// Number of vertices in the underlying graph.
121    pub fn num_vertices(&self) -> usize {
122        self.graph.num_vertices()
123    }
124
125    /// Number of edges in the underlying graph.
126    pub fn num_edges(&self) -> usize {
127        self.graph.num_edges()
128    }
129
130    /// Check whether the selected vertices form a clique of size exactly `k`.
131    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
132        is_k_clique_config(&self.graph, config, self.k)
133    }
134}
135
136impl<W> Problem for MaximumEdgeWeightedKClique<W>
137where
138    W: WeightElement + crate::variant::VariantParam,
139{
140    const NAME: &'static str = "MaximumEdgeWeightedKClique";
141    type Value = Max<W::Sum>;
142
143    fn variant() -> Vec<(&'static str, &'static str)> {
144        crate::variant_params![W]
145    }
146
147    fn dims(&self) -> Vec<usize> {
148        vec![2; self.graph.num_vertices()]
149    }
150
151    fn evaluate(&self, config: &[usize]) -> Max<W::Sum> {
152        if !is_k_clique_config(&self.graph, config, self.k) {
153            return Max(None);
154        }
155        // Sum weights of edges whose both endpoints are selected.
156        let mut total = W::Sum::zero();
157        for ((u, v), weight) in self.graph.edges().iter().zip(self.edge_weights.iter()) {
158            if config.get(*u).copied().unwrap_or(0) == 1
159                && config.get(*v).copied().unwrap_or(0) == 1
160            {
161                total += weight.to_sum();
162            }
163        }
164        Max(Some(total))
165    }
166}
167
168/// Check whether `config` selects exactly `k` vertices that form a clique.
169fn is_k_clique_config(graph: &SimpleGraph, config: &[usize], k: usize) -> bool {
170    let n = graph.num_vertices();
171    if config.len() != n {
172        return false;
173    }
174    let selected: Vec<usize> = config
175        .iter()
176        .enumerate()
177        .filter(|(_, &v)| v == 1)
178        .map(|(i, _)| i)
179        .collect();
180    if selected.len() != k {
181        return false;
182    }
183    for i in 0..selected.len() {
184        for j in (i + 1)..selected.len() {
185            if !graph.has_edge(selected[i], selected[j]) {
186                return false;
187            }
188        }
189    }
190    true
191}
192
193crate::declare_variants! {
194    default MaximumEdgeWeightedKClique<i32> => "2^num_vertices",
195    MaximumEdgeWeightedKClique<f64>         => "2^num_vertices",
196}
197
198#[cfg(feature = "example-db")]
199pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
200    vec![crate::example_db::specs::ModelExampleSpec {
201        id: "maximum_edge_weighted_k_clique_simplegraph_i32",
202        instance: Box::new(MaximumEdgeWeightedKClique::<i32>::new(
203            SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (0, 3), (1, 3)]),
204            vec![5, 4, -1, 1, 0],
205            3,
206        )),
207        optimal_config: vec![1, 1, 1, 0],
208        optimal_value: serde_json::json!(8),
209    }]
210}
211
212#[cfg(test)]
213#[path = "../../unit_tests/models/graph/maximum_edge_weighted_k_clique.rs"]
214mod tests;
problemreductions/models/graph/maximum_edge_weighted_k_clique.rs

problemreductions/models/graph/
maximum_edge_weighted_k_clique.rs
