problemreductions/models/graph/
isomorphic_spanning_tree.rs

1//! Isomorphic Spanning Tree problem implementation.
2//!
3//! Given a graph G and a tree T with |V(G)| = |V(T)|, determine whether G
4//! contains a spanning tree isomorphic to T. This is a classical NP-complete
5//! problem (Garey & Johnson, ND8) that generalizes Hamiltonian Path.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::variant::VariantParam;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "IsomorphicSpanningTree",
16        display_name: "Isomorphic Spanning Tree",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Does graph G contain a spanning tree isomorphic to tree T?",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The host graph G" },
26            FieldInfo { name: "tree", type_name: "SimpleGraph", description: "The target tree T (must be a tree with |V(T)| = |V(G)|)" },
27        ],
28    }
29}
30
31/// Isomorphic Spanning Tree problem.
32///
33/// Given an undirected graph G = (V, E) and a tree T = (V_T, E_T) with
34/// |V| = |V_T|, determine if there exists a bijection π: V_T → V such that
35/// for every edge {u, v} in E_T, {π(u), π(v)} is an edge in E.
36///
37/// The configuration encodes an isomorphism as a permutation of the vertices of
38/// `graph`: `config[i]` is the graph vertex that tree vertex `i` maps to.
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::graph::IsomorphicSpanningTree;
44/// use problemreductions::topology::SimpleGraph;
45/// use problemreductions::{Problem, BruteForce};
46///
47/// // Host graph: triangle 0-1-2-0
48/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
49/// // Tree: path 0-1-2
50/// let tree = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
51/// let problem = IsomorphicSpanningTree::new(graph, tree);
52///
53/// let solver = BruteForce::new();
54/// let sol = solver.solve(&problem).unwrap();
55/// assert!(sol.is_some());
56/// ```
57#[derive(Debug, Clone, Serialize)]
58pub struct IsomorphicSpanningTree<G> {
59    graph: G,
60    tree: SimpleGraph,
61}
62
63impl<'de, G> Deserialize<'de> for IsomorphicSpanningTree<G>
64where
65    G: Graph + Deserialize<'de>,
66{
67    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
68    where
69        D: serde::Deserializer<'de>,
70    {
71        #[derive(Deserialize)]
72        struct Helper<G> {
73            graph: G,
74            tree: SimpleGraph,
75        }
76        let helper = Helper::<G>::deserialize(deserializer)?;
77        Self::try_new(helper.graph, helper.tree).map_err(serde::de::Error::custom)
78    }
79}
80
81impl<G: Graph> IsomorphicSpanningTree<G> {
82    /// Create a new IsomorphicSpanningTree problem.
83    ///
84    /// # Panics
85    ///
86    /// Panics if |V(G)| != |V(T)| or if T is not a tree (not connected or
87    /// wrong number of edges).
88    pub fn new(graph: G, tree: SimpleGraph) -> Self {
89        Self::try_new(graph, tree).unwrap_or_else(|error| panic!("{error}"))
90    }
91
92    fn try_new(graph: G, tree: SimpleGraph) -> Result<Self, &'static str> {
93        let n = graph.num_vertices();
94        if n != tree.num_vertices() {
95            return Err("graph and tree must have the same number of vertices");
96        }
97        if tree.num_edges() != n.saturating_sub(1) {
98            return Err("tree must have exactly n-1 edges");
99        }
100        if !is_connected(&tree) {
101            return Err("tree must be connected");
102        }
103        Ok(Self { graph, tree })
104    }
105
106    /// Get a reference to the host graph.
107    pub fn graph(&self) -> &G {
108        &self.graph
109    }
110
111    /// Get a reference to the target tree.
112    pub fn tree(&self) -> &SimpleGraph {
113        &self.tree
114    }
115
116    /// Get the number of vertices.
117    pub fn num_vertices(&self) -> usize {
118        self.graph.num_vertices()
119    }
120
121    /// Get the number of edges in the host graph.
122    pub fn num_edges(&self) -> usize {
123        self.graph.num_edges()
124    }
125
126    /// Get the edges of the target tree.
127    pub fn tree_edges(&self) -> Vec<(usize, usize)> {
128        self.tree.edges()
129    }
130}
131
132impl<G> Problem for IsomorphicSpanningTree<G>
133where
134    G: Graph + VariantParam,
135{
136    const NAME: &'static str = "IsomorphicSpanningTree";
137    type Solution = Vec<usize>;
138    type Value = crate::types::Or;
139
140    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
141
142    fn variant() -> Vec<(&'static str, &'static str)> {
143        crate::variant_params![G]
144    }
145
146    fn evaluate(
147        &self,
148        config: &Self::Solution,
149    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
150        let n = self.graph.num_vertices();
151        if config.len() != n {
152            return Err(crate::traits::EvaluationError::InvalidConfiguration(
153                "vertex mapping length does not match the graph".into(),
154            ));
155        }
156        if config.iter().any(|&vertex| vertex >= n) {
157            return Err(crate::traits::EvaluationError::InvalidConfiguration(
158                "vertex mapping contains an out-of-range vertex".into(),
159            ));
160        }
161        Ok({
162            crate::types::Or(is_valid_isomorphic_spanning_tree(
163                &self.graph,
164                &self.tree,
165                config,
166            ))
167        })
168    }
169}
170
171impl<G> crate::solvers::BruteForceProblem for IsomorphicSpanningTree<G>
172where
173    G: Graph + VariantParam,
174{
175    fn dimensions(&self) -> Vec<usize> {
176        vec![self.graph.num_vertices(); self.graph.num_vertices()]
177    }
178}
179
180fn is_valid_isomorphic_spanning_tree<G: Graph>(
181    graph: &G,
182    tree: &SimpleGraph,
183    config: &[usize],
184) -> bool {
185    let n = graph.num_vertices();
186    if config.len() != n {
187        return false;
188    }
189
190    let mut seen = vec![false; n];
191    for &v in config {
192        if v >= n || seen[v] {
193            return false;
194        }
195        seen[v] = true;
196    }
197
198    tree.edges()
199        .into_iter()
200        .all(|(u, v)| graph.has_edge(config[u], config[v]))
201}
202
203fn is_connected(graph: &SimpleGraph) -> bool {
204    let n = graph.num_vertices();
205    if n == 0 {
206        return true;
207    }
208
209    let mut visited = vec![false; n];
210    let mut queue = std::collections::VecDeque::new();
211    visited[0] = true;
212    queue.push_back(0);
213    let mut count = 1;
214
215    while let Some(v) = queue.pop_front() {
216        for u in graph.neighbors(v) {
217            if !visited[u] {
218                visited[u] = true;
219                count += 1;
220                queue.push_back(u);
221            }
222        }
223    }
224
225    count == n
226}
227
228#[cfg(feature = "example-db")]
229pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
230    vec![crate::example_db::specs::ModelExampleSpec {
231        id: "isomorphic_spanning_tree",
232        instance: Box::new(IsomorphicSpanningTree::new(
233            SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
234            SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]),
235        )),
236        optimal_config: serde_json::json!(vec![0, 1, 2, 3]),
237        optimal_value: serde_json::json!(true),
238    }]
239}
240
241crate::declare_variants! {
242    default IsomorphicSpanningTree<SimpleGraph> => "2^num_vertices",
243}
244
245crate::register_brute_force! {
246    IsomorphicSpanningTree<SimpleGraph>,
247}
248
249#[cfg(test)]
250#[path = "../../unit_tests/models/graph/isomorphic_spanning_tree.rs"]
251mod tests;
problemreductions/models/graph/isomorphic_spanning_tree.rs

problemreductions/models/graph/
isomorphic_spanning_tree.rs
