Struct SparseGraph 

pub struct SparseGraph<D> {
    vsize: usize,
    start: Vec<usize>,
    neighbors: Vec<Neighbor<usize, usize>>,
    pub edges: Vec<(usize, usize)>,
    _marker: PhantomData<fn() -> D>,
}

Static Sparse Graph represented as Compressed Sparse Row.

Fields

vsize: usize

start: Vec<usize>

neighbors: Vec<Neighbor<usize, usize>>

edges: Vec<(usize, usize)>

_marker: PhantomData<fn() -> D>

Implementations

impl SparseGraph<DirectedEdge>

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 SparseGraph<UndirectedEdge>

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 SparseGraph<BidirectionalEdge>

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<D> SparseGraph<D>

pub fn vertices_size(&self) -> usize

Return the number of vertices.

Examples found in repository

crates/competitive/src/graph/sparse_graph.rs (line 36)

    pub fn vertices(&self) -> ops::Range<usize> {
        0..self.vertices_size()
    }

crates/competitive/src/tree/depth.rs (line 13)

    pub fn tree_depth(&self, root: usize) -> Vec<u64> {
        let mut depth = vec![0; self.vertices_size()];
        self.depth_dfs(root, self.vertices_size(), 0, &mut depth);
        depth
    }
}

#[codesnip::entry("weighted_tree_depth", include("algebra", "SparseGraph"))]
impl UndirectedSparseGraph {
    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,
    {
        for a in self.neighbors(u).filter(|a| a.to != p) {
            let nd = M::operate(&d, &weight(a.label));
            self.weighted_depth_dfs::<M, _>(a.to, u, nd, depth, weight);
        }
        depth[u] = d;
    }
    pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>(
        &self,
        root: usize,
        weight: F,
    ) -> Vec<M::T> {
        let mut depth = vec![M::unit(); self.vertices_size()];
        self.weighted_depth_dfs::<M, _>(root, usize::MAX, M::unit(), &mut depth, &weight);
        depth
    }
}

#[codesnip::entry("tree_size", include("SparseGraph"))]
impl UndirectedSparseGraph {
    fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>) {
        size[u] = 1;
        for a in self.neighbors(u).filter(|a| a.to != p) {
            self.size_dfs(a.to, u, size);
            size[u] += size[a.to];
        }
    }
    pub fn tree_size(&self, root: usize) -> Vec<u64> {
        let mut size = vec![0; self.vertices_size()];
        self.size_dfs(root, usize::MAX, &mut size);
        size
    }

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

    pub fn new(tree: &'a UndirectedSparseGraph, root: usize) -> Self {
        let n = tree.vertices_size();
        Self {
            tree,
            root,
            vidx: vec![[0usize; 2]; n],
            eidx: vec![[0usize; 2]; n - 1],
            pos: 0,
            _marker: PhantomData,
        }
    }

    pub fn build_with_trace(mut self, mut trace: impl FnMut(usize)) -> EulerTour<K> {
        self.dfs(self.root, !0, &mut trace);
        EulerTour {
            root: self.root,
            vidx: self.vidx,
            eidx: self.eidx,
            size: self.pos,
            _marker: PhantomData,
        }
    }

    pub fn build(self) -> EulerTour<K> {
        self.build_with_trace(|_u| {})
    }

    fn dfs(&mut self, u: usize, parent: usize, trace: &mut impl FnMut(usize)) {
        self.vidx[u][0] = self.pos;
        trace(u);
        self.pos += 1;
        for a in self.tree.neighbors(u) {
            if a.to != parent {
                self.eidx[a.label][0] = self.pos;
                self.dfs(a.to, u, trace);
                self.eidx[a.label][1] = self.pos;
                if K::USE_VISIT {
                    trace(u);
                    self.pos += 1;
                }
            }
        }
        self.vidx[u][1] = self.pos;
        if K::USE_LAST {
            trace(u);
            self.pos += 1;
        }
    }
}

impl EulerTourBuilder<'_, marker::First> {
    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::First>, Vec<T>)
    where
        T: Clone,
    {
        assert_eq!(s.len(), self.tree.vertices_size());
        let mut trace = Vec::with_capacity(marker::First::size(s.len()));
        let tour = self.build_with_trace(|u| {
            trace.push(s[u].clone());
        });
        (tour, trace)
    }
}

impl EulerTourBuilder<'_, marker::FirstLast> {
    pub fn build_with_rearrange<T>(
        self,
        s: &[T],
        mut inverse: impl FnMut(T) -> T,
    ) -> (EulerTour<marker::FirstLast>, Vec<T>)
    where
        T: Clone,
    {
        assert_eq!(s.len(), self.tree.vertices_size());
        let mut visited = vec![false; s.len()];
        let mut trace = Vec::with_capacity(marker::FirstLast::size(s.len()));
        let tour = self.build_with_trace(|u| {
            if !visited[u] {
                trace.push(s[u].clone());
                visited[u] = true;
            } else {
                trace.push(inverse(s[u].clone()));
            }
        });
        (tour, trace)
    }
}

impl EulerTourBuilder<'_, marker::Visit> {
    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::Visit>, Vec<T>)
    where
        T: Clone,
    {
        assert_eq!(s.len(), self.tree.vertices_size());
        let mut trace = Vec::with_capacity(marker::Visit::size(s.len()));
        let tour = self.build_with_trace(|u| {
            trace.push(s[u].clone());
        });
        (tour, trace)
    }

crates/competitive/src/tree/rerooting.rs (line 41)

    fn build<I>(graph: &'a UndirectedSparseGraph, rooting: F, inverse: Option<I>) -> Self
    where
        I: Fn(&M::T, &M::T) -> M::T,
    {
        let dp = vec![M::unit(); graph.vertices_size()];
        let ep = vec![M::unit(); graph.vertices_size() * 2];
        let mut self_ = Self {
            graph,
            dp,
            ep,
            rooting,
        };
        self_.rerooting(inverse);
        self_
    }

crates/competitive/src/graph/low_link.rs (line 14)

    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
        let mut self_ = Self {
            graph,
            low: vec![0; graph.vertices_size()],
            ord: vec![usize::MAX; graph.vertices_size()],
            articulation: vec![],
            bridge: vec![],
        };
        for u in graph.vertices() {
            if self_.ord[u] == usize::MAX {
                self_.dfs(u, !0, &mut 0);
            }
        }
        self_
    }

crates/competitive/src/tree/tree_order.rs (line 10)

    pub fn tree_order(&self, root: usize) -> (Vec<usize>, Vec<usize>) {
        let n = self.vertices_size();
        let mut order = Vec::with_capacity(n);
        let mut parents = vec![!0usize; n];
        let mut stack = Vec::with_capacity(n);
        stack.push(root);
        while let Some(u) = stack.pop() {
            order.push(u);
            for a in self.neighbors(u).rev() {
                if a.to != parents[u] {
                    parents[a.to] = u;
                    stack.push(a.to);
                }
            }
        }
        (order, parents)
    }

Additional examples can be found in:

• crates/competitive/src/tree/tree_centroid.rs
• crates/competitive/src/tree/centroid_decomposition.rs
• crates/competitive/src/graph/maximum_flow.rs
• crates/competitive/src/graph/minimum_cost_flow.rs
• crates/competitive/src/tree/distance_frequencies.rs
• crates/competitive/src/tree/tree_center.rs
• crates/competitive/src/tree/level_ancestor.rs
• crates/competitive/src/graph/strongly_connected_component.rs
• crates/competitive/src/tree/heavy_light_decomposition.rs
• crates/competitive/src/tree/static_top_tree.rs

pub fn edges_size(&self) -> usize

Return the number of edges.

Examples found in repository

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

    fn eidx(&self, u: usize, a: Neighbor<usize, usize>) -> usize {
        a.label + self.graph.edges_size() * (u > a.to) as usize
    }
    #[inline]
    fn reidx(&self, u: usize, a: Neighbor<usize, usize>) -> usize {
        a.label + self.graph.edges_size() * (u < a.to) as usize
    }

crates/competitive/src/tree/static_top_tree.rs (line 160)

    pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self {
        let n = graph.vertices_size();
        assert!(n > 0);
        assert!(root < n);
        assert_eq!(graph.edges_size() + 1, n);

        let RootedInfo {
            order,
            children_start,
            children,
            edge_child,
            parent_edge,
        } = rooted_children(graph, root);
        let mut this = Self {
            root,
            n,
            edge_child,
            parent_edge,
            compressed: Vec::with_capacity(n.saturating_sub(1)),
            raked: Vec::with_capacity(n.saturating_sub(1)),
            vertex_links: vec![
                VertexLinks {
                    heavy_parent: usize::MAX,
                    compress_parent: usize::MAX,
                    rake_parent: usize::MAX,
                };
                n
            ],
            compress_roots: vec![None; n],
            rake_roots: vec![None; n],
        };

        let mut heavy_child = vec![usize::MAX; n];
        let mut mask = vec![1u64; n];
        let mut buckets: [Vec<Node>; 64] = std::array::from_fn(|_| Vec::new());

        for &u in order.iter().rev() {
            let children = &children[children_start[u]..children_start[u + 1]];
            let mut sum_rake = 0u64;
            for &v in children {
                sum_rake += bit_ceil(mask[v]) << 1;
            }
            mask[u] = bit_ceil(sum_rake);
            for &v in children {
                let child = bit_ceil(mask[v]) << 1;
                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
                let step = 1u64 << depth;
                let cand = ((mask[v] + step - 1) >> depth << depth) + step;
                if cand <= mask[u] {
                    mask[u] = cand;
                    heavy_child[u] = v;
                }
            }

            let mut has = 0u64;
            let mut num_light = 0usize;
            for &v in children {
                if v == heavy_child[u] {
                    continue;
                }
                num_light += 1;
                let child = bit_ceil(mask[v]) << 1;
                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
                this.build_compress(v, &heavy_child, &mask);
                buckets[depth].push(Node {
                    depth,
                    slot: Slot::RakeLeaf(v),
                });
                has |= 1u64 << depth;
            }
            if num_light == 0 {
                continue;
            }

            while num_light > 1 {
                let left = pop_bucket(&mut buckets, &mut has);
                let right = pop_bucket(&mut buckets, &mut has);
                let node = this.merge_rake(left, right);
                let depth = node.depth;
                buckets[depth].push(node);
                has |= 1u64 << depth;
                num_light -= 1;
            }

            let root = pop_bucket(&mut buckets, &mut has);
            this.rake_roots[u] = Some(root.slot);
            for &v0 in children {
                if v0 == heavy_child[u] {
                    continue;
                }
                let rake_parent = this.vertex_links[v0].rake_parent;
                let mut v = v0;
                while v != usize::MAX {
                    this.vertex_links[v].heavy_parent = u;
                    this.vertex_links[v].rake_parent = rake_parent;
                    v = heavy_child[v];
                }
            }
        }

        this.build_compress(root, &heavy_child, &mask);
        this
    }

    pub fn vertices_size(&self) -> usize {
        self.n
    }

    pub fn edges_size(&self) -> usize {
        self.edge_child.len()
    }

    pub fn dp<C>(
        &self,
        vertices: Vec<<C as Cluster>::Vertex>,
        edges: Vec<<C as Cluster>::Edge>,
    ) -> StaticTopTreeDp<'_, C>
    where
        C: Cluster,
    {
        StaticTopTreeDp::new(self, vertices, edges)
    }

    pub fn fold_all<C>(
        &self,
        vertices: &[<C as Cluster>::Vertex],
        edges: &[<C as Cluster>::Edge],
    ) -> <C as Cluster>::Point
    where
        C: Cluster,
    {
        assert_eq!(vertices.len(), self.vertices_size());
        assert_eq!(edges.len(), self.edges_size());
        let path = self.fold_compress::<C>(
            vertices,
            edges,
            self.compress_roots[self.root].expect("root compress tree must exist"),
        );
        C::add_edge(&path)
    }

    fn build_compress(&mut self, mut vertex: usize, heavy_child: &[usize], mask: &[u64]) -> Node {
        let start = vertex;
        let mut stack = Vec::new();
        while vertex != usize::MAX {
            stack.push(Node {
                depth: bit_ceil(mask[vertex]).trailing_zeros() as usize,
                slot: Slot::CompressLeaf(vertex),
            });
            loop {
                let len = stack.len();
                if len >= 3
                    && (stack[len - 3].depth == stack[len - 2].depth
                        || stack[len - 3].depth <= stack[len - 1].depth)
                {
                    let tail = stack.pop().unwrap();
                    let right = stack.pop().unwrap();
                    let left = stack.pop().unwrap();
                    let node = self.merge_compress(left, right);
                    stack.push(node);
                    stack.push(tail);
                } else if len >= 2 && stack[len - 2].depth <= stack[len - 1].depth {
                    let right = stack.pop().unwrap();
                    let left = stack.pop().unwrap();
                    stack.push(self.merge_compress(left, right));
                } else {
                    break;
                }
            }
            vertex = heavy_child[vertex];
        }
        while stack.len() > 1 {
            let right = stack.pop().unwrap();
            let left = stack.pop().unwrap();
            stack.push(self.merge_compress(left, right));
        }
        let root = stack.pop().unwrap();
        self.compress_roots[start] = Some(root.slot);
        root
    }

    fn merge_compress(&mut self, left: Node, right: Node) -> Node {
        let id = self.compressed.len();
        self.set_parent(left.slot, id << 1);
        self.set_parent(right.slot, id << 1 | 1);
        self.compressed.push(InnerNode {
            left: left.slot,
            right: right.slot,
            parent: usize::MAX,
        });
        Node {
            depth: left.depth.max(right.depth) + 1,
            slot: Slot::CompressInner(id),
        }
    }

    fn merge_rake(&mut self, left: Node, right: Node) -> Node {
        let id = self.raked.len();
        self.set_parent(left.slot, id << 1);
        self.set_parent(right.slot, id << 1 | 1);
        self.raked.push(InnerNode {
            left: left.slot,
            right: right.slot,
            parent: usize::MAX,
        });
        Node {
            depth: left.depth.max(right.depth) + 1,
            slot: Slot::RakeInner(id),
        }
    }

    fn set_parent(&mut self, slot: Slot, parent: usize) {
        match slot {
            Slot::CompressLeaf(v) => self.vertex_links[v].compress_parent = parent,
            Slot::CompressInner(i) => self.compressed[i].parent = parent,
            Slot::RakeLeaf(v) => self.vertex_links[v].rake_parent = parent,
            Slot::RakeInner(i) => self.raked[i].parent = parent,
        }
    }

    fn init_compress<C>(
        &self,
        data: &mut StaticTopTreeDataBuilder<C>,
        vertices: &[<C as Cluster>::Vertex],
        edges: &[<C as Cluster>::Edge],
        slot: Slot,
    ) -> <C as Cluster>::Path
    where
        C: Cluster,
    {
        match slot {
            Slot::CompressLeaf(vertex) => {
                let point = self.init_point(data, vertices, edges, vertex);
                C::add_vertex(
                    &point,
                    &vertices[vertex],
                    self.parent_edge_ref(edges, vertex),
                )
            }
            Slot::CompressInner(id) => {
                let node = &self.compressed[id];
                let left = self.init_compress(data, vertices, edges, node.left);
                let right = self.init_compress(data, vertices, edges, node.right);
                data.compressed[id].write(InnerValue {
                    parent: node.parent,
                    left: left.clone(),
                    right: right.clone(),
                });
                C::compress(&left, &right)
            }
            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
        }
    }

    fn fold_compress<C>(
        &self,
        vertices: &[<C as Cluster>::Vertex],
        edges: &[<C as Cluster>::Edge],
        slot: Slot,
    ) -> <C as Cluster>::Path
    where
        C: Cluster,
    {
        match slot {
            Slot::CompressLeaf(vertex) => {
                let point = self.fold_point::<C>(vertices, edges, vertex);
                C::add_vertex(
                    &point,
                    &vertices[vertex],
                    self.parent_edge_ref(edges, vertex),
                )
            }
            Slot::CompressInner(id) => {
                let node = &self.compressed[id];
                let left = self.fold_compress::<C>(vertices, edges, node.left);
                let right = self.fold_compress::<C>(vertices, edges, node.right);
                C::compress(&left, &right)
            }
            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
        }
    }

    fn init_point<C>(
        &self,
        data: &mut StaticTopTreeDataBuilder<C>,
        vertices: &[<C as Cluster>::Vertex],
        edges: &[<C as Cluster>::Edge],
        vertex: usize,
    ) -> <C as Cluster>::Point
    where
        C: Cluster,
    {
        let point = if let Some(slot) = self.rake_roots[vertex] {
            self.init_rake(data, vertices, edges, slot)
        } else {
            C::unit_point()
        };
        data.light_points[vertex] = point.clone();
        point
    }

    fn fold_point<C>(
        &self,
        vertices: &[<C as Cluster>::Vertex],
        edges: &[<C as Cluster>::Edge],
        vertex: usize,
    ) -> <C as Cluster>::Point
    where
        C: Cluster,
    {
        if let Some(slot) = self.rake_roots[vertex] {
            self.fold_rake::<C>(vertices, edges, slot)
        } else {
            C::unit_point()
        }
    }

    fn init_rake<C>(
        &self,
        data: &mut StaticTopTreeDataBuilder<C>,
        vertices: &[<C as Cluster>::Vertex],
        edges: &[<C as Cluster>::Edge],
        slot: Slot,
    ) -> <C as Cluster>::Point
    where
        C: Cluster,
    {
        match slot {
            Slot::RakeLeaf(vertex) => {
                let path = self.init_compress(
                    data,
                    vertices,
                    edges,
                    self.compress_roots[vertex].expect("light child path must exist"),
                );
                C::add_edge(&path)
            }
            Slot::RakeInner(id) => {
                let node = &self.raked[id];
                let left = self.init_rake(data, vertices, edges, node.left);
                let right = self.init_rake(data, vertices, edges, node.right);
                data.raked[id].write(InnerValue {
                    parent: node.parent,
                    left: left.clone(),
                    right: right.clone(),
                });
                C::rake(&left, &right)
            }
            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
        }
    }

    fn fold_rake<C>(
        &self,
        vertices: &[<C as Cluster>::Vertex],
        edges: &[<C as Cluster>::Edge],
        slot: Slot,
    ) -> <C as Cluster>::Point
    where
        C: Cluster,
    {
        match slot {
            Slot::RakeLeaf(vertex) => {
                let path = self.fold_compress::<C>(
                    vertices,
                    edges,
                    self.compress_roots[vertex].expect("light child path must exist"),
                );
                C::add_edge(&path)
            }
            Slot::RakeInner(id) => {
                let node = &self.raked[id];
                let left = self.fold_rake::<C>(vertices, edges, node.left);
                let right = self.fold_rake::<C>(vertices, edges, node.right);
                C::rake(&left, &right)
            }
            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
        }
    }

    fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T> {
        let edge = self.parent_edge[vertex];
        if edge == usize::MAX {
            None
        } else {
            Some(&edges[edge])
        }
    }
}

impl<'a, C> StaticTopTreeDp<'a, C>
where
    C: Cluster,
{
    pub fn new(
        tree: &'a StaticTopTree,
        vertices: Vec<<C as Cluster>::Vertex>,
        edges: Vec<<C as Cluster>::Edge>,
    ) -> Self {
        assert_eq!(vertices.len(), tree.vertices_size());
        assert_eq!(edges.len(), tree.edges_size());

        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
        let path = tree.init_compress(
            &mut data,
            &vertices,
            &edges,
            tree.compress_roots[tree.root].expect("root compress tree must exist"),
        );
        let all_point = C::add_edge(&path);
        Self {
            tree,
            vertices,
            edges,
            compressed: unsafe { assume_init_vec(data.compressed) },
            raked: unsafe { assume_init_vec(data.raked) },
            light_points: data.light_points,
            all_point,
        }
    }

    pub fn get_vertex(&self, vertex: usize) -> &<C as Cluster>::Vertex {
        &self.vertices[vertex]
    }

    pub fn apply_vertex<F>(&mut self, vertex: usize, f: F)
    where
        F: FnOnce(&mut <C as Cluster>::Vertex),
    {
        assert!(vertex < self.vertices.len());
        f(&mut self.vertices[vertex]);
        self.update_from_vertex(vertex);
    }

    pub fn set_vertex(&mut self, vertex: usize, value: <C as Cluster>::Vertex) {
        self.apply_vertex(vertex, |x| *x = value);
    }

    pub fn get_edge(&self, edge: usize) -> &<C as Cluster>::Edge {
        &self.edges[edge]
    }

    pub fn apply_edge<F>(&mut self, edge: usize, f: F)
    where
        F: FnOnce(&mut <C as Cluster>::Edge),
    {
        assert!(edge < self.edges.len());
        f(&mut self.edges[edge]);
        self.update_from_vertex(self.tree.edge_child[edge]);
    }

    pub fn set_edge(&mut self, edge: usize, value: <C as Cluster>::Edge) {
        self.apply_edge(edge, |x| *x = value);
    }

    pub fn fold_all(&self) -> &<C as Cluster>::Point {
        &self.all_point
    }

    #[inline(always)]
    pub fn fold_path(&self, mut vertex: usize) -> <C as Cluster>::Path {
        assert!(vertex < self.tree.n);
        let mut path = C::unit_path();
        let mut point = self.light_points[vertex].clone();
        loop {
            let links = self.tree.vertex_links[vertex];
            let mut left = C::unit_path();
            let mut right = C::unit_path();
            let mut compress_parent = links.compress_parent;
            while compress_parent != usize::MAX {
                let inner = &self.compressed[compress_parent / 2];
                if compress_parent & 1 == 0 {
                    right = C::compress(&right, &inner.right);
                } else {
                    left = C::compress(&inner.left, &left);
                }
                compress_parent = inner.parent;
            }
            let right_point = C::add_edge(&right);
            point = C::rake(&point, &right_point);
            let mid = C::add_vertex(
                &point,
                &self.vertices[vertex],
                self.tree.parent_edge_ref(&self.edges, vertex),
            );
            let mid = C::compress(&mid, &path);
            path = C::compress(&left, &mid);
            if links.heavy_parent == usize::MAX {
                return path;
            }

            point = C::unit_point();
            let mut rake_parent = links.rake_parent;
            while rake_parent != usize::MAX {
                let inner = &self.raked[rake_parent / 2];
                if rake_parent & 1 == 0 {
                    point = C::rake(&point, &inner.right);
                } else {
                    point = C::rake(&inner.left, &point);
                }
                rake_parent = inner.parent;
            }
            vertex = links.heavy_parent;
        }
    }

    fn update_from_vertex(&mut self, mut vertex: usize) {
        assert!(vertex < self.tree.n);
        while vertex != usize::MAX {
            let links = self.tree.vertex_links[vertex];
            let base = C::add_vertex(
                &self.light_points[vertex],
                &self.vertices[vertex],
                self.tree.parent_edge_ref(&self.edges, vertex),
            );
            let path = self.update_compress(links.compress_parent, base);
            let point = C::add_edge(&path);
            let point = self.update_rake(links.rake_parent, point);
            if links.heavy_parent == usize::MAX {
                self.all_point = point;
            } else {
                self.light_points[links.heavy_parent] = point;
            }
            vertex = links.heavy_parent;
        }
    }

    fn update_compress(
        &mut self,
        mut id: usize,
        mut path: <C as Cluster>::Path,
    ) -> <C as Cluster>::Path {
        while id != usize::MAX {
            let inner = &mut self.compressed[id / 2];
            if id & 1 == 0 {
                inner.left = path;
            } else {
                inner.right = path;
            }
            path = C::compress(&inner.left, &inner.right);
            id = inner.parent;
        }
        path
    }

    fn update_rake(
        &mut self,
        mut id: usize,
        mut point: <C as Cluster>::Point,
    ) -> <C as Cluster>::Point {
        while id != usize::MAX {
            let inner = &mut self.raked[id / 2];
            if id & 1 == 0 {
                inner.left = point;
            } else {
                inner.right = point;
            }
            point = C::rake(&inner.left, &inner.right);
            id = inner.parent;
        }
        point
    }
}

struct StaticTopTreeDataBuilder<C>
where
    C: Cluster,
{
    compressed: Vec<MaybeUninit<InnerValue<<C as Cluster>::Path>>>,
    raked: Vec<MaybeUninit<InnerValue<<C as Cluster>::Point>>>,
    light_points: Vec<<C as Cluster>::Point>,
}

impl<C> StaticTopTreeDataBuilder<C>
where
    C: Cluster,
{
    fn new(tree: &StaticTopTree) -> Self {
        let mut compressed = Vec::with_capacity(tree.compressed.len());
        compressed.resize_with(tree.compressed.len(), MaybeUninit::uninit);
        let mut raked = Vec::with_capacity(tree.raked.len());
        raked.resize_with(tree.raked.len(), MaybeUninit::uninit);
        Self {
            compressed,
            raked,
            light_points: vec![C::unit_point(); tree.n],
        }
    }
}

unsafe fn assume_init_vec<T>(mut vec: Vec<MaybeUninit<T>>) -> Vec<T> {
    let len = vec.len();
    let cap = vec.capacity();
    let ptr = vec.as_mut_ptr() as *mut T;
    std::mem::forget(vec);
    unsafe { Vec::from_raw_parts(ptr, len, cap) }
}

fn bit_ceil(x: u64) -> u64 {
    if x <= 1 { 1 } else { x.next_power_of_two() }
}

fn rooted_children(graph: &UndirectedSparseGraph, root: usize) -> RootedInfo {
    let n = graph.vertices_size();
    let mut order = Vec::with_capacity(n);
    let mut parent = vec![usize::MAX; n];
    let mut parent_edge = vec![usize::MAX; n];
    let mut edge_child = vec![0; graph.edges_size()];
    order.push(root);
    parent[root] = usize::MAX;
    for i in 0..n {
        let u = order[i];
        for a in graph.neighbors(u) {
            if a.to == parent[u] {
                continue;
            }
            parent[a.to] = u;
            parent_edge[a.to] = a.label;
            edge_child[a.label] = a.to;
            order.push(a.to);
        }
    }
    let mut children_start = vec![0usize; n + 1];
    for &v in order.iter().skip(1) {
        children_start[parent[v] + 1] += 1;
    }
    for i in 1..=n {
        children_start[i] += children_start[i - 1];
    }
    let mut children = vec![0; n.saturating_sub(1)];
    let mut child_pos = children_start.clone();
    for &v in order.iter().skip(1) {
        let pos = child_pos[parent[v]];
        children[pos] = v;
        child_pos[parent[v]] += 1;
    }
    RootedInfo {
        order,
        children_start,
        children,
        edge_child,
        parent_edge,
    }
}

pub fn vertices(&self) -> Range<usize>

Return an iterator over graph vertices.

Examples found in repository

crates/aizu_online_judge/src/grl/grl_1_a.rs (line 12)

pub fn grl_1_a(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
    let cost = graph.standard_sp_additive().dijkstra([r], |eid| d[eid]);
    for u in graph.vertices() {
        if cost[u].is_maximum() {
            pp!("INF");
        } else {
            pp!(cost[u]);
        }
    }
}

#[verify::aizu_online_judge("GRL_1_A")]
pub fn grl_1_a_option(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
    let cost = graph.option_sp_additive().dijkstra([r], |eid| Some(d[eid]));
    for u in graph.vertices() {
        match cost[u] {
            Some(d) => pp!(d),
            None => pp!("INF"),
        };
    }
}

crates/competitive/src/graph/low_link.rs (line 19)

    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
        let mut self_ = Self {
            graph,
            low: vec![0; graph.vertices_size()],
            ord: vec![usize::MAX; graph.vertices_size()],
            articulation: vec![],
            bridge: vec![],
        };
        for u in graph.vertices() {
            if self_.ord[u] == usize::MAX {
                self_.dfs(u, !0, &mut 0);
            }
        }
        self_
    }

crates/aizu_online_judge/src/grl/grl_1_b.rs (line 12)

pub fn grl_1_b(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
    let cost = graph
        .option_sp_additive()
        .bellman_ford([r], |eid| Some(d[eid]), true);
    if let Some(cost) = cost {
        for u in graph.vertices() {
            match cost[u] {
                Some(d) => pp!(d),
                None => pp!("INF"),
            };
        }
    } else {
        pp!("NEGATIVE CYCLE");
    }
}

crates/competitive/src/graph/graphvis.rs (line 14)

    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,
    {
        let mut s = String::new();
        s.push_str("digraph G {\n    graph [ splines=false, layout=neato ];\n");
        for u in self.vertices() {
            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
        }
        for u in self.vertices() {
            for a in self.neighbors(u) {
                writeln!(s, "    {} -> {} [{}];", u, a.to, edge_attr(a.label)).ok();
            }
        }
        s.push('}');
        s
    }
}

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,
    {
        let mut s = String::new();
        s.push_str("graph G {\n    graph [ splines=false, layout=neato ];\n");
        for u in self.vertices() {
            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
        }
        for (i, (u, v)) in self.edges.iter().cloned().enumerate() {
            writeln!(s, "    {} -- {} [{}];", u, v, edge_attr(i)).ok();
        }
        s.push('}');
        s
    }
}

impl BidirectionalSparseGraph {
    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,
    {
        let mut s = String::new();
        s.push_str("digraph G {\n    graph [ splines=false, layout=neato ];\n");
        for u in self.vertices() {
            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
        }
        for u in self.vertices() {
            for a in self.neighbors(u) {
                writeln!(s, "    {} -> {} [{}];", u, a.to, edge_attr(a.label)).ok();
            }
        }
        s.push('}');
        s
    }

crates/aizu_online_judge/src/grl/grl_1_c.rs (line 14)

pub fn grl_1_c(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(vs, es, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
    let cost = graph
        .option_sp_additive()
        .warshall_floyd_ap(|eid| Some(Saturating(d[eid])));
    if graph.vertices().any(|u| cost[u][u].unwrap().0 < 0) {
        pp!("NEGATIVE CYCLE");
    } else {
        for u in graph.vertices() {
            for v in graph.vertices() {
                match cost[u][v] {
                    Some(d) => pp!(d.0, !),
                    None => pp!("INF", !),
                };
                pp!(if v + 1 == vs { '\n' } else { ' ' }, !);
            }
        }
    }
}

crates/competitive/src/graph/minimum_cost_flow.rs (line 85)

    fn bellman_ford(&mut self, s: usize) {
        self.potential.clear();
        self.potential.resize(self.graph.vertices_size(), i64::MAX);
        self.potential[s] = 0;
        for _ in 1..self.graph.vertices_size() {
            let mut end = true;
            for u in self.graph.vertices() {
                if self.potential[u] == i64::MAX {
                    continue;
                }
                for a in self.graph.neighbors(u) {
                    if self.capacities[a.label] == 0 {
                        continue;
                    }
                    let ncost = self.potential[u].saturating_add(self.costs[a.label]);
                    if self.potential[a.to] > ncost {
                        self.potential[a.to] = ncost;
                        end = false;
                    }
                }
            }
            if end {
                break;
            }
        }
    }

Additional examples can be found in:

• crates/competitive/src/tree/tree_center.rs
• crates/competitive/src/graph/strongly_connected_component.rs

pub fn builder<T>(vsize: usize) -> SparseGraphBuilder<T, D>

pub fn builder_with_esize<T>( vsize: usize, esize: usize, ) -> SparseGraphBuilder<T, D>

impl<D> SparseGraph<D>

where D: SparseGraphConstruction,

pub fn from_edges(vsize: usize, edges: Vec<(usize, usize)>) -> Self

Construct graph from edges.

Examples found in repository

crates/competitive/src/graph/sparse_graph.rs (line 185)

    pub fn build(self) -> (SparseGraph<D>, Vec<T>) {
        let graph = SparseGraph::from_edges(self.vsize, self.edges);
        (graph, self.rest)
    }

crates/competitive/src/graph/maximum_flow.rs (line 29)

    pub fn gen_graph(&mut self) -> BidirectionalSparseGraph {
        let edges = std::mem::take(&mut self.edges);
        BidirectionalSparseGraph::from_edges(self.vsize, edges)
    }

crates/competitive/src/graph/minimum_cost_flow.rs (line 32)

    pub fn gen_graph(&mut self) -> BidirectionalSparseGraph {
        let edges = std::mem::take(&mut self.edges);
        BidirectionalSparseGraph::from_edges(self.vsize, edges)
    }

crates/competitive/src/tree/generator.rs (line 15)

    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
        let n = rng.random(&self.0);
        let edges = from_prufer_sequence(
            n,
            &rng.random_iter(0..n)
                .take(n.saturating_sub(2))
                .collect::<Vec<usize>>(),
        );
        UndirectedSparseGraph::from_edges(n, edges)
    }
}

pub struct PathTree<T>(pub T);

impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for PathTree<T> {
    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
        let n = rng.random(&self.0);
        let edges = (1..n).map(|u| (u - 1, u)).collect();
        UndirectedSparseGraph::from_edges(n, edges)
    }
}

pub struct StarTree<T>(pub T);

impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for StarTree<T> {
    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
        let n = rng.random(&self.0);
        let edges = (1..n).map(|u| (0, u)).collect();
        UndirectedSparseGraph::from_edges(n, edges)
    }
}

pub struct MixedTree<T>(pub T);

impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for MixedTree<T> {
    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
            let mut edges = Vec::with_capacity(n.saturating_sub(1));
            if n >= 2 {
                let k = rng.random(1..n);
                for n in [k, n - k].iter().cloned() {
                    let ty = rng.rand(6);
                    edges.extend(match ty {
                        0 => from_prufer_sequence(
                            n,
                            &rng.random_iter(0..n)
                                .take(n.saturating_sub(2))
                                .collect::<Vec<usize>>(),
                        ),
                        1 => (1..n).map(|u| (u - 1, u)).collect(),
                        2 => (1..n).map(|u| (0, u)).collect(),
                        _ => rand_inner(n, rng),
                    });
                }
                for (u, v) in edges[k - 1..].iter_mut() {
                    *u += k;
                    *v += k;
                }
                edges.push((rng.random(0..k), rng.random(k..n)));
            }
            edges
        }
        let n = rng.random(&self.0);
        let edges = rand_inner(n, rng);
        UndirectedSparseGraph::from_edges(n, edges)
    }

crates/library_checker/src/tree/lca.rs (line 23)

pub fn lca_hld(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, p: [usize; iter n - 1]);
    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let hld = graph.hld(0);
    for _ in 0..q {
        sc!(u, v);
        pp!(hld.lca(u, v));
    }
}

crates/library_checker/src/graph/scc.rs (line 8)

pub fn scc(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(vs, es, edges: [(usize, usize); es]);
    let graph = DirectedSparseGraph::from_edges(vs, edges);
    let scc = StronglyConnectedComponent::new(&graph);
    let comp = scc.components();
    pp!(comp.len());
    for vs in comp.into_iter() {
        pp!(vs.len(), @it vs);
    }
}

Additional examples can be found in:

• crates/aizu_online_judge/src/grl/grl_5_c.rs
• crates/competitive/src/graph/two_satisfiability.rs
• crates/competitive/src/graph/strongly_connected_component.rs
• crates/library_checker/src/graph/two_edge_connected_components.rs
• crates/library_checker/src/tree/vertex_add_subtree_sum.rs
• crates/aizu_online_judge/src/grl/grl_5_d.rs
• crates/aizu_online_judge/src/grl/grl_5_e.rs
• crates/library_checker/src/data_structure/persistent_unionfind.rs
• crates/competitive/src/graph/dulmage_mendelsohn_decomposition.rs
• crates/competitive/src/algorithm/doubling.rs
• crates/competitive/src/tree/centroid_decomposition.rs

pub fn reverse_graph(&self) -> SparseGraph<D>

impl SparseGraph<UndirectedEdge>

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/distance_frequencies.rs (lines 15-40)

    pub fn distance_frequencies(&self) -> Vec<u64> {
        let n = self.vertices_size();
        let mut table = vec![0u64; n];
        if n == 0 {
            return table;
        }
        table[0] = n as u64;
        if n == 1 {
            return table;
        }
        table[1] = (n * 2 - 2) as u64;
        self.centroid_decomposition(|parents, vs, lsize, _rsize| {
            let n = vs.len();
            let mut dist = vec![0usize; n];
            for i in 1..n {
                dist[i] = dist[parents[i]] + 1;
            }
            let d_max = dist.iter().max().cloned().unwrap_or_default();
            let mut f = vec![0u64; d_max + 1];
            let mut g = vec![0u64; d_max + 1];
            for i in 1..=lsize {
                f[dist[i]] += 1;
            }
            for i in lsize + 1..n {
                g[dist[i]] += 1;
            }
            while f.last().is_some_and(|&x| x == 0) {
                f.pop();
            }
            while g.last().is_some_and(|&x| x == 0) {
                g.pop();
            }
            let h = U64Convolve::convolve(f, g);
            for (i, &x) in h.iter().enumerate() {
                table[i] += x * 2;
            }
        });
        table
    }

pub fn contour_query_range(&self) -> ContourQueryRange

Examples found in repository

crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 17)

pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = cq
        .component_sizes()
        .map(|n| BinaryIndexedTree::new(n + 1))
        .collect();

    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { v, l, r, x } => {
                cq.for_each_contour_range(v, l, r, |c, start, end| {
                    bits[c].update(start, x);
                    bits[c].update(end, -x);
                });
                if l == 0 && 0 < r {
                    a[v] += x;
                }
            }
            Query::Get { v } => {
                let mut ans = a[v];
                cq.for_each_index(v, |c, i| ans += bits[c].accumulate(i));
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 17)

pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut raw: Vec<_> = cq.component_sizes().map(|n| vec![0; n]).collect();
    for (v, &x) in a.iter().enumerate() {
        cq.for_each_index(v, |c, i| raw[c][i] += x);
    }
    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = raw
        .into_iter()
        .map(|values| BinaryIndexedTree::from_slice(&values))
        .collect();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                cq.for_each_index(p, |c, i| bits[c].update(i, x));
            }
            Query::Sum { v, l, r } => {
                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
                cq.for_each_contour_range(v, l, r, |c, start, end| {
                    ans += bits[c].fold_abelian(start, end);
                });
                pp!(ans);
            }
        }
    }
}

impl SparseGraph<UndirectedEdge>

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)

    fn depth_dfs(&self, u: usize, p: usize, d: u64, depth: &mut Vec<u64>) {
        depth[u] = d;
        for a in self.neighbors(u).filter(|a| a.to != p) {
            self.depth_dfs(a.to, u, d + 1, depth);
        }
    }
    pub fn tree_depth(&self, root: usize) -> Vec<u64> {
        let mut depth = vec![0; self.vertices_size()];
        self.depth_dfs(root, self.vertices_size(), 0, &mut depth);
        depth
    }

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

impl SparseGraph<UndirectedEdge>

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)

    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,
    {
        for a in self.neighbors(u).filter(|a| a.to != p) {
            let nd = M::operate(&d, &weight(a.label));
            self.weighted_depth_dfs::<M, _>(a.to, u, nd, depth, weight);
        }
        depth[u] = d;
    }
    pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>(
        &self,
        root: usize,
        weight: F,
    ) -> Vec<M::T> {
        let mut depth = vec![M::unit(); self.vertices_size()];
        self.weighted_depth_dfs::<M, _>(root, usize::MAX, M::unit(), &mut depth, &weight);
        depth
    }

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 8)

pub fn grl_5_a(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(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();
    pp!(ans);
}

impl SparseGraph<UndirectedEdge>

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

Examples found in repository

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

    fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>) {
        size[u] = 1;
        for a in self.neighbors(u).filter(|a| a.to != p) {
            self.size_dfs(a.to, u, size);
            size[u] += size[a.to];
        }
    }
    pub fn tree_size(&self, root: usize) -> Vec<u64> {
        let mut size = vec![0; self.vertices_size()];
        self.size_dfs(root, usize::MAX, &mut size);
        size
    }

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

impl SparseGraph<UndirectedEdge>

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

Examples found in repository

crates/library_checker/src/tree/frequency_table_of_tree_distance.rs (line 8)

pub fn frequency_table_of_tree_distance(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, (g, _): @TreeGraphScanner::<usize>::new(n));
    let freqs = g.distance_frequencies();
    pp!(@it freqs[1..].iter().map(|&f| f / 2));
}

impl SparseGraph<UndirectedEdge>

pub fn subtree_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, First>

pub fn path_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, FirstLast>

Examples found in repository

crates/aizu_online_judge/src/grl/grl_5_d.rs (line 23)

pub fn grl_5_d(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, c: [SizedCollect<usize>; iter n]);
    let edges = c
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let et = graph.path_euler_tour_builder(0).build();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);

    sc!(q);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { v, w } => {
                et.update(v, w, -w, |k, x| bit.update(k, x));
            }
            Query::Get { u } => {
                let ans = et.fold(u, |k| bit.accumulate(k));
                pp!(ans);
            }
        }
    }
}

pub fn full_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, Visit>

pub fn lca(&self, root: usize) -> LowestCommonAncestor

Examples found in repository

crates/aizu_online_judge/src/grl/grl_5_c.rs (line 13)

pub fn grl_5_c(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, c: [SizedCollect<usize>; iter n]);
    let edges = c
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let tree = UndirectedSparseGraph::from_edges(n, edges);
    let lca = tree.lca(0);
    sc!(q, uv: [(usize, usize); iter q]);
    for (u, v) in uv {
        pp!(lca.lca(u, v));
    }
}

crates/library_checker/src/tree/jump_on_tree.rs (line 20)

pub fn jump_on_tree_level_ancestor(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
    let la = g.level_ancestor(0);
    let lca = g.lca(0);
    for _ in 0..q {
        sc!(s, t, i);
        let l = lca.lca(s, t);
        let dl = la.depth(l);
        let ds = la.depth(s) - dl;
        let dt = la.depth(t) - dl;
        let ans = if i <= ds {
            la.la(s, i)
        } else if i <= ds + dt {
            la.la(t, ds + dt - i)
        } else {
            None
        };
        pp!(ans.unwrap_or(!0) as isize);
    }
}

#[verify::library_checker("jump_on_tree")]
pub fn jump_on_tree_level_ancestor_batch(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize); iter q]);
    let lca = g.lca(0);
    let results = g.level_ancestor_batch(
        0,
        queries.map(|(s, t, i)| {
            let l = lca.lca(s, t);
            let dl = lca.depth(l);
            let ds = lca.depth(s) - dl;
            let dt = lca.depth(t) - dl;
            if i <= ds {
                (s, i)
            } else if i <= ds + dt {
                (t, ds + dt - i)
            } else {
                (0, n)
            }
        }),
    );
    pp!(@lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
}

impl SparseGraph<UndirectedEdge>

pub fn hld(&self, root: usize) -> HeavyLightDecomposition

Examples found in repository

crates/library_checker/src/tree/jump_on_tree.rs (line 8)

pub fn jump_on_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
    let hld = g.hld(0);
    for _ in 0..q {
        sc!(s, t, i);
        pp!(hld.jump(s, t, i).unwrap_or(!0) as isize);
    }
}

crates/library_checker/src/tree/lca.rs (line 24)

pub fn lca_hld(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, p: [usize; iter n - 1]);
    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let hld = graph.hld(0);
    for _ in 0..q {
        sc!(u, v);
        pp!(hld.lca(u, v));
    }
}

crates/library_checker/src/tree/vertex_set_path_composite.rs (line 17)

pub fn vertex_set_path_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, ab: [(M, M); n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let hld = graph.hld(0);
    let mut fold = hld.build_fold::<LinearOperation<_>>(&ab);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Set { p, cd } => {
                fold.set(p, cd);
            }
            Query::Apply { u, v, x } => {
                let (a, b) = fold.fold_vertices(u, v);
                pp!(a * x + b);
            }
        }
    }
}

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 43)

pub fn vertex_add_subtree_sum_hld(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
    let tree = UndirectedSparseGraph::from_edges(n, edges);
    let hld = tree.hld(0);
    let mut b = vec![0; n];
    for (v, x) in a.into_iter().enumerate() {
        b[hld.index(v)] = x;
    }
    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { u, x } => seg.update(hld.index(u), x),
            Query::Sum { u } => {
                pp!(seg.fold(hld.subtree_range(u)));
            }
        }
    }
}

crates/aizu_online_judge/src/grl/grl_5_e.rs (line 23)

pub fn grl_5_e(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, c: [SizedCollect<usize>; iter n]);
    let edges = c
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let hld = graph.hld(0);
    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0u64, n));

    sc!(q);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { v, w } => {
                hld.path_edges(0, v, |l, r| seg.update(l..r, w));
            }
            Query::Get { u } => {
                let mut ans = 0;
                hld.path_edges(0, u, |l, r| ans += seg.fold(l..r).0);
                pp!(ans);
            }
        }
    }
}

impl SparseGraph<UndirectedEdge>

pub fn level_ancestor(&self, root: usize) -> LevelAncestor

Examples found in repository

crates/library_checker/src/tree/jump_on_tree.rs (line 19)

pub fn jump_on_tree_level_ancestor(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
    let la = g.level_ancestor(0);
    let lca = g.lca(0);
    for _ in 0..q {
        sc!(s, t, i);
        let l = lca.lca(s, t);
        let dl = la.depth(l);
        let ds = la.depth(s) - dl;
        let dt = la.depth(t) - dl;
        let ans = if i <= ds {
            la.la(s, i)
        } else if i <= ds + dt {
            la.la(t, ds + dt - i)
        } else {
            None
        };
        pp!(ans.unwrap_or(!0) as isize);
    }
}

crates/competitive/src/algorithm/doubling.rs (line 278)

    pub fn new(size: usize, f: impl Fn(usize) -> (usize, M::T)) -> Self {
        let (next, value): (Vec<_>, Vec<_>) = (0..size).map(f).unzip();

        let mut indeg = vec![0usize; size];
        for &to in &next {
            indeg[to] += 1;
        }
        let mut in_cycle = vec![true; size];
        let mut deq = VecDeque::new();
        for (u, &deg) in indeg.iter().enumerate() {
            if deg == 0 {
                deq.push_back(u);
            }
        }
        while let Some(u) = deq.pop_front() {
            in_cycle[u] = false;
            indeg[next[u]] -= 1;
            if indeg[next[u]] == 0 {
                deq.push_back(next[u]);
            }
        }

        let mut cycle_id = vec![!0; size];
        let mut cycle_pos = vec![!0; size];
        let mut cycles = Vec::new();
        for i in 0..size {
            if in_cycle[i] && cycle_id[i] == !0 {
                let mut cycle = Vec::new();
                let mut u = i;
                loop {
                    cycle_id[u] = cycles.len();
                    cycle_pos[u] = cycle.len();
                    cycle.push(u);
                    u = next[u];
                    if u == i {
                        break;
                    }
                }
                cycles.push(cycle);
            }
        }

        let mut rev = vec![Vec::new(); size];
        for u in 0..size {
            rev[next[u]].push(u);
        }

        let mut depth_to_cycle = vec![0usize; size];
        let mut cycle_entry = vec![!0; size];
        let mut prefix_up = Vec::with_capacity(size);
        prefix_up.resize_with(size, M::unit);
        let mut q = VecDeque::new();
        for i in 0..size {
            if in_cycle[i] {
                cycle_entry[i] = i;
                prefix_up[i] = M::operate(&value[i], &M::unit());
                q.push_back(i);
            }
        }
        while let Some(u) = q.pop_front() {
            for &v in &rev[u] {
                if in_cycle[v] || cycle_entry[v] != !0 {
                    continue;
                }
                cycle_entry[v] = cycle_entry[u];
                depth_to_cycle[v] = depth_to_cycle[u] + 1;
                cycle_id[v] = cycle_id[u];
                prefix_up[v] = M::operate(&value[v], &prefix_up[u]);
                q.push_back(v);
            }
        }

        let mut cycle_prefix = Vec::with_capacity(cycles.len());
        for cycle in &cycles {
            let len = cycle.len();
            let mut pref = Vec::with_capacity(2 * len + 1);
            pref.push(M::unit());
            for i in 0..2 * len {
                let v = cycle[i % len];
                let next_val = M::operate(pref.last().unwrap(), &value[v]);
                pref.push(next_val);
            }
            cycle_prefix.push(pref);
        }

        let root = size;
        let mut edges = Vec::with_capacity(size);
        for u in 0..size {
            if in_cycle[u] {
                edges.push((u, root));
            } else {
                edges.push((u, next[u]));
            }
        }
        let graph = UndirectedSparseGraph::from_edges(size + 1, edges);
        let la = graph.level_ancestor(root);

        Self {
            depth_to_cycle,
            cycle_entry,
            cycle_id,
            cycle_pos,
            cycles,
            cycle_prefix,
            prefix_up,
            la,
        }
    }

pub fn level_ancestor_batch( &self, root: usize, queries: impl IntoIterator<Item = (usize, usize)>, ) -> Vec<Option<usize>>

Examples found in repository

crates/library_checker/src/tree/jump_on_tree.rs (lines 43-58)

pub fn jump_on_tree_level_ancestor_batch(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize); iter q]);
    let lca = g.lca(0);
    let results = g.level_ancestor_batch(
        0,
        queries.map(|(s, t, i)| {
            let l = lca.lca(s, t);
            let dl = lca.depth(l);
            let ds = lca.depth(s) - dl;
            let dt = lca.depth(t) - dl;
            if i <= ds {
                (s, i)
            } else if i <= ds + dt {
                (t, ds + dt - i)
            } else {
                (0, n)
            }
        }),
    );
    pp!(@lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
}

impl SparseGraph<UndirectedEdge>

pub fn static_top_tree(&self, root: usize) -> StaticTopTree

Examples found in repository

crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 110)

pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n,
        q,
        value: [M; n],
        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));

    let top_tree = graph.static_top_tree(0);
    let mut dp = top_tree.dp::<Dp>(value, edges);

    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::SetVertex { v, x } => {
                dp.set_vertex(v, x);
                pp!(dp.fold_all().sum);
            }
            Query::SetEdge { e, a, b } => {
                dp.set_edge(e, (a, b));
                pp!(dp.fold_all().sum);
            }
        }
    }
}

crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 144)

pub fn point_set_tree_path_composite_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n,
        q,
        value: [M; n],
        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));

    let top_tree = graph.static_top_tree(0);
    let mut dp = top_tree.dp::<Dp>(value, edges);

    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::SetVertex { v, x, r } => {
                dp.set_vertex(v, x);
                pp!(dp.fold_path(r).reverse.sum);
            }
            Query::SetEdge { e, a, b, r } => {
                dp.set_edge(e, (a, b));
                pp!(dp.fold_path(r).reverse.sum);
            }
        }
    }
}

impl SparseGraph<UndirectedEdge>

pub fn tree_center(&self) -> TreeCenter

tree center

Examples found in repository

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

    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 SparseGraph<UndirectedEdge>

pub fn tree_centroid(&self) -> usize

impl SparseGraph<UndirectedEdge>

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),

impl<D> SparseGraph<D>

where D: SparseGraphConstruction,

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

(order, parents)

Examples found in repository

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

    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
        let (order, parents) = self.tree_order(root);
        LowestCommonAncestor::from_dfs_preorder(&parents, &order)
    }

crates/competitive/src/tree/level_ancestor.rs (line 14)

    pub fn level_ancestor(&self, root: usize) -> LevelAncestor {
        let n = self.vertices_size();
        let (order, parent) = self.tree_order(root);
        let mut depth = vec![0; n];
        for &u in order.iter().skip(1) {
            depth[u] = depth[parent[u]] + 1;
        }
        let mut height = vec![1; n];
        let mut heavy = vec![n; n];
        for &u in order.iter().skip(1).rev() {
            let p = parent[u];
            if heavy[p] == n || height[heavy[p]] < height[u] {
                heavy[p] = u;
            }
            height[p] = height[p].max(height[u] + 1);
        }

        let mut start = vec![0; n];
        let mut index = vec![0; n];
        let mut ladder = Vec::with_capacity(2 * n);
        for &head in &order {
            if head != root && heavy[parent[head]] == head {
                continue;
            }
            let extension = height[head].min(depth[head]);
            let offset = ladder.len();
            ladder.resize(offset + extension + height[head], n);
            let mut u = head;
            for i in (0..extension).rev() {
                u = parent[u];
                ladder[offset + i] = u;
            }
            let mut u = head;
            for i in extension..extension + height[head] {
                ladder[offset + i] = u;
                start[u] = offset;
                index[u] = offset + i;
                u = heavy[u];
            }
        }

        LevelAncestor {
            parent,
            depth,
            start,
            index,
            ladder,
        }
    }

    pub fn level_ancestor_batch(
        &self,
        root: usize,
        queries: impl IntoIterator<Item = (usize, usize)>,
    ) -> Vec<Option<usize>> {
        let n = self.vertices_size();
        let mut start = vec![0; n + 1];
        let queries: Vec<(usize, usize)> = queries.into_iter().collect();
        for &(u, _) in &queries {
            start[u] += 1;
        }
        for d in 0..n {
            start[d + 1] += start[d];
        }
        let qsize = queries.len();
        let mut batch = vec![(0, 0); qsize];
        for (i, &(u, k)) in queries.iter().enumerate() {
            start[u] -= 1;
            batch[start[u]] = (k, i);
        }
        let (order, parent) = self.tree_order(root);
        let mut path = Vec::with_capacity(n);
        let mut results = vec![None; qsize];
        for u in order {
            while path.last().is_some_and(|&v| v != parent[u]) {
                path.pop();
            }
            path.push(u);
            for &(k, qi) in &batch[start[u]..start[u + 1]] {
                let depth = path.len() - 1;
                if k <= depth {
                    results[qi] = Some(path[depth - k]);
                }
            }
        }
        results
    }

crates/competitive/src/tree/rerooting.rs (line 73)

    fn rerooting<I: Fn(&M::T, &M::T) -> M::T>(&mut self, inverse: Option<I>) {
        let (order, parents) = self.graph.tree_order(0);
        for &u in order.iter().skip(1).rev() {
            let mut sum = M::unit();
            let mut parent = None;
            for a in self.graph.neighbors(u) {
                if a.to == parents[u] {
                    parent = Some(a);
                } else {
                    sum = self.merge(&sum, &self.ep[self.eidx(u, a)]);
                }
            }
            let a = parent.unwrap();
            let i = self.reidx(u, a);
            self.ep[i] = self.add_subroot(&sum, u, a.label);
            if inverse.is_some() {
                self.dp[u] = sum;
            }
        }
        if let Some(inverse) = inverse {
            for u in order {
                let sum = if u == 0 {
                    self.graph.neighbors(u).fold(M::unit(), |sum, a| {
                        self.merge(&sum, &self.ep[self.eidx(u, a)])
                    })
                } else {
                    let a = self
                        .graph
                        .neighbors(u)
                        .find(|a| a.to == parents[u])
                        .unwrap();
                    self.merge(&self.dp[u], &self.ep[self.eidx(u, a)])
                };
                self.dp[u] = self.add_root(&sum, u);
                for a in self.graph.neighbors(u) {
                    if a.to != parents[u] {
                        let value = inverse(&sum, &self.ep[self.eidx(u, a)]);
                        let i = self.reidx(u, a);
                        self.ep[i] = self.add_subroot(&value, u, a.label);
                    }
                }
            }
            return;
        }
        let mut prefix = Vec::new();
        for u in order {
            prefix.clear();
            prefix.push(M::unit());
            for a in self.graph.neighbors(u) {
                prefix.push(self.merge(prefix.last().unwrap(), &self.ep[self.eidx(u, a)]));
            }
            self.dp[u] = self.add_root(prefix.last().unwrap(), u);
            let mut suffix = M::unit();
            for (k, a) in self.graph.neighbors(u).enumerate().rev() {
                if a.to != parents[u] {
                    let i = self.reidx(u, a);
                    self.ep[i] = self.add_subroot(&self.merge(&prefix[k], &suffix), u, a.label);
                }
                suffix = self.merge(&self.ep[self.eidx(u, a)], &suffix);
            }
        }
    }

crates/competitive/src/tree/centroid_decomposition.rs (line 272)

    pub fn contour_query_range(&self) -> ContourQueryRange {
        let n = self.vertices_size();
        assert!(n <= u32::MAX as usize / 2);
        if n <= 1 {
            return ContourQueryRange {
                comp_range: vec![0],
                info_indptr: vec![0; n + 1],
                infos: vec![],
                local_info: vec![(usize::MAX, 0); n],
                local_offsets: vec![],
                local_masks: vec![],
            };
        }
        let (vertices, graph) = {
            let (vertices, parents) = self.tree_order(0);
            let mut indices = vec![0; n];
            for (i, &v) in vertices.iter().enumerate() {
                indices[v] = i;
            }
            let edges = vertices
                .iter()
                .enumerate()
                .skip(1)
                .map(|(i, &v)| (i, indices[parents[v]]))
                .collect();
            let graph = UndirectedSparseGraph::from_edges(n, edges);
            (vertices, graph)
        };
        let mut comp_range = vec![0usize];
        let mut vertex_info = Vec::with_capacity(n * (n.ilog2() as usize + 1));
        let mut info_indptr = vec![0usize; n + 1];
        let mut local_info = vec![(usize::MAX, 0); n];
        let mut local_offsets = Vec::new();
        let mut local_masks = Vec::new();
        let mut distances = Vec::new();
        let mut local_sizes = Vec::new();
        let mut removed = vec![false; n];
        let mut parents = vec![usize::MAX; n];
        let mut sizes = vec![0usize; n];
        let mut tasks = vec![0];
        let mut order = Vec::with_capacity(n);
        let mut entries = Vec::with_capacity(n);
        let mut boundaries = Vec::new();
        let mut groups = Vec::new();
        while let Some(root) = tasks.pop() {
            order.clear();
            order.push(root);
            parents[root] = usize::MAX;
            let mut i = 0;
            while i < order.len() {
                let v = order[i];
                sizes[v] = 1;
                for edge in graph.neighbors(v) {
                    if !removed[edge.to] && edge.to != parents[v] {
                        parents[edge.to] = v;
                        order.push(edge.to);
                    }
                }
                i += 1;
            }
            if order.len() <= 32 {
                let len = order.len();
                if len > 1 {
                    let comp = local_offsets.len();
                    let offset = local_masks.len();
                    local_offsets.push(offset);
                    local_sizes.push(len);
                    local_masks.resize(offset + len * (len + 1), 0u32);
                    distances.clear();
                    distances.resize(len * len, 0u8);
                    for (i, &v) in order.iter().enumerate() {
                        local_info[vertices[v]] = (comp, i);
                        sizes[v] = i;
                        local_masks[offset + i * (len + 1) + 1] = 1 << i;
                    }
                    for (i, &v) in order.iter().enumerate().skip(1) {
                        let parent = sizes[parents[v]];
                        for j in 0..i {
                            let distance = distances[parent * len + j] + 1;
                            distances[i * len + j] = distance;
                            distances[j * len + i] = distance;
                            local_masks[offset + i * (len + 1) + distance as usize + 1] |= 1 << j;
                            local_masks[offset + j * (len + 1) + distance as usize + 1] |= 1 << i;
                        }
                    }
                    for row in local_masks[offset..].chunks_exact_mut(len + 1) {
                        for d in 1..=len {
                            row[d] |= row[d - 1];
                        }
                    }
                }
                continue;
            }
            let mut centroid = root;
            for &v in order.iter().rev() {
                if sizes[v] >= order.len().div_ceil(2) {
                    centroid = v;
                    break;
                }
                sizes[parents[v]] += sizes[v];
            }
            removed[centroid] = true;
            entries.clear();
            entries.push((centroid, 0));
            boundaries.clear();
            boundaries.extend([0, 1]);
            for edge in graph.neighbors(centroid) {
                let v = edge.to;
                if removed[v] {
                    continue;
                }
                tasks.push(v);
                parents[v] = centroid;
                let mut i = entries.len();
                entries.push((v, 1));
                while i < entries.len() {
                    let (v, distance) = entries[i];
                    for edge in graph.neighbors(v) {
                        if !removed[edge.to] && edge.to != parents[v] {
                            parents[edge.to] = v;
                            entries.push((edge.to, distance + 1));
                        }
                    }
                    i += 1;
                }
                boundaries.push(entries.len());
            }
            groups.push((0, boundaries.len() - 1));
            while let Some((first, last)) = groups.pop() {
                if last - first < 2 {
                    continue;
                }
                let weight = boundaries[last] - boundaries[first];
                let target = boundaries[first] + weight.div_ceil(2);
                let mut middle =
                    first + 1 + boundaries[first + 1..last].partition_point(|&p| p < target);
                middle = middle.min(last - 1);
                if middle > first + 1 {
                    let x = boundaries[middle] - boundaries[first];
                    let y = boundaries[middle - 1] - boundaries[first];
                    if y.max(weight - y) < x.max(weight - x) {
                        middle -= 1;
                    }
                }
                for (l, r) in [(first, middle), (middle, last)] {
                    let comp = comp_range.len() - 1;
                    let mut max_distance = 0;
                    for &(v, dep) in &entries[boundaries[l]..boundaries[r]] {
                        vertex_info.push((
                            vertices[v] as u32,
                            ContourInfo {
                                comp: comp as u32,
                                dep: dep as u32,
                            },
                        ));
                        info_indptr[vertices[v] + 1] += 1;
                        max_distance = max_distance.max(dep);
                    }
                    comp_range.push(comp_range[comp] + max_distance + 1);
                }
                groups.extend([(middle, last), (first, middle)]);
            }
        }
        for len in local_sizes {
            comp_range.push(comp_range.last().unwrap() + len);
        }
        for v in 1..=n {
            info_indptr[v] += info_indptr[v - 1];
        }
        let mut infos = vec![ContourInfo { comp: 0, dep: 0 }; vertex_info.len()];
        let mut positions = info_indptr.clone();
        for (v, info) in vertex_info {
            let v = v as usize;
            infos[positions[v]] = info;
            positions[v] += 1;
        }
        ContourQueryRange {
            comp_range,
            info_indptr,
            infos,
            local_info,
            local_offsets,
            local_masks,
        }
    }

Trait Implementations

impl<D: Clone> Clone for SparseGraph<D>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<D: Debug> Debug for SparseGraph<D>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DirectedGraph for SparseGraph<DirectedEdge>

impl<T> EdgeMap<T> for SparseGraph<DirectedEdge>

type Emap = Vec<T>

fn construct_emap<F>(&self, f: F) -> Self::Emap

where F: FnMut() -> T,

fn emap_get<'a>(&self, map: &'a Self::Emap, eid: Self::Label) -> &'a T

fn emap_get_mut<'a>( &self, map: &'a mut Self::Emap, eid: Self::Label, ) -> &'a mut T

fn emap_set(&self, map: &mut Self::Emap, eid: Self::Label, value: T)

impl<T> EdgeMap<T> for SparseGraph<UndirectedEdge>

type Emap = Vec<T>

fn construct_emap<F>(&self, f: F) -> Self::Emap

where F: FnMut() -> T,

fn emap_get<'a>(&self, map: &'a Self::Emap, eid: Self::Label) -> &'a T

fn emap_get_mut<'a>( &self, map: &'a mut Self::Emap, eid: Self::Label, ) -> &'a mut T

fn emap_set(&self, map: &mut Self::Emap, eid: Self::Label, value: T)

impl From<&SparseGraph<UndirectedEdge>> for RootedTree

fn from(graph: &UndirectedSparseGraph) -> Self

Converts to this type from the input type.

impl<D> Graph for SparseGraph<D>

where D: SparseGraphConstruction,

type Vertex = usize

type Label = usize

type Vertices<'g> = Range<usize> where D: 'g

type Neighbors<'g> = Copied<Iter<'g, Neighbor<usize, usize>>> where D: 'g

fn vsize(&self) -> usize

fn vertices(&self) -> Self::Vertices<'_>

fn neighbors(&self, vertex: Self::Vertex) -> Self::Neighbors<'_>

impl<T: RandomSpec<usize>> RandomSpec<SparseGraph<UndirectedEdge>> for PruferSequence<T>

fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph

Return a random value.

fn rand_iter(self, rng: &mut Xorshift) -> RandIter<'_, T, Self>

Return an iterator that generates random values.

impl<T: RandomSpec<usize>> RandomSpec<SparseGraph<UndirectedEdge>> for PathTree<T>

fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph

Return a random value.

fn rand_iter(self, rng: &mut Xorshift) -> RandIter<'_, T, Self>

Return an iterator that generates random values.

impl<T: RandomSpec<usize>> RandomSpec<SparseGraph<UndirectedEdge>> for StarTree<T>

fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph

Return a random value.

fn rand_iter(self, rng: &mut Xorshift) -> RandIter<'_, T, Self>

Return an iterator that generates random values.

impl<T: RandomSpec<usize>> RandomSpec<SparseGraph<UndirectedEdge>> for MixedTree<T>

fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph

Return a random value.

fn rand_iter(self, rng: &mut Xorshift) -> RandIter<'_, T, Self>

Return an iterator that generates random values.

impl<D, T> VertexMap<T> for SparseGraph<D>

where D: SparseGraphConstruction,

type Vmap = Vec<T>

fn construct_vmap<F>(&self, f: F) -> Self::Vmap

where F: FnMut() -> T,

fn vmap_get<'a>(&self, map: &'a Self::Vmap, vid: Self::Vertex) -> &'a T

fn vmap_get_mut<'a>( &self, map: &'a mut Self::Vmap, vid: Self::Vertex, ) -> &'a mut T

fn vmap_set(&self, map: &mut Self::Vmap, vertex: Self::Vertex, value: T)