UndirectedSparseGraph

competitive::graph

Type Alias UndirectedSparseGraph 

Source 
pub type UndirectedSparseGraph = SparseGraph<UndirectedEdge>;

Aliased Type§

pub struct UndirectedSparseGraph {
    vsize: usize,
    pub start: Vec<usize>,
    pub elist: Vec<Adjacency>,
    pub edges: Vec<(usize, usize)>,
    _marker: PhantomData<fn() -> UndirectedEdge>,
}

Fields§

§vsize: usize§start: Vec<usize>§elist: Vec<Adjacency>§edges: Vec<(usize, usize)>§_marker: PhantomData<fn() -> UndirectedEdge>

Implementations§

Source§

impl UndirectedSparseGraph

Source

pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
where N: Fn(usize) -> NA, E: Fn(usize) -> EA, NA: Display, EA: Display,

Source§

impl UndirectedSparseGraph

Source

pub fn centroid_decomposition( &self, f: impl FnMut(&[usize], &[usize], usize, usize), )

1/3 centroid decomposition

  • f: (parents: &usize, vs: &usize, lsize: usize, rsize: usize)
  • 0: root, 1..=lsize: left subtree, lsize+1..=lsize+rsize: right subtree
Examples found in repository?
crates/competitive/src/tree/centroid_decomposition.rs (lines 141-166)
130    pub fn distance_frequencies(&self) -> Vec<u64> {
131        let n = self.vertices_size();
132        let mut table = vec![0u64; n];
133        if n == 0 {
134            return table;
135        }
136        table[0] = n as u64;
137        if n == 1 {
138            return table;
139        }
140        table[1] = (n * 2 - 2) as u64;
141        self.centroid_decomposition(|parents, vs, lsize, _rsize| {
142            let n = vs.len();
143            let mut dist = vec![0usize; n];
144            for i in 1..n {
145                dist[i] = dist[parents[i]] + 1;
146            }
147            let d_max = dist.iter().max().cloned().unwrap_or_default();
148            let mut f = vec![0u64; d_max + 1];
149            let mut g = vec![0u64; d_max + 1];
150            for i in 1..=lsize {
151                f[dist[i]] += 1;
152            }
153            for i in lsize + 1..n {
154                g[dist[i]] += 1;
155            }
156            while f.last().is_some_and(|&x| x == 0) {
157                f.pop();
158            }
159            while g.last().is_some_and(|&x| x == 0) {
160                g.pop();
161            }
162            let h = U64Convolve::convolve(f, g);
163            for (i, &x) in h.iter().enumerate() {
164                table[i] += x * 2;
165            }
166        });
167        table
168    }
Source

pub fn distance_frequencies(&self) -> Vec<u64>

Examples found in repository?
crates/library_checker/src/tree/frequency_table_of_tree_distance.rs (line 10)
6pub fn frequency_table_of_tree_distance(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let freqs = g.distance_frequencies();
11    iter_print!(writer, @it freqs[1..].iter().map(|&f| f / 2));
12}
Source§

impl UndirectedSparseGraph

Source

fn depth_dfs(&self, u: usize, p: usize, d: u64, depth: &mut Vec<u64>)

Examples found in repository?
crates/competitive/src/tree/depth.rs (line 9)
6    fn depth_dfs(&self, u: usize, p: usize, d: u64, depth: &mut Vec<u64>) {
7        depth[u] = d;
8        for a in self.adjacencies(u).filter(|a| a.to != p) {
9            self.depth_dfs(a.to, u, d + 1, depth);
10        }
11    }
12    pub fn tree_depth(&self, root: usize) -> Vec<u64> {
13        let mut depth = vec![0; self.vertices_size()];
14        self.depth_dfs(root, self.vertices_size(), 0, &mut depth);
15        depth
16    }
Source

pub fn tree_depth(&self, root: usize) -> Vec<u64>

Examples found in repository?
crates/competitive/src/tree/euler_tour.rs (line 142)
141    pub fn gen_lca<D: LcaMonoidDispatch>(&'a self) -> LowestCommonAncestor<'a, D> {
142        D::set_depth(self.graph.tree_depth(self.root));
143        let dst = DisjointSparseTable::<LcaMonoid<D>>::new(self.vtrace.clone());
144        LowestCommonAncestor { euler: self, dst }
145    }
Source§

impl UndirectedSparseGraph

Source

fn weighted_depth_dfs<M, F>( &self, u: usize, p: usize, d: M::T, depth: &mut Vec<M::T>, weight: &F, )
where M: Monoid, F: Fn(usize) -> M::T,

Examples found in repository?
crates/competitive/src/tree/depth.rs (line 34)
21    fn weighted_depth_dfs<M, F>(
22        &self,
23        u: usize,
24        p: usize,
25        d: M::T,
26        depth: &mut Vec<M::T>,
27        weight: &F,
28    ) where
29        M: Monoid,
30        F: Fn(usize) -> M::T,
31    {
32        for a in self.adjacencies(u).filter(|a| a.to != p) {
33            let nd = M::operate(&d, &weight(a.id));
34            self.weighted_depth_dfs::<M, _>(a.to, u, nd, depth, weight);
35        }
36        depth[u] = d;
37    }
38    pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>(
39        &self,
40        root: usize,
41        weight: F,
42    ) -> Vec<M::T> {
43        let mut depth = vec![M::unit(); self.vertices_size()];
44        self.weighted_depth_dfs::<M, _>(root, usize::MAX, M::unit(), &mut depth, &weight);
45        depth
46    }
Source

pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>( &self, root: usize, weight: F, ) -> Vec<M::T>

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_5_a.rs (line 10)
6pub fn grl_5_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
10    let d = graph.weighted_tree_depth::<AdditiveOperation<_>, _>(0, |eid| w[eid]);
11    let r = (0..n).max_by_key(|&u| d[u]).unwrap();
12    let ans = graph
13        .weighted_tree_depth::<AdditiveOperation<_>, _>(r, |eid| w[eid])
14        .into_iter()
15        .max()
16        .unwrap();
17    writeln!(writer, "{}", ans).ok();
18}
Source§

impl UndirectedSparseGraph

Source

fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>)

Examples found in repository?
crates/competitive/src/tree/depth.rs (line 54)
51    fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>) {
52        size[u] = 1;
53        for a in self.adjacencies(u).filter(|a| a.to != p) {
54            self.size_dfs(a.to, u, size);
55            size[u] += size[a.to];
56        }
57    }
58    pub fn tree_size(&self, root: usize) -> Vec<u64> {
59        let mut size = vec![0; self.vertices_size()];
60        self.size_dfs(root, usize::MAX, &mut size);
61        size
62    }
Source

pub fn tree_size(&self, root: usize) -> Vec<u64>

Source§

impl UndirectedSparseGraph

Source

pub fn tree_center(&self) -> TreeCenter

tree center

Examples found in repository?
crates/competitive/src/tree/tree_hash.rs (line 51)
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§

impl UndirectedSparseGraph

Source

pub fn tree_centroid(&self) -> usize

Source§

impl UndirectedSparseGraph

Source

pub fn tree_dp_bottom_up<T, F>(&self, root: usize, dp: &mut [T], f: F)
where F: FnMut(&mut T, &T),

Source

pub fn tree_dp_top_down<T, F>(&self, root: usize, dp: &mut [T], f: F)
where F: FnMut(&mut T, &T),