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

problemreductions/models/graph/
maximum_common_edge_subgraph.rs
