competitive/tree/
tree_center.rs

1use crate::graph::{Graph, UndirectedSparseGraph};
2
3#[codesnip::entry("tree_center")]
4#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
5pub enum TreeCenter {
6    One(usize),
7    Two(usize, usize),
8}
9#[codesnip::entry("tree_center", include("SparseGraph"))]
10impl UndirectedSparseGraph {
11    /// tree center
12    pub fn tree_center(&self) -> TreeCenter {
13        let n = self.vertices_size();
14        assert_ne!(n, 0);
15        let mut deq = std::collections::VecDeque::with_capacity(n);
16        let mut deg: Vec<_> = self.vertices().map(|u| self.neighbors(u).len()).collect();
17        for u in self.vertices() {
18            if self.neighbors(u).len() <= 1 {
19                deq.push_back(u);
20            }
21        }
22        let mut k = 0;
23        let mut cnt = deq.len();
24        if cnt < n {
25            k = deq.len();
26            'outer: while let Some(u) = deq.pop_front() {
27                k -= 1;
28                for a in self.neighbors(u) {
29                    deg[a.to] -= 1;
30                    if deg[a.to] == 1 {
31                        deq.push_back(a.to);
32                        cnt += 1;
33                        if cnt == n {
34                            break 'outer;
35                        }
36                    }
37                }
38                if k == 0 {
39                    k = deq.len();
40                }
41            }
42        }
43        if deq.len() == k + 1 {
44            TreeCenter::One(*deq.back().unwrap())
45        } else {
46            let u = deq.pop_back().unwrap();
47            let v = deq.pop_back().unwrap();
48            if u < v {
49                TreeCenter::Two(u, v)
50            } else {
51                TreeCenter::Two(v, u)
52            }
53        }
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60    use crate::{
61        graph::UndirectedSparseGraph,
62        tools::{
63            Xorshift,
64            testutil::{exhaustive_sequences, sample_usize},
65        },
66        tree::{MixedTree, PathTree, PruferSequence, StarTree},
67    };
68
69    impl UndirectedSparseGraph {
70        fn naive_tree_center(&self) -> TreeCenter {
71            let mut md: Vec<_> = self
72                .vertices()
73                .map(|u| (self.tree_depth(u).into_iter().max().unwrap_or_default(), u))
74                .collect();
75            md.sort_unstable();
76            if md.len() == 1 {
77                TreeCenter::One(md[0].1)
78            } else if md.len() >= 2 {
79                if md[0].0 == md[1].0 {
80                    TreeCenter::Two(md[0].1, md[1].1)
81                } else {
82                    TreeCenter::One(md[0].1)
83                }
84            } else {
85                panic!("vertex size should be larger than one.");
86            }
87        }
88    }
89
90    #[test]
91    fn test_center() {
92        // Prüfer sequences enumerate every labelled tree through six vertices.
93        let exhaustive = (1usize..=6).flat_map(|n| {
94            let len = n.saturating_sub(2);
95            exhaustive_sequences(0..n, len..=len).map(move |sequence| {
96                let mut degrees = vec![1; n];
97                for &v in &sequence {
98                    degrees[v] += 1;
99                }
100                let mut edges = Vec::new();
101                for v in sequence {
102                    let leaf = degrees.iter().position(|&d| d == 1).unwrap();
103                    edges.push((leaf, v));
104                    degrees[leaf] -= 1;
105                    degrees[v] -= 1;
106                }
107                let leaves: Vec<_> = (0..n).filter(|&v| degrees[v] == 1).collect();
108                if let &[a, b] = leaves.as_slice() {
109                    edges.push((a, b));
110                }
111                UndirectedSparseGraph::from_edges(n, edges)
112            })
113        });
114        let mut rng = Xorshift::default();
115        let random = sample_usize(&mut rng, 16, 1..=200, 200)
116            .into_iter()
117            .flat_map(|n| {
118                [
119                    rng.random(PathTree(n)),
120                    rng.random(StarTree(n)),
121                    rng.random(PruferSequence(n)),
122                    rng.random(MixedTree(n)),
123                ]
124            });
125        for graph in exhaustive.chain(random) {
126            assert_eq!(
127                graph.tree_center(),
128                graph.naive_tree_center(),
129                "graph={graph:?}"
130            );
131        }
132    }
133}
competitive/tree/tree_center.rs

competitive/tree/
tree_center.rs
