problemreductions/models/graph/
maximum_common_edge_subgraph.rs

1//! Maximum Common Edge Subgraph problem implementation.
2//!
3//! Given two finite directed edge-labelled graphs `G1 = (V1, E1)` and
4//! `G2 = (V2, E2)` with `E_i subset.eq V_i x Sigma x V_i`, find a partial
5//! injective map `f: U1 -> V2`, where `U1 subset.eq V1`, that maximizes the
6//! number of labelled arcs `(u, lambda, v) in E1` such that `u, v in U1` and
7//! `(f(u), lambda, f(v)) in E2`. Edge labels must match exactly and the model
8//! uses set semantics (each preserved arc contributes `1`).
9//!
10//! The configuration vector has length `|V1|`. For each source vertex `u`, the
11//! value `config[u] in {0, ..., |V2| - 1, |V2|}` records which target vertex
12//! `u` is matched to, with the sentinel value `|V2|` denoting "unmatched"
13//! (`bottom`). Feasibility requires injectivity on the matched vertices.
14
15use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry};
16use crate::traits::Problem;
17use crate::types::Max;
18use serde::{Deserialize, Serialize};
19
20inventory::submit! {
21    ProblemSchemaEntry {
22        name: "MaximumCommonEdgeSubgraph",
23        display_name: "Maximum Common Edge Subgraph",
24        aliases: &["MCES"],
25        dimensions: &[],
26        module_path: module_path!(),
27        description: "Maximize the number of preserved labelled directed arcs under a partial injective vertex map from G1 into G2",
28        fields: &[
29            FieldInfo {
30                name: "graph_1",
31                type_name: "LabelledDigraph",
32                description: "Source directed edge-labelled graph G1 = (V1, E1) whose vertices are mapped",
33            },
34            FieldInfo {
35                name: "graph_2",
36                type_name: "LabelledDigraph",
37                description: "Target directed edge-labelled graph G2 = (V2, E2) receiving the partial injective map",
38            },
39        ],
40    }
41}
42
43inventory::submit! {
44    ProblemSizeFieldEntry {
45        name: "MaximumCommonEdgeSubgraph",
46        fields: &["num_vertices_1", "num_vertices_2", "num_arcs_1", "num_arcs_2"],
47    }
48}
49
50/// A directed labelled arc `(src, label, dst)` in a [`LabelledDigraph`].
51///
52/// Labels are unsigned integers; the alphabet `Sigma` is encoded by mapping
53/// each symbol to a distinct nonnegative integer.
54#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
55pub struct LabelledArc {
56    /// Source vertex index.
57    pub src: usize,
58    /// Edge label.
59    pub label: u32,
60    /// Destination vertex index.
61    pub dst: usize,
62}
63
64impl LabelledArc {
65    /// Construct a new labelled arc.
66    pub fn new(src: usize, label: u32, dst: usize) -> Self {
67        Self { src, label, dst }
68    }
69}
70
71/// A finite directed edge-labelled graph used by
72/// [`MaximumCommonEdgeSubgraph`].
73///
74/// Vertices are the indices `0..num_vertices`. Arcs are stored as a flat
75/// vector and treated as a set (duplicates are deduplicated by the
76/// constructor).
77#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
78pub struct LabelledDigraph {
79    /// Number of vertices `|V|`.
80    pub num_vertices: usize,
81    /// Labelled directed arcs `(u, label, v)`.
82    pub arcs: Vec<LabelledArc>,
83}
84
85impl LabelledDigraph {
86    /// Construct a new labelled digraph.
87    ///
88    /// # Panics
89    /// Panics if any arc references a vertex index outside `0..num_vertices`.
90    pub fn new(num_vertices: usize, arcs: Vec<LabelledArc>) -> Self {
91        for arc in &arcs {
92            assert!(
93                arc.src < num_vertices,
94                "labelled arc source {} out of range for num_vertices = {}",
95                arc.src,
96                num_vertices
97            );
98            assert!(
99                arc.dst < num_vertices,
100                "labelled arc destination {} out of range for num_vertices = {}",
101                arc.dst,
102                num_vertices
103            );
104        }
105        // Deduplicate while preserving order so set semantics hold.
106        let mut seen = std::collections::HashSet::new();
107        let mut deduped = Vec::with_capacity(arcs.len());
108        for arc in arcs {
109            if seen.insert((arc.src, arc.label, arc.dst)) {
110                deduped.push(arc);
111            }
112        }
113        Self {
114            num_vertices,
115            arcs: deduped,
116        }
117    }
118
119    /// Number of vertices `|V|`.
120    pub fn num_vertices(&self) -> usize {
121        self.num_vertices
122    }
123
124    /// Number of distinct labelled arcs `|E|`.
125    pub fn num_arcs(&self) -> usize {
126        self.arcs.len()
127    }
128
129    /// Labelled directed arcs.
130    pub fn arcs(&self) -> &[LabelledArc] {
131        &self.arcs
132    }
133}
134
135/// The Maximum Common Edge Subgraph problem.
136///
137/// Given two finite directed edge-labelled graphs `G1 = (V1, E1)` and
138/// `G2 = (V2, E2)`, find a partial injective map `f: U1 -> V2` with
139/// `U1 subset.eq V1` that maximizes
140///
141/// `|{(u, lambda, v) in E1 : u, v in U1 and (f(u), lambda, f(v)) in E2}|`.
142///
143/// # Configuration encoding
144///
145/// `dims()` returns `vec![graph_2.num_vertices + 1; graph_1.num_vertices]`.
146/// For each source vertex `u in V1`, `config[u]` is either an index in
147/// `0..graph_2.num_vertices` (the matched target vertex) or the sentinel
148/// value `graph_2.num_vertices` denoting `bottom` (unmatched). Feasibility
149/// requires the matched values (everything not equal to the sentinel) to be
150/// pairwise distinct.
151#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
152pub struct MaximumCommonEdgeSubgraph {
153    graph_1: LabelledDigraph,
154    graph_2: LabelledDigraph,
155}
156
157impl MaximumCommonEdgeSubgraph {
158    /// Construct a new instance from two labelled digraphs.
159    pub fn new(graph_1: LabelledDigraph, graph_2: LabelledDigraph) -> Self {
160        Self { graph_1, graph_2 }
161    }
162
163    /// Source graph `G1`.
164    pub fn graph_1(&self) -> &LabelledDigraph {
165        &self.graph_1
166    }
167
168    /// Target graph `G2`.
169    pub fn graph_2(&self) -> &LabelledDigraph {
170        &self.graph_2
171    }
172
173    /// Number of vertices in `G1`: `|V1|`.
174    pub fn num_vertices_1(&self) -> usize {
175        self.graph_1.num_vertices()
176    }
177
178    /// Number of vertices in `G2`: `|V2|`.
179    pub fn num_vertices_2(&self) -> usize {
180        self.graph_2.num_vertices()
181    }
182
183    /// Number of labelled arcs in `G1`: `|E1|`.
184    pub fn num_arcs_1(&self) -> usize {
185        self.graph_1.num_arcs()
186    }
187
188    /// Number of labelled arcs in `G2`: `|E2|`.
189    pub fn num_arcs_2(&self) -> usize {
190        self.graph_2.num_arcs()
191    }
192
193    /// Sentinel value encoding `bottom` (unmatched) for any `config[u]`.
194    pub fn bottom_index(&self) -> usize {
195        self.graph_2.num_vertices()
196    }
197
198    /// Check that `config` describes a partial injective map.
199    ///
200    /// Validity requires: `config.len() == |V1|`, every entry lies in
201    /// `0..=|V2|` (with `|V2|` denoting `bottom`), and all entries strictly
202    /// less than `|V2|` are pairwise distinct.
203    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
204        let n1 = self.num_vertices_1();
205        let n2 = self.num_vertices_2();
206        if config.len() != n1 {
207            return false;
208        }
209        let bottom = n2;
210        let mut used = vec![false; n2];
211        for &value in config {
212            if value > bottom {
213                return false;
214            }
215            if value == bottom {
216                continue;
217            }
218            if used[value] {
219                return false;
220            }
221            used[value] = true;
222        }
223        true
224    }
225
226    /// Count the labelled arcs in `G1` that are preserved by the partial
227    /// injective map `config`. Returns `None` if `config` is infeasible.
228    pub fn preserved_arc_count(&self, config: &[usize]) -> Option<usize> {
229        if !self.is_valid_solution(config) {
230            return None;
231        }
232        let bottom = self.bottom_index();
233        // Build a lookup set of arcs in G2 for O(1) membership checks.
234        let arcs_2: std::collections::HashSet<(usize, u32, usize)> = self
235            .graph_2
236            .arcs()
237            .iter()
238            .map(|arc| (arc.src, arc.label, arc.dst))
239            .collect();
240        let mut count = 0usize;
241        for arc in self.graph_1.arcs() {
242            let fu = config[arc.src];
243            let fv = config[arc.dst];
244            if fu == bottom || fv == bottom {
245                continue;
246            }
247            if arcs_2.contains(&(fu, arc.label, fv)) {
248                count += 1;
249            }
250        }
251        Some(count)
252    }
253}
254
255impl Problem for MaximumCommonEdgeSubgraph {
256    const NAME: &'static str = "MaximumCommonEdgeSubgraph";
257    type Value = Max<i64>;
258
259    fn variant() -> Vec<(&'static str, &'static str)> {
260        crate::variant_params![]
261    }
262
263    fn dims(&self) -> Vec<usize> {
264        vec![self.graph_2.num_vertices() + 1; self.graph_1.num_vertices()]
265    }
266
267    fn evaluate(&self, config: &[usize]) -> Max<i64> {
268        match self.preserved_arc_count(config) {
269            Some(count) => Max(Some(count as i64)),
270            None => Max(None),
271        }
272    }
273}
274
275crate::declare_variants! {
276    default MaximumCommonEdgeSubgraph => "(num_vertices_2 + 1)^num_vertices_1",
277}
278
279#[cfg(feature = "example-db")]
280pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
281    vec![crate::example_db::specs::ModelExampleSpec {
282        id: "maximum_common_edge_subgraph",
283        instance: Box::new(MaximumCommonEdgeSubgraph::new(
284            LabelledDigraph::new(
285                5,
286                vec![
287                    LabelledArc::new(0, 0, 1),
288                    LabelledArc::new(1, 1, 2),
289                    LabelledArc::new(0, 2, 2),
290                    LabelledArc::new(2, 0, 3),
291                    LabelledArc::new(1, 3, 3),
292                    LabelledArc::new(3, 1, 4),
293                ],
294            ),
295            LabelledDigraph::new(
296                4,
297                vec![
298                    LabelledArc::new(0, 0, 1),
299                    LabelledArc::new(1, 1, 2),
300                    LabelledArc::new(0, 2, 2),
301                    LabelledArc::new(2, 0, 3),
302                    LabelledArc::new(1, 3, 3),
303                    LabelledArc::new(0, 1, 3),
304                ],
305            ),
306        )),
307        // 4 encodes bottom because |V2| = 4. The map 0->0, 1->1, 2->2, 3->3,
308        // 4->bottom preserves the first five source arcs.
309        optimal_config: vec![0, 1, 2, 3, 4],
310        optimal_value: serde_json::json!(5),
311    }]
312}
313
314#[cfg(test)]
315#[path = "../../unit_tests/models/graph/maximum_common_edge_subgraph.rs"]
316mod tests;
problemreductions/models/graph/maximum_common_edge_subgraph.rs

problemreductions/models/graph/
maximum_common_edge_subgraph.rs
