algorithms_edu/algo/graph/tree/
rooting.rs

1//! Often when working with trees we are given them as a graph with undirected edges, however
2//! sometimes a better representation is a rooted tree. This module (and the [`with_parent`] submodule) contains
3//! implementations to build a tree from its adjacency list representation with a given root id.
4//!
5//! - Time Complexity: O(V+E)
6//!
7//! # Resources
8//!
9//! - [W. Fiset's video](https://www.youtube.com/watch?v=2FFq2_je7Lg&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=9)
10
11use super::Node;
12use crate::algo::graph::UnweightedAdjacencyList;
13
14impl Node {
15    pub fn from_adjacency_list(graph: &UnweightedAdjacencyList, root: usize) -> Self {
16        fn build_tree_recursive(
17            graph: &UnweightedAdjacencyList,
18            node_id: usize,
19            parent_id: Option<usize>,
20        ) -> Node {
21            let mut node = Node::new(node_id);
22            for &child_id in &graph[node_id] {
23                if let Some(id) = parent_id {
24                    if id == child_id {
25                        continue;
26                    }
27                }
28                let child_node = build_tree_recursive(graph, child_id, Some(node_id));
29                node.children.push(child_node);
30            }
31            node
32        }
33        build_tree_recursive(graph, root, None)
34    }
35}
36
37#[cfg(test)]
38mod tests {
39    use super::*;
40
41    #[test]
42    fn test_tree_rooting() {
43        let graph = UnweightedAdjacencyList::new_undirected(
44            9,
45            &[
46                [0, 1],
47                [2, 1],
48                [2, 3],
49                [3, 4],
50                [5, 3],
51                [2, 6],
52                [6, 7],
53                [6, 8],
54            ],
55        );
56        let root = Node::from_adjacency_list(&graph, 6);
57        // Rooted at 6 the root should look like:
58        //         6
59        //      2  7  8
60        //    1  3
61        //  0   4 5
62        println!("{:?}", &root);
63        assert_eq!(
64            root,
65            Node {
66                id: 6,
67                children: vec![
68                    Node {
69                        id: 2,
70                        children: vec![
71                            Node {
72                                id: 1,
73                                children: vec![Node::new(0)]
74                            },
75                            Node {
76                                id: 3,
77                                children: vec![Node::new(4), Node::new(5)]
78                            }
79                        ]
80                    },
81                    Node::new(7),
82                    Node::new(8)
83                ]
84            }
85        );
86        let root = Node::from_adjacency_list(&graph, 3);
87        // Rooted at 3 the root should look like:
88        //       3
89        //    2  4  5
90        //  6  1
91        // 7 8  0
92        println!("{:?}", &root);
93        assert_eq!(
94            root,
95            Node {
96                id: 3,
97                children: vec![
98                    Node {
99                        id: 2,
100                        children: vec![
101                            Node {
102                                id: 1,
103                                children: vec![Node::new(0)]
104                            },
105                            Node {
106                                id: 6,
107                                children: vec![Node::new(7), Node::new(8)]
108                            }
109                        ]
110                    },
111                    Node::new(4),
112                    Node::new(5)
113                ]
114            }
115        );
116    }
117}
118
119pub mod with_parent {
120    //! This module contains implementations of tree rooting for node types that contain a pointer to the parent.
121    use crate::algo::graph::tree::with_parent::*;
122    use crate::algo::graph::UnweightedAdjacencyList;
123
124    impl Node {
125        pub fn from_adjacency_list(
126            graph: &UnweightedAdjacencyList,
127            root: usize,
128        ) -> Rc<RefCell<Node>> {
129            fn build_tree_recursive(
130                graph: &UnweightedAdjacencyList,
131                node_id: usize,
132                parent: Option<&Rc<RefCell<Node>>>,
133            ) -> Rc<RefCell<Node>> {
134                let node = Node::new(node_id, parent);
135                for &child_id in &graph[node_id] {
136                    if let Some(parent_node) = parent {
137                        if parent_node.borrow().id == child_id {
138                            continue;
139                        }
140                    }
141                    let child_node = build_tree_recursive(graph, child_id, Some(&node));
142                    node.borrow_mut().children.push(child_node);
143                }
144                node
145            }
146            build_tree_recursive(graph, root, None)
147        }
148    }
149
150    impl UnsafeTreeNode {
151        pub fn from_adjacency_list(graph: &UnweightedAdjacencyList, root: usize) -> Box<Self> {
152            fn build_tree_recursive(
153                graph: &UnweightedAdjacencyList,
154                mut node: Box<UnsafeTreeNode>,
155            ) -> Box<UnsafeTreeNode> {
156                for &child_id in &graph[node.id] {
157                    if !node.parent.is_null() && unsafe { (*node.parent).id == child_id } {
158                        continue;
159                    }
160                    let child_node = build_tree_recursive(
161                        graph,
162                        Box::new(UnsafeTreeNode::new(
163                            child_id,
164                            node.as_ref() as *const UnsafeTreeNode,
165                        )),
166                    );
167                    node.children.push(child_node);
168                }
169                node
170            }
171            build_tree_recursive(graph, Box::new(UnsafeTreeNode::new(root, std::ptr::null())))
172        }
173    }
174
175    #[cfg(test)]
176    mod tests {
177        use super::*;
178
179        #[test]
180        fn test_tree_rooting_rc() {
181            let graph = UnweightedAdjacencyList::new_undirected(
182                9,
183                &[
184                    [0, 1],
185                    [2, 1],
186                    [2, 3],
187                    [3, 4],
188                    [5, 3],
189                    [2, 6],
190                    [6, 7],
191                    [6, 8],
192                ],
193            );
194            let root = Node::from_adjacency_list(&graph, 6);
195            // Rooted at 6 the root should look like:
196            //         6
197            //      2  7  8
198            //    1  3
199            //  0   4 5
200            let _node0 = Node::new(0, None);
201            let _node1 = Node::new(1, None);
202            let _node2 = Node::new(2, None);
203            let _node3 = Node::new(3, None);
204            let _node4 = Node::new(4, None);
205            let _node5 = Node::new(5, None);
206            let _node5 = Node::new(5, None);
207            let _node6 = Node::new(6, None);
208            let _node7 = Node::new(7, None);
209            let _node8 = Node::new(8, None);
210            Node::add_child(&_node6, &_node2);
211            Node::add_child(&_node6, &_node7);
212            Node::add_child(&_node6, &_node8);
213            Node::add_child(&_node2, &_node1);
214            Node::add_child(&_node2, &_node3);
215            Node::add_child(&_node1, &_node0);
216            Node::add_child(&_node3, &_node4);
217            Node::add_child(&_node3, &_node5);
218
219            let root1 = _node6;
220
221            assert_eq!(root, root1);
222        }
223
224        #[test]
225        fn test_tree_rooting_unsafe() {
226            let mut graph = UnweightedAdjacencyList::with_size(9);
227            graph.add_undirected_edge(0, 1);
228            graph.add_undirected_edge(2, 1);
229            graph.add_undirected_edge(2, 3);
230            graph.add_undirected_edge(3, 4);
231            graph.add_undirected_edge(5, 3);
232            graph.add_undirected_edge(2, 6);
233            graph.add_undirected_edge(6, 7);
234            graph.add_undirected_edge(6, 8);
235            let tree = UnsafeTreeNode::from_adjacency_list(&graph, 6);
236            // Rooted at 6 the tree should look like:
237            //           6
238            //      2    7     8
239            //    1   3
240            //  0    4 5
241            println!("{:?}", &tree);
242            // layer 1
243            let UnsafeTreeNode {
244                id,
245                parent,
246                children,
247            } = *tree;
248            assert_eq!(id, 6);
249            assert!(parent.is_null());
250            assert_eq!(children.len(), 3);
251            let node2 = &children[0];
252            assert_eq!(node2.id, 2);
253            assert_eq!((unsafe { &*node2.parent }).id, 6);
254            assert_eq!(node2.children.len(), 2);
255
256            let tree = UnsafeTreeNode::from_adjacency_list(&graph, 3);
257            // Rooted at 3 the tree should look like:
258            //               3
259            //     2         4        5
260            //  6     1
261            // 7 8    0
262            let UnsafeTreeNode {
263                id,
264                parent,
265                children,
266            } = *tree;
267            assert_eq!(id, 3);
268            assert!(parent.is_null());
269            assert_eq!(children.len(), 3);
270            let node2 = &children[0];
271            assert_eq!(node2.id, 2);
272            assert_eq!((unsafe { &*node2.parent }).id, 3);
273            assert_eq!(node2.children.len(), 2);
274        }
275    }
276}
algorithms_edu/algo/graph/tree/rooting.rs

algorithms_edu/algo/graph/tree/
rooting.rs
