algorithms_edu/algo/graph/tree/
center.rs

1//! This algorithm finds the center(s) of an undirected tree represented by an adjacency list.
2//!
3//! - Time Complexity: $O(V+E)$
4//!
5//! # Resources
6//!
7//! - [W. Fiset's video](https://www.youtube.com/watch?v=nzF_9bjDzdc&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=10)
8
9use crate::algo::graph::UnweightedAdjacencyList;
10
11// A tree can either have one or two center(s)
12#[derive(Debug, Eq, PartialEq)]
13pub enum Center {
14    One(usize),
15    Two(usize, usize),
16}
17
18impl UnweightedAdjacencyList {
19    /// Finds the center(s) of an undirected tree.
20    /// The adjacency list must be build with undirected edges, and does not contain cycles, so that
21    /// it qualifies the definition for a tree.
22    pub fn center(&self) -> Center {
23        let n = self.node_count();
24        // Tracks the degree of each node
25        // the degee of a node is the number of its neighbours (i.e. nodes that it points to)
26        let mut degrees = vec![0; n];
27        let mut leaves = Vec::new();
28        // compute degrees and identify all leaves (i.e. nodes that are connected to only one neighbour and thus
29        // with a degree of 1)
30        self.nodes().for_each(|(i, neighbours)| {
31            let degree = neighbours.len();
32            // this also processes singleton nodes with a degree of zero
33            // (but you can treat it as `degree == 1` for the sake of simplicity, in which case the
34            // algorithm only works if the graph is not disconnected and contains only one tree)
35            if degree <= 1 {
36                leaves.push(i);
37            }
38            degrees[i] = degree;
39        });
40        let mut processed_leaves = leaves.len();
41        // Pruning leaf nodes by decreasing the degree of its neighbours.
42        // If the degree drops to 1, the node becomes a new leaf node and is added to `new_leaves`
43        // which are processed in the next round of iteration
44        // The process repeats until only the centers remain.
45        while processed_leaves < n {
46            let mut new_leaves = Vec::new();
47            for &leaf in &leaves {
48                for &neighbour in &self[leaf] {
49                    degrees[neighbour] = degrees[neighbour].saturating_sub(1);
50                    if degrees[neighbour] == 1 {
51                        new_leaves.push(neighbour);
52                    }
53                }
54            }
55            processed_leaves += new_leaves.len();
56            leaves = new_leaves;
57        }
58        match leaves.len() {
59            1 => Center::One(leaves[0]),
60            2 => Center::Two(leaves[0], leaves[1]),
61            _ => unreachable!(),
62        }
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_tree_center() {
72        let graph = UnweightedAdjacencyList::with_size(1);
73        assert_eq!(graph.center(), Center::One(0));
74
75        let mut graph = UnweightedAdjacencyList::with_size(2);
76        graph.add_undirected_edge(0, 1);
77        assert_eq!(graph.center(), Center::Two(0, 1));
78
79        let mut graph = UnweightedAdjacencyList::with_size(3);
80        graph.add_undirected_edge(0, 1);
81        graph.add_undirected_edge(1, 2);
82        assert_eq!(graph.center(), Center::One(1));
83
84        let mut graph = UnweightedAdjacencyList::with_size(9);
85        graph.add_undirected_edge(0, 1);
86        graph.add_undirected_edge(2, 1);
87        graph.add_undirected_edge(2, 3);
88        graph.add_undirected_edge(3, 4);
89        graph.add_undirected_edge(5, 3);
90        graph.add_undirected_edge(2, 6);
91        graph.add_undirected_edge(6, 7);
92        graph.add_undirected_edge(6, 8);
93        assert_eq!(graph.center(), Center::One(2));
94    }
95}
algorithms_edu/algo/graph/tree/center.rs

algorithms_edu/algo/graph/tree/
center.rs
