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

problemreductions/models/graph/
maximum_common_edge_subgraph.rs
