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)]
47#[serde(try_from = "MaximumLeafSpanningTreeData<G>")]
48#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
49pub struct MaximumLeafSpanningTree<G> {
50    /// The underlying graph.
51    graph: G,
52}
53
54#[derive(Deserialize)]
55#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
56struct MaximumLeafSpanningTreeData<G> {
57    graph: G,
58}
59
60impl<G> TryFrom<MaximumLeafSpanningTreeData<G>> for MaximumLeafSpanningTree<G>
61where
62    G: Graph,
63{
64    type Error = crate::registry::ConstructionError;
65
66    fn try_from(data: MaximumLeafSpanningTreeData<G>) -> Result<Self, Self::Error> {
67        Self::try_new(data.graph)
68    }
69}
70
71impl<G: Graph> MaximumLeafSpanningTree<G> {
72    /// Create a MaximumLeafSpanningTree problem from a graph.
73    ///
74    /// The graph must have at least 2 vertices.
75    pub fn new(graph: G) -> Self {
76        Self::try_new(graph).unwrap_or_else(|error| panic!("{error}"))
77    }
78
79    fn try_new(graph: G) -> Result<Self, crate::registry::ConstructionError> {
80        if graph.num_vertices() < 2 {
81            return Err("graph must have at least 2 vertices".into());
82        }
83        Ok(Self { graph })
84    }
85
86    /// Get a reference to the underlying graph.
87    pub fn graph(&self) -> &G {
88        &self.graph
89    }
90
91    /// Get the number of vertices in the underlying graph.
92    pub fn num_vertices(&self) -> usize {
93        self.graph.num_vertices()
94    }
95
96    /// Get the number of edges in the underlying graph.
97    pub fn num_edges(&self) -> usize {
98        self.graph.num_edges()
99    }
100
101    /// Check if a configuration is a valid spanning tree.
102    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
103        is_valid_spanning_tree(&self.graph, config)
104    }
105}
106
107/// Check if a configuration forms a valid spanning tree:
108/// 1. Exactly n-1 edges selected
109/// 2. Selected edges form a connected subgraph (which, combined with n-1 edges, implies a tree)
110fn is_valid_spanning_tree<G: Graph>(graph: &G, config: &[bool]) -> bool {
111    let n = graph.num_vertices();
112    let edges = graph.edges();
113    if config.len() != edges.len() {
114        return false;
115    }
116
117    // Count selected edges
118    let selected_count = config.iter().filter(|&&selected| selected).count();
119    if selected_count != n - 1 {
120        return false;
121    }
122
123    // Build adjacency from selected edges and check connectivity via BFS
124    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
125    for (idx, &sel) in config.iter().enumerate() {
126        if sel {
127            let (u, v) = edges[idx];
128            adj[u].push(v);
129            adj[v].push(u);
130        }
131    }
132
133    // BFS from vertex 0
134    let mut visited = vec![false; n];
135    let mut queue = std::collections::VecDeque::new();
136    visited[0] = true;
137    queue.push_back(0);
138    while let Some(v) = queue.pop_front() {
139        for &u in &adj[v] {
140            if !visited[u] {
141                visited[u] = true;
142                queue.push_back(u);
143            }
144        }
145    }
146
147    // All vertices must be reachable
148    visited.iter().all(|&v| v)
149}
150
151/// Count the number of leaves (degree-1 vertices) in the tree defined by the config.
152fn count_leaves<G: Graph>(graph: &G, config: &[bool]) -> usize {
153    let n = graph.num_vertices();
154    let edges = graph.edges();
155    let mut degree = vec![0usize; n];
156    for (idx, &sel) in config.iter().enumerate() {
157        if sel {
158            let (u, v) = edges[idx];
159            degree[u] += 1;
160            degree[v] += 1;
161        }
162    }
163    degree.iter().filter(|&&d| d == 1).count()
164}
165
166impl<G> Problem for MaximumLeafSpanningTree<G>
167where
168    G: Graph + crate::variant::VariantParam,
169{
170    const NAME: &'static str = "MaximumLeafSpanningTree";
171    type Solution = Vec<bool>;
172    type Value = Max<i64>;
173
174    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
175
176    fn variant() -> Vec<(&'static str, &'static str)> {
177        crate::variant_params![G]
178    }
179
180    fn evaluate(
181        &self,
182        config: &Self::Solution,
183    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
184        if config.len() != self.graph.num_edges() {
185            return Err(crate::traits::EvaluationError::InvalidConfiguration(
186                "edge-selection length does not match the graph".into(),
187            ));
188        }
189        Ok({
190            if !is_valid_spanning_tree(&self.graph, config) {
191                return Ok(Max(None));
192            }
193            Max(Some(
194                i64::try_from(count_leaves(&self.graph, config)).map_err(|_| {
195                    crate::traits::EvaluationError::IntegerOverflow(
196                        "converting leaf count to i64".into(),
197                    )
198                })?,
199            ))
200        })
201    }
202}
203
204impl<G> crate::solvers::BruteForceProblem for MaximumLeafSpanningTree<G>
205where
206    G: Graph + crate::variant::VariantParam,
207{
208    fn dimensions(&self) -> Vec<usize> {
209        vec![2; self.graph.num_edges()]
210    }
211}
212
213crate::impl_random_generate!(
214    MaximumLeafSpanningTree<SimpleGraph>,
215    crate::random::SimpleGraphRandomSpec,
216    |spec| {
217        if spec.num_vertices < 2 {
218            return Err("num_vertices must be at least 2".to_string().into());
219        }
220        Ok(MaximumLeafSpanningTree::new(spec.graph()?))
221    }
222);
223
224crate::declare_variants! {
225    default MaximumLeafSpanningTree<SimpleGraph> => "1.8966^num_vertices" random,
226}
227
228crate::register_brute_force! {
229    MaximumLeafSpanningTree<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
230}
231
232#[cfg(feature = "example-db")]
233pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
234    vec![crate::example_db::specs::ModelExampleSpec {
235        id: "maximum_leaf_spanning_tree_simplegraph",
236        instance: Box::new(MaximumLeafSpanningTree::new(SimpleGraph::new(
237            6,
238            vec![
239                (0, 1),
240                (0, 2),
241                (0, 3),
242                (1, 4),
243                (2, 4),
244                (2, 5),
245                (3, 5),
246                (4, 5),
247                (1, 3),
248            ],
249        ))),
250        // 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)
251        // Tree: {(0,1),(0,2),(0,3),(2,4),(2,5)} = indices 0,1,2,4,5
252        // Leaves: 1,3,4,5 (degree 1 each), Internal: 0 (deg 3), 2 (deg 3)
253        optimal_config: serde_json::json!(vec![
254            true, true, true, false, true, true, false, false, false
255        ]),
256        optimal_value: serde_json::json!(4),
257    }]
258}
259
260#[cfg(test)]
261#[path = "../../unit_tests/models/graph/maximum_leaf_spanning_tree.rs"]
262mod tests;
problemreductions/models/graph/maximum_leaf_spanning_tree.rs

problemreductions/models/graph/
maximum_leaf_spanning_tree.rs
