problemreductions/models/graph/
maximum_leaf_spanning_tree.rs

1//! Maximum Leaf Spanning Tree problem implementation.
2//!
3//! Given a connected graph G, find a spanning tree T of G that maximizes
4//! the number of leaves (degree-1 vertices) in T.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::Max;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "MaximumLeafSpanningTree",
15        display_name: "Maximum Leaf Spanning Tree",
16        aliases: &[],
17        dimensions: &[
18            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
19        ],
20        category: crate::registry::ProblemCategory::Graph,
21        module_path: module_path!(),
22        description: "Find spanning tree maximizing the number of leaves",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
25        ],
26    }
27}
28
29/// The Maximum Leaf Spanning Tree problem.
30///
31/// Given a connected graph G = (V, E), find a spanning tree T of G such that
32/// the number of leaves (vertices with degree 1 in T) is maximized.
33///
34/// # Representation
35///
36/// Each edge is assigned a binary variable:
37/// - 0: edge is not in the spanning tree
38/// - 1: edge is in the spanning tree
39///
40/// A valid spanning tree requires exactly n-1 selected edges that form a
41/// connected, acyclic subgraph spanning all vertices.
42///
43/// # Type Parameters
44///
45/// * `G` - The graph type (e.g., `SimpleGraph`)
46#[derive(Debug, Clone, Serialize, Deserialize)]
47pub struct MaximumLeafSpanningTree<G> {
48    /// The underlying graph.
49    graph: G,
50}
51
52impl<G: Graph> MaximumLeafSpanningTree<G> {
53    /// Create a MaximumLeafSpanningTree problem from a graph.
54    ///
55    /// The graph must have at least 2 vertices.
56    pub fn new(graph: G) -> Self {
57        assert!(
58            graph.num_vertices() >= 2,
59            "graph must have at least 2 vertices"
60        );
61        Self { graph }
62    }
63
64    /// Get a reference to the underlying graph.
65    pub fn graph(&self) -> &G {
66        &self.graph
67    }
68
69    /// Get the number of vertices in the underlying graph.
70    pub fn num_vertices(&self) -> usize {
71        self.graph.num_vertices()
72    }
73
74    /// Get the number of edges in the underlying graph.
75    pub fn num_edges(&self) -> usize {
76        self.graph.num_edges()
77    }
78
79    /// Check if a configuration is a valid spanning tree.
80    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
81        is_valid_spanning_tree(&self.graph, config)
82    }
83}
84
85/// Check if a configuration forms a valid spanning tree:
86/// 1. Exactly n-1 edges selected
87/// 2. Selected edges form a connected subgraph (which, combined with n-1 edges, implies a tree)
88fn is_valid_spanning_tree<G: Graph>(graph: &G, config: &[bool]) -> bool {
89    let n = graph.num_vertices();
90    let edges = graph.edges();
91    if config.len() != edges.len() {
92        return false;
93    }
94
95    // Count selected edges
96    let selected_count = config.iter().filter(|&&selected| selected).count();
97    if selected_count != n - 1 {
98        return false;
99    }
100
101    // Build adjacency from selected edges and check connectivity via BFS
102    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
103    for (idx, &sel) in config.iter().enumerate() {
104        if sel {
105            let (u, v) = edges[idx];
106            adj[u].push(v);
107            adj[v].push(u);
108        }
109    }
110
111    // BFS from vertex 0
112    let mut visited = vec![false; n];
113    let mut queue = std::collections::VecDeque::new();
114    visited[0] = true;
115    queue.push_back(0);
116    while let Some(v) = queue.pop_front() {
117        for &u in &adj[v] {
118            if !visited[u] {
119                visited[u] = true;
120                queue.push_back(u);
121            }
122        }
123    }
124
125    // All vertices must be reachable
126    visited.iter().all(|&v| v)
127}
128
129/// Count the number of leaves (degree-1 vertices) in the tree defined by the config.
130fn count_leaves<G: Graph>(graph: &G, config: &[bool]) -> usize {
131    let n = graph.num_vertices();
132    let edges = graph.edges();
133    let mut degree = vec![0usize; n];
134    for (idx, &sel) in config.iter().enumerate() {
135        if sel {
136            let (u, v) = edges[idx];
137            degree[u] += 1;
138            degree[v] += 1;
139        }
140    }
141    degree.iter().filter(|&&d| d == 1).count()
142}
143
144impl<G> Problem for MaximumLeafSpanningTree<G>
145where
146    G: Graph + crate::variant::VariantParam,
147{
148    const NAME: &'static str = "MaximumLeafSpanningTree";
149    type Solution = Vec<bool>;
150    type Value = Max<i64>;
151
152    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
153
154    fn variant() -> Vec<(&'static str, &'static str)> {
155        crate::variant_params![G]
156    }
157
158    fn evaluate(
159        &self,
160        config: &Self::Solution,
161    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
162        if config.len() != self.graph.num_edges() {
163            return Err(crate::traits::EvaluationError::InvalidConfiguration(
164                "edge-selection length does not match the graph".into(),
165            ));
166        }
167        Ok({
168            if !is_valid_spanning_tree(&self.graph, config) {
169                return Ok(Max(None));
170            }
171            Max(Some(
172                i64::try_from(count_leaves(&self.graph, config)).map_err(|_| {
173                    crate::traits::EvaluationError::IntegerOverflow(
174                        "converting leaf count to i64".into(),
175                    )
176                })?,
177            ))
178        })
179    }
180}
181
182impl<G> crate::solvers::BruteForceProblem for MaximumLeafSpanningTree<G>
183where
184    G: Graph + crate::variant::VariantParam,
185{
186    fn dimensions(&self) -> Vec<usize> {
187        vec![2; self.graph.num_edges()]
188    }
189}
190
191crate::impl_random_generate!(
192    MaximumLeafSpanningTree<SimpleGraph>,
193    crate::random::SimpleGraphRandomSpec,
194    |spec| {
195        if spec.num_vertices < 2 {
196            return Err("num_vertices must be at least 2".to_string().into());
197        }
198        Ok(MaximumLeafSpanningTree::new(spec.graph()?))
199    }
200);
201
202crate::declare_variants! {
203    default MaximumLeafSpanningTree<SimpleGraph> => "1.8966^num_vertices" random,
204}
205
206crate::register_brute_force! {
207    MaximumLeafSpanningTree<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
208}
209
210#[cfg(feature = "example-db")]
211pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
212    vec![crate::example_db::specs::ModelExampleSpec {
213        id: "maximum_leaf_spanning_tree_simplegraph",
214        instance: Box::new(MaximumLeafSpanningTree::new(SimpleGraph::new(
215            6,
216            vec![
217                (0, 1),
218                (0, 2),
219                (0, 3),
220                (1, 4),
221                (2, 4),
222                (2, 5),
223                (3, 5),
224                (4, 5),
225                (1, 3),
226            ],
227        ))),
228        // Edges: 0:(0,1), 1:(0,2), 2:(0,3), 3:(1,4), 4:(2,4), 5:(2,5), 6:(3,5), 7:(4,5), 8:(1,3)
229        // Tree: {(0,1),(0,2),(0,3),(2,4),(2,5)} = indices 0,1,2,4,5
230        // Leaves: 1,3,4,5 (degree 1 each), Internal: 0 (deg 3), 2 (deg 3)
231        optimal_config: serde_json::json!(vec![
232            true, true, true, false, true, true, false, false, false
233        ]),
234        optimal_value: serde_json::json!(4),
235    }]
236}
237
238#[cfg(test)]
239#[path = "../../unit_tests/models/graph/maximum_leaf_spanning_tree.rs"]
240mod tests;
problemreductions/models/graph/maximum_leaf_spanning_tree.rs

problemreductions/models/graph/
maximum_leaf_spanning_tree.rs
