Type Alias UndirectedSparseGraph

pub type UndirectedSparseGraph = SparseGraph<UndirectedEdge>;

Aliased Type

pub struct UndirectedSparseGraph {
    pub start: Vec<usize>,
    pub elist: Vec<Adjacency>,
    pub edges: Vec<(usize, usize)>,
    /* private fields */
}

Fields

start: Vec<usize>

elist: Vec<Adjacency>

edges: Vec<(usize, usize)>

Implementations

impl UndirectedSparseGraph

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,

impl UndirectedSparseGraph

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

Examples found in repository

crates/competitive/src/tree/euler_tour.rs (line 142)

    pub fn gen_lca<D: LcaMonoidDispatch>(&'a self) -> LowestCommonAncestor<'a, D> {
        D::set_depth(self.graph.tree_depth(self.root));
        let dst = DisjointSparseTable::<LcaMonoid<D>>::new(self.vtrace.clone());
        LowestCommonAncestor { euler: self, dst }
    }

impl UndirectedSparseGraph

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)

pub fn grl_5_a(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
    let d = graph.weighted_tree_depth::<AdditiveOperation<_>, _>(0, |eid| w[eid]);
    let r = (0..n).max_by_key(|&u| d[u]).unwrap();
    let ans = graph
        .weighted_tree_depth::<AdditiveOperation<_>, _>(r, |eid| w[eid])
        .into_iter()
        .max()
        .unwrap();
    writeln!(writer, "{}", ans).ok();
}

impl UndirectedSparseGraph

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

impl UndirectedSparseGraph

pub fn tree_center(&self) -> TreeCenter

tree center

Examples found in repository

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

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

impl UndirectedSparseGraph

pub fn tree_centroid(&self) -> usize

impl UndirectedSparseGraph

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

where F: FnMut(&mut T, &T),

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

where F: FnMut(&mut T, &T),