problemreductions/models/graph/
subgraph_isomorphism.rs

1//! SubgraphIsomorphism problem implementation.
2//!
3//! The Subgraph Isomorphism problem asks whether a "pattern" graph H can be
4//! found embedded within a "host" graph G as a subgraph — that is, whether
5//! there exists an injective mapping f: V(H) -> V(G) such that every edge
6//! {u,v} in H maps to an edge {f(u),f(v)} in G.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::topology::{Graph, SimpleGraph};
10use crate::traits::Problem;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "SubgraphIsomorphism",
16        display_name: "Subgraph Isomorphism",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Graph,
20        module_path: module_path!(),
21        description: "Determine if host graph G contains a subgraph isomorphic to pattern graph H",
22        fields: &[
23            FieldInfo { name: "graph", type_name: "SimpleGraph", description: "The host graph G = (V_1, E_1) to search in" },
24            FieldInfo { name: "pattern", type_name: "SimpleGraph", description: "The pattern graph H = (V_2, E_2) to find as a subgraph" },
25        ],
26    }
27}
28
29/// The Subgraph Isomorphism problem.
30///
31/// Given a host graph G = (V_1, E_1) and a pattern graph H = (V_2, E_2),
32/// determine whether there exists an injective function f: V_2 -> V_1 such
33/// that for every edge {u,v} in E_2, {f(u), f(v)} is an edge in E_1.
34///
35/// This is a satisfaction (decision) problem: the metric is `bool`.
36///
37/// # Configuration
38///
39/// A configuration is a vector of length |V_2| where each entry is a value
40/// in {0, ..., |V_1|-1} representing the host vertex that each pattern
41/// vertex maps to. The configuration is valid (true) if:
42/// 1. All mapped host vertices are distinct (injective mapping)
43/// 2. Every edge in the pattern graph maps to an edge in the host graph
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::graph::SubgraphIsomorphism;
49/// use problemreductions::topology::SimpleGraph;
50/// use problemreductions::{Problem, BruteForce};
51///
52/// // Host: K4 (complete graph on 4 vertices)
53/// let host = SimpleGraph::new(4, vec![(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]);
54/// // Pattern: triangle (K3)
55/// let pattern = SimpleGraph::new(3, vec![(0,1),(0,2),(1,2)]);
56/// let problem = SubgraphIsomorphism::new(host, pattern);
57///
58/// // Mapping [0, 1, 2] means pattern vertex 0->host 0, 1->1, 2->2
59/// assert!(problem.evaluate(&vec![0, 1, 2]).unwrap());
60///
61/// let solver = BruteForce::new();
62/// let solution = solver.solve(&problem).unwrap();
63/// assert!(solution.is_some());
64/// ```
65#[derive(Debug, Clone, Serialize, Deserialize)]
66pub struct SubgraphIsomorphism {
67    /// The host graph G = (V_1, E_1).
68    host_graph: SimpleGraph,
69    /// The pattern graph H = (V_2, E_2).
70    pattern_graph: SimpleGraph,
71}
72
73impl SubgraphIsomorphism {
74    /// Create a new SubgraphIsomorphism problem.
75    ///
76    /// # Arguments
77    /// * `host_graph` - The host graph to search in
78    /// * `pattern_graph` - The pattern graph to find as a subgraph
79    pub fn new(host_graph: SimpleGraph, pattern_graph: SimpleGraph) -> Self {
80        Self {
81            host_graph,
82            pattern_graph,
83        }
84    }
85
86    /// Get a reference to the host graph.
87    pub fn host_graph(&self) -> &SimpleGraph {
88        &self.host_graph
89    }
90
91    /// Get a reference to the pattern graph.
92    pub fn pattern_graph(&self) -> &SimpleGraph {
93        &self.pattern_graph
94    }
95
96    /// Get the number of vertices in the host graph.
97    pub fn num_host_vertices(&self) -> usize {
98        self.host_graph.num_vertices()
99    }
100
101    /// Get the number of edges in the host graph.
102    pub fn num_host_edges(&self) -> usize {
103        self.host_graph.num_edges()
104    }
105
106    /// Get the number of vertices in the pattern graph.
107    pub fn num_pattern_vertices(&self) -> usize {
108        self.pattern_graph.num_vertices()
109    }
110
111    /// Get the number of edges in the pattern graph.
112    pub fn num_pattern_edges(&self) -> usize {
113        self.pattern_graph.num_edges()
114    }
115
116    /// Check if a configuration represents a valid subgraph isomorphism.
117    pub fn is_valid_solution(
118        &self,
119        config: &[usize],
120    ) -> Result<bool, crate::traits::EvaluationError> {
121        let n_pattern = self.pattern_graph.num_vertices();
122        let n_host = self.host_graph.num_vertices();
123
124        if n_pattern > n_host {
125            return Ok(false);
126        }
127        if config.len() != n_pattern {
128            return Err(crate::traits::EvaluationError::InvalidConfiguration(
129                "vertex mapping length does not match the pattern graph".into(),
130            ));
131        }
132        if config.iter().any(|&vertex| vertex >= n_host) {
133            return Err(crate::traits::EvaluationError::InvalidConfiguration(
134                "vertex mapping contains an out-of-range target vertex".into(),
135            ));
136        }
137        for i in 0..n_pattern {
138            for j in (i + 1)..n_pattern {
139                if config[i] == config[j] {
140                    return Ok(false);
141                }
142            }
143        }
144        for (u, v) in self.pattern_graph.edges() {
145            if !self.host_graph.has_edge(config[u], config[v]) {
146                return Ok(false);
147            }
148        }
149        Ok(true)
150    }
151}
152
153impl Problem for SubgraphIsomorphism {
154    const NAME: &'static str = "SubgraphIsomorphism";
155    type Solution = Vec<usize>;
156    type Value = crate::types::Or;
157
158    crate::problem_parameters![
159        ("num_host_edges", num_host_edges),
160        ("num_host_vertices", num_host_vertices),
161        ("num_pattern_edges", num_pattern_edges),
162        ("num_pattern_vertices", num_pattern_vertices),
163    ];
164
165    fn evaluate(
166        &self,
167        config: &Self::Solution,
168    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
169        Ok(crate::types::Or(self.is_valid_solution(config)?))
170    }
171
172    fn variant() -> Vec<(&'static str, &'static str)> {
173        crate::variant_params![]
174    }
175}
176
177impl crate::solvers::BruteForceProblem for SubgraphIsomorphism {
178    fn dimensions(&self) -> Vec<usize> {
179        let n_host = self.host_graph.num_vertices();
180        let n_pattern = self.pattern_graph.num_vertices();
181
182        if n_pattern > n_host {
183            // No injective mapping possible: each variable gets an empty domain.
184            vec![0; n_pattern]
185        } else {
186            vec![n_host; n_pattern]
187        }
188    }
189}
190
191crate::declare_variants! {
192    default SubgraphIsomorphism => "num_host_vertices ^ num_pattern_vertices",
193}
194
195crate::register_brute_force! {
196    SubgraphIsomorphism,
197}
198
199#[cfg(feature = "example-db")]
200pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
201    use crate::topology::SimpleGraph;
202    // Host: K4, Pattern: K3 → map [0,1,2] preserves all edges
203    vec![crate::example_db::specs::ModelExampleSpec {
204        id: "subgraph_isomorphism",
205        instance: Box::new(SubgraphIsomorphism::new(
206            SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
207            SimpleGraph::new(3, vec![(0, 1), (0, 2), (1, 2)]),
208        )),
209        optimal_config: serde_json::json!(vec![0, 1, 2]),
210        optimal_value: serde_json::json!(true),
211    }]
212}
213
214#[cfg(test)]
215#[path = "../../unit_tests/models/graph/subgraph_isomorphism.rs"]
216mod tests;
problemreductions/models/graph/subgraph_isomorphism.rs

problemreductions/models/graph/
subgraph_isomorphism.rs
