Struct TreeHasher

Source

pub struct TreeHasher {
    rv: Vec<u64>,
    rng: Xorshift,
}

Fields§

§rv: Vec<u64>§rng: Xorshift

Implementations§

Source §

fn mersenne_mod(a: u64) -> u64

Examples found in repository ?

crates/competitive/src/tree/tree_hash.rs (line 36)

35    fn mersenne_mul_mod(a: u64, b: u64) -> u64 {
36        Self::mersenne_mod(Self::mersenne_mul(a, b))
37    }
38    pub fn new() -> Self {
39        Self {
40            rv: Vec::new(),
41            rng: Xorshift::new(),
42        }
43    }
44    pub fn with_seed(seed: u64) -> Self {
45        Self {
46            rv: Vec::new(),
47            rng: Xorshift::new_with_seed(seed),
48        }
49    }
50    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
51        match g.tree_center() {
52            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
53            TreeCenter::Two(u, v) => {
54                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
55            }
56        }
57    }
58    pub fn hash_rooted(&mut self, g: &UndirectedSparseGraph, root: usize, parent: usize) -> u64 {
59        self.hash_rec(g, root, parent, 0)
60    }
61    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
62        let mut s = 1u64;
63        if self.rv.len() <= d {
64            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
65        }
66        for a in g.adjacencies(u) {
67            if a.to != p {
68                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
69            }
70        }
71        s += self.rv[d];
72        if s >= Self::MOD {
73            s -= Self::MOD;
74        }
75        s
76    }

Source

fn mersenne_mul(a: u64, b: u64) -> u64

Examples found in repository ?

crates/competitive/src/tree/tree_hash.rs (line 36)

35    fn mersenne_mul_mod(a: u64, b: u64) -> u64 {
36        Self::mersenne_mod(Self::mersenne_mul(a, b))
37    }

Source

fn mersenne_mul_mod(a: u64, b: u64) -> u64

Examples found in repository ?

crates/competitive/src/tree/tree_hash.rs (line 54)

50    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
51        match g.tree_center() {
52            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
53            TreeCenter::Two(u, v) => {
54                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
55            }
56        }
57    }
58    pub fn hash_rooted(&mut self, g: &UndirectedSparseGraph, root: usize, parent: usize) -> u64 {
59        self.hash_rec(g, root, parent, 0)
60    }
61    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
62        let mut s = 1u64;
63        if self.rv.len() <= d {
64            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
65        }
66        for a in g.adjacencies(u) {
67            if a.to != p {
68                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
69            }
70        }
71        s += self.rv[d];
72        if s >= Self::MOD {
73            s -= Self::MOD;
74        }
75        s
76    }

Source

pub fn new() -> Self

Source

pub fn with_seed(seed: u64) -> Self

Source

pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64

Source

pub fn hash_rooted( &mut self, g: &UndirectedSparseGraph, root: usize, parent: usize, ) -> u64

Examples found in repository ?

crates/competitive/src/tree/tree_hash.rs (line 54)

50    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
51        match g.tree_center() {
52            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
53            TreeCenter::Two(u, v) => {
54                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
55            }
56        }
57    }

Source

fn hash_rec( &mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize, ) -> u64

Examples found in repository ?

crates/competitive/src/tree/tree_hash.rs (line 52)

50    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
51        match g.tree_center() {
52            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
53            TreeCenter::Two(u, v) => {
54                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
55            }
56        }
57    }
58    pub fn hash_rooted(&mut self, g: &UndirectedSparseGraph, root: usize, parent: usize) -> u64 {
59        self.hash_rec(g, root, parent, 0)
60    }
61    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
62        let mut s = 1u64;
63        if self.rv.len() <= d {
64            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
65        }
66        for a in g.adjacencies(u) {
67            if a.to != p {
68                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
69            }
70        }
71        s += self.rv[d];
72        if s >= Self::MOD {
73            s -= Self::MOD;
74        }
75        s
76    }