algorithms_edu/algo/graph/tree/
isomorphism.rs

1//! Determines if two unrooted trees are isomorphic. This algorithm can easily be modified to support
2//! checking if two rooted trees are isomorphic.
3//!
4//! # Resources
5//!
6//! - [W. Fiset's video](https://www.youtube.com/watch?v=OCKvEMF0Xac&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=11)
7
8use crate::algo::graph::tree::center::Center;
9use crate::algo::graph::tree::Node;
10use crate::algo::graph::UnweightedAdjacencyList;
11
12impl From<Center> for Vec<usize> {
13    fn from(center: Center) -> Self {
14        match center {
15            Center::One(x) => vec![x],
16            Center::Two(x, y) => vec![x, y],
17        }
18    }
19}
20
21impl Node {
22    pub fn encode(&self) -> Vec<u8> {
23        let mut labels: Vec<_> = self.children.iter().map(|node| node.encode()).collect();
24        labels.sort();
25        let mut res = Vec::new();
26        res.push(b'(');
27        for label in &labels {
28            res.extend_from_slice(label);
29        }
30        res.push(b')');
31        res
32    }
33}
34
35impl UnweightedAdjacencyList {
36    pub fn is_isomorphic_with(&self, other: &UnweightedAdjacencyList) -> bool {
37        let this_centers: Vec<usize> = self.center().into();
38        let other_centers: Vec<usize> = other.center().into();
39        for &c1 in &this_centers {
40            let tree1 = Node::from_adjacency_list(&self, c1);
41            for &c2 in &other_centers {
42                let tree2 = Node::from_adjacency_list(&self, c2);
43                if tree1.encode() == tree2.encode() {
44                    return true;
45                }
46            }
47        }
48        false
49    }
50}
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_tree_encoding() {
58        let adj = UnweightedAdjacencyList::new_undirected(
59            10,
60            &[
61                [0, 2],
62                [0, 1],
63                [0, 3],
64                [2, 6],
65                [2, 7],
66                [1, 4],
67                [1, 5],
68                [5, 9],
69                [3, 8],
70            ],
71        );
72        let root = Node::from_adjacency_list(&adj, 0);
73        let encoded = root.encode();
74        let encoded = String::from_utf8(encoded).unwrap();
75        assert_eq!(&encoded, "(((())())(()())(()))")
76    }
77
78    #[test]
79    fn test_tree_isomorphism() {
80        let tree1 = UnweightedAdjacencyList::new_undirected(5, &[[2, 0], [3, 4], [2, 1], [2, 3]]);
81        let tree2 = UnweightedAdjacencyList::new_undirected(5, &[[1, 0], [2, 4], [1, 3], [1, 2]]);
82        assert!(tree1.is_isomorphic_with(&tree2));
83    }
84}
algorithms_edu/algo/graph/tree/isomorphism.rs

algorithms_edu/algo/graph/tree/
isomorphism.rs
