problemreductions/models/graph/

isomorphic_spanning_tree.rs

//! Isomorphic Spanning Tree problem implementation.
//!
//! Given a graph G and a tree T with |V(G)| = |V(T)|, determine whether G
//! contains a spanning tree isomorphic to T. This is a classical NP-complete
//! problem (Garey & Johnson, ND8) that generalizes Hamiltonian Path.

use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
use crate::topology::{Graph, SimpleGraph};
use crate::traits::Problem;
use crate::variant::VariantParam;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "IsomorphicSpanningTree",
        display_name: "Isomorphic Spanning Tree",
        aliases: &[],
        dimensions: &[
            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
        ],
        module_path: module_path!(),
        description: "Does graph G contain a spanning tree isomorphic to tree T?",
        fields: &[
            FieldInfo { name: "graph", type_name: "G", description: "The host graph G" },
            FieldInfo { name: "tree", type_name: "SimpleGraph", description: "The target tree T (must be a tree with |V(T)| = |V(G)|)" },
        ],
    }
}

/// Isomorphic Spanning Tree problem.
///
/// Given an undirected graph G = (V, E) and a tree T = (V_T, E_T) with
/// |V| = |V_T|, determine if there exists a bijection π: V_T → V such that
/// for every edge {u, v} in E_T, {π(u), π(v)} is an edge in E.
///
/// The configuration encodes an isomorphism as a permutation of the vertices of
/// `graph`: `config[i]` is the graph vertex that tree vertex `i` maps to.
///
/// # Example
///
/// ```
/// use problemreductions::models::graph::IsomorphicSpanningTree;
/// use problemreductions::topology::SimpleGraph;
/// use problemreductions::{Problem, Solver, BruteForce};
///
/// // Host graph: triangle 0-1-2-0
/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
/// // Tree: path 0-1-2
/// let tree = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
/// let problem = IsomorphicSpanningTree::new(graph, tree);
///
/// let solver = BruteForce::new();
/// let sol = solver.find_witness(&problem);
/// assert!(sol.is_some());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
pub struct IsomorphicSpanningTree<G> {
    graph: G,
    tree: SimpleGraph,
}

impl<G: Graph> IsomorphicSpanningTree<G> {
    /// Create a new IsomorphicSpanningTree problem.
    ///
    /// # Panics
    ///
    /// Panics if |V(G)| != |V(T)| or if T is not a tree (not connected or
    /// wrong number of edges).
    pub fn new(graph: G, tree: SimpleGraph) -> Self {
        let n = graph.num_vertices();
        assert_eq!(
            n,
            tree.num_vertices(),
            "graph and tree must have the same number of vertices"
        );
        assert_eq!(
            tree.num_edges(),
            n.saturating_sub(1),
            "tree must have exactly n-1 edges"
        );
        assert!(is_connected(&tree), "tree must be connected");
        Self { graph, tree }
    }

    /// Get a reference to the host graph.
    pub fn graph(&self) -> &G {
        &self.graph
    }

    /// Get a reference to the target tree.
    pub fn tree(&self) -> &SimpleGraph {
        &self.tree
    }

    /// Get the number of vertices.
    pub fn num_vertices(&self) -> usize {
        self.graph.num_vertices()
    }

    /// Get the number of edges in the host graph.
    pub fn num_edges(&self) -> usize {
        self.graph.num_edges()
    }

    /// Get the edges of the target tree.
    pub fn tree_edges(&self) -> Vec<(usize, usize)> {
        self.tree.edges()
    }
}

impl<G> Problem for IsomorphicSpanningTree<G>
where
    G: Graph + VariantParam,
{
    const NAME: &'static str = "IsomorphicSpanningTree";
    type Value = crate::types::Or;

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![G]
    }

    fn dims(&self) -> Vec<usize> {
        vec![self.graph.num_vertices(); self.graph.num_vertices()]
    }

    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
        crate::types::Or(is_valid_isomorphic_spanning_tree(
            &self.graph,
            &self.tree,
            config,
        ))
    }
}

fn is_valid_isomorphic_spanning_tree<G: Graph>(
    graph: &G,
    tree: &SimpleGraph,
    config: &[usize],
) -> bool {
    let n = graph.num_vertices();
    if config.len() != n {
        return false;
    }

    let mut seen = vec![false; n];
    for &v in config {
        if v >= n || seen[v] {
            return false;
        }
        seen[v] = true;
    }

    tree.edges()
        .into_iter()
        .all(|(u, v)| graph.has_edge(config[u], config[v]))
}

fn is_connected(graph: &SimpleGraph) -> bool {
    let n = graph.num_vertices();
    if n == 0 {
        return true;
    }

    let mut visited = vec![false; n];
    let mut queue = std::collections::VecDeque::new();
    visited[0] = true;
    queue.push_back(0);
    let mut count = 1;

    while let Some(v) = queue.pop_front() {
        for u in graph.neighbors(v) {
            if !visited[u] {
                visited[u] = true;
                count += 1;
                queue.push_back(u);
            }
        }
    }

    count == n
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "isomorphic_spanning_tree",
        instance: Box::new(IsomorphicSpanningTree::new(
            SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
            SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]),
        )),
        optimal_config: vec![0, 1, 2, 3],
        optimal_value: serde_json::json!(true),
    }]
}

crate::declare_variants! {
    default IsomorphicSpanningTree<SimpleGraph> => "2^num_vertices",
}

#[cfg(test)]
#[path = "../../unit_tests/models/graph/isomorphic_spanning_tree.rs"]
mod tests;