Struct SparseGraph

Source

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

Expand description

Static Sparse Graph represented as Compressed Sparse Row.

Fields§

§start: Vec<usize>§elist: Vec<Adjacency>§edges: Vec<(usize, usize)>

Implementations§

Source §

impl SparseGraph<DirectedEdge>

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

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

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 §

pub fn for_each_connected_components<F>(&self, f: F)
where F: FnMut(&Self, usize, &[(usize, usize)]),

f: |g, root, ord: [vertex, parent]| {}

Source §

impl<D> SparseGraph<D>

Source

pub fn vertices_size(&self) -> usize

Return the number of vertices.

Examples found in repository ?

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

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

More examples

Hide additional examples

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

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    }
17}
18
19#[codesnip::entry("weighted_tree_depth", include("algebra", "SparseGraph"))]
20impl UndirectedSparseGraph {
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    }
47}
48
49#[codesnip::entry("tree_size", include("SparseGraph"))]
50impl UndirectedSparseGraph {
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    }

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

15    pub fn new(root: usize, graph: &'a UndirectedSparseGraph) -> Self {
16        let mut self_ = Self {
17            graph,
18            eidx: vec![(0, 0); graph.vertices_size() - 1],
19            par: vec![usize::MAX; graph.vertices_size()],
20            epos: 0,
21        };
22        self_.edge_tour(root, usize::MAX);
23        self_
24    }
25    pub fn length(&self) -> usize {
26        self.epos
27    }
28    fn edge_tour(&mut self, u: usize, p: usize) {
29        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
30            self.par[a.to] = a.id;
31            self.eidx[a.id].0 = self.epos;
32            self.epos += 1;
33            self.edge_tour(a.to, u);
34            self.eidx[a.id].1 = self.epos;
35            self.epos += 1;
36        }
37    }
38}
39
40#[codesnip::entry("EulerTourForVertex", include("SparseGraph"))]
41#[derive(Clone, Debug)]
42pub struct EulerTourForVertex<'a> {
43    graph: &'a UndirectedSparseGraph,
44    pub vidx: Vec<(usize, usize)>,
45    vpos: usize,
46}
47#[codesnip::entry("EulerTourForVertex")]
48impl<'a> EulerTourForVertex<'a> {
49    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
50        Self {
51            graph,
52            vidx: vec![(0, 0); graph.vertices_size()],
53            vpos: 0,
54        }
55    }
56    pub fn length(&self) -> usize {
57        self.vpos
58    }
59    pub fn subtree_vertex_tour(&mut self, u: usize, p: usize) {
60        self.vidx[u].0 = self.vpos;
61        self.vpos += 1;
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            self.subtree_vertex_tour(a.to, u);
64        }
65        self.vidx[u].1 = self.vpos;
66    }
67    pub fn path_vertex_tour(&mut self, u: usize, p: usize) {
68        self.vidx[u].0 = self.vpos;
69        self.vpos += 1;
70        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
71            self.path_vertex_tour(a.to, u);
72        }
73        self.vidx[u].1 = self.vpos;
74        self.vpos += 1;
75    }
76    pub fn subtree_query<T, F: FnMut(usize, usize) -> T>(&self, u: usize, mut f: F) -> T {
77        let (l, r) = self.vidx[u];
78        f(l, r)
79    }
80    pub fn subtree_update<T, F: FnMut(usize, T)>(&self, u: usize, x: T, mut f: F) {
81        let (l, _r) = self.vidx[u];
82        f(l, x);
83    }
84    pub fn path_query<T, F: FnMut(usize, usize) -> T>(&self, u: usize, v: usize, mut f: F) -> T {
85        let (mut l, mut r) = (self.vidx[u].0, self.vidx[v].0);
86        if l > r {
87            std::mem::swap(&mut l, &mut r);
88        }
89        f(l, r + 1)
90    }
91    pub fn path_update<T, F: FnMut(usize, T)>(&self, u: usize, x: T, invx: T, mut f: F) {
92        let (l, r) = self.vidx[u];
93        f(l, x);
94        f(r, invx);
95    }
96}
97
98#[codesnip::entry("EulerTourForRichVertex", include("SparseGraph"))]
99#[derive(Clone, Debug)]
100pub struct EulerTourForRichVertex<'a> {
101    graph: &'a UndirectedSparseGraph,
102    pub root: usize,
103    pub vidx: Vec<(usize, usize)>,
104    vtrace: Vec<usize>,
105}
106#[codesnip::entry("EulerTourForRichVertex")]
107impl<'a> EulerTourForRichVertex<'a> {
108    pub fn new(root: usize, graph: &'a UndirectedSparseGraph) -> Self {
109        let mut self_ = Self {
110            graph,
111            root,
112            vidx: vec![(0, 0); graph.vertices_size()],
113            vtrace: vec![],
114        };
115        self_.vertex_tour(root, usize::MAX);
116        self_
117    }

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

27    pub fn new(graph: &'a UndirectedSparseGraph, rooting: F) -> Self {
28        let dp = vec![M::unit(); graph.vertices_size()];
29        let ep = vec![M::unit(); graph.vertices_size() * 2];
30        let mut self_ = Self {
31            graph,
32            dp,
33            ep,
34            rooting,
35        };
36        self_.rerooting();
37        self_
38    }

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

11    pub fn new(root: usize, graph: &mut UndirectedSparseGraph) -> Self {
12        let mut self_ = Self {
13            par: vec![0; graph.vertices_size()],
14            size: vec![0; graph.vertices_size()],
15            head: vec![0; graph.vertices_size()],
16            vidx: vec![0; graph.vertices_size()],
17        };
18        self_.build(root, graph);
19        self_
20    }
21
22    fn dfs_size(&mut self, u: usize, p: usize, graph: &mut UndirectedSparseGraph) {
23        self.par[u] = p;
24        self.size[u] = 1;
25        let base = graph.start[u];
26        if graph.adjacencies(u).len() > 1 && graph.adjacencies(u).next().unwrap().to == p {
27            graph.elist.swap(base, base + 1);
28        }
29        for i in base..graph.start[u + 1] {
30            let a = graph.elist[i];
31            if a.to != p {
32                self.dfs_size(a.to, u, graph);
33                self.size[u] += self.size[a.to];
34                if self.size[graph.elist[base].to] < self.size[a.to] {
35                    graph.elist.swap(base, i);
36                }
37            }
38        }
39    }
40
41    fn dfs_hld(&mut self, u: usize, p: usize, t: &mut usize, graph: &UndirectedSparseGraph) {
42        self.vidx[u] = *t;
43        *t += 1;
44        let mut adjacencies = graph.adjacencies(u).filter(|a| a.to != p);
45        if let Some(a) = adjacencies.next() {
46            self.head[a.to] = self.head[u];
47            self.dfs_hld(a.to, u, t, graph);
48        }
49        for a in adjacencies {
50            self.head[a.to] = a.to;
51            self.dfs_hld(a.to, u, t, graph);
52        }
53    }
54
55    fn build(&mut self, root: usize, graph: &mut UndirectedSparseGraph) {
56        self.head[root] = root;
57        self.dfs_size(root, graph.vertices_size(), graph);
58        let mut t = 0;
59        self.dfs_hld(root, graph.vertices_size(), &mut t, graph);
60    }

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

11    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
12        let mut self_ = Self {
13            graph,
14            low: vec![0; graph.vertices_size()],
15            ord: vec![usize::MAX; graph.vertices_size()],
16            articulation: vec![],
17            bridge: vec![],
18        };
19        for u in graph.vertices() {
20            if self_.ord[u] == usize::MAX {
21                self_.dfs(u, graph.vertices_size(), &mut 0);
22            }
23        }
24        self_
25    }
26    fn dfs(&mut self, u: usize, p: usize, now_ord: &mut usize) {
27        self.low[u] = *now_ord;
28        self.ord[u] = *now_ord;
29        *now_ord += 1;
30        let mut is_articulation = false;
31        let mut cnt = 0;
32        for a in self.graph.adjacencies(u) {
33            if self.ord[a.to] == usize::MAX {
34                cnt += 1;
35                self.dfs(a.to, u, now_ord);
36                self.low[u] = self.low[u].min(self.low[a.to]);
37                is_articulation |= p < self.graph.vertices_size() && self.ord[u] <= self.low[a.to];
38                if self.ord[u] < self.low[a.to] {
39                    self.bridge.push((u.min(a.to), u.max(a.to)));
40                }
41            } else if a.to != p {
42                self.low[u] = self.low[u].min(self.ord[a.to]);
43            }
44        }
45        is_articulation |= p == self.graph.vertices_size() && cnt > 1;
46        if is_articulation {
47            self.articulation.push(u);
48        }
49    }

Additional examples can be found in:

Source

pub fn edges_size(&self) -> usize

Return the number of edges.

Examples found in repository ?

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

40    fn eidx(&self, u: usize, a: &Adjacency) -> usize {
41        a.id + self.graph.edges_size() * (u > a.to) as usize
42    }
43    #[inline]
44    fn reidx(&self, u: usize, a: &Adjacency) -> usize {
45        a.id + self.graph.edges_size() * (u < a.to) as usize
46    }

More examples

Hide additional examples

crates/competitive/src/graph/order.rs (line 48)

46    pub fn dfs_tree(&self, root: usize) -> Vec<bool> {
47        let mut visited = vec![false; self.vertices_size()];
48        let mut used = vec![false; self.edges_size()];
49        visited[root] = true;
50        let mut stack = vec![root];
51        while let Some(u) = stack.pop() {
52            for a in self.adjacencies(u).rev() {
53                if !visited[a.to] {
54                    visited[a.to] = true;
55                    used[a.id] = true;
56                    stack.push(a.to);
57                }
58            }
59        }
60        used
61    }

Source

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

Return an iterator over graph vertices.

Examples found in repository ?

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

11    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
12        let mut self_ = Self {
13            graph,
14            low: vec![0; graph.vertices_size()],
15            ord: vec![usize::MAX; graph.vertices_size()],
16            articulation: vec![],
17            bridge: vec![],
18        };
19        for u in graph.vertices() {
20            if self_.ord[u] == usize::MAX {
21                self_.dfs(u, graph.vertices_size(), &mut 0);
22            }
23        }
24        self_
25    }

More examples

Hide additional examples

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

10pub fn grl_1_a(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
14    let cost = graph.dijkstra_ss::<StandardSp<AdditiveOperation<_>>, _>(r, &d);
15    for u in graph.vertices() {
16        if cost[u].is_maximum() {
17            writeln!(writer, "INF").ok();
18        } else {
19            writeln!(writer, "{}", cost[u]).ok();
20        }
21    }
22}
23
24#[verify::aizu_online_judge("GRL_1_A")]
25pub fn grl_1_a_option(reader: impl Read, mut writer: impl Write) {
26    let s = read_all_unchecked(reader);
27    let mut scanner = Scanner::new(&s);
28    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
29    let cost = graph.dijkstra_ss::<OptionSp<AdditiveOperation<_>>, _>(r, &|eid| Some(d[eid]));
30    for u in graph.vertices() {
31        match cost[u] {
32            Some(d) => writeln!(writer, "{}", d).ok(),
33            None => writeln!(writer, "INF").ok(),
34        };
35    }
36}

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

5    pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
6    where
7        N: Fn(usize) -> NA,
8        E: Fn(usize) -> EA,
9        NA: Display,
10        EA: Display,
11    {
12        let mut s = String::new();
13        s.push_str("digraph G {\n    graph [ splines=false, layout=neato ];\n");
14        for u in self.vertices() {
15            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
16        }
17        for u in self.vertices() {
18            for a in self.adjacencies(u) {
19                writeln!(s, "    {} -> {} [{}];", u, a.to, edge_attr(a.id)).ok();
20            }
21        }
22        s.push('}');
23        s
24    }
25}
26
27impl UndirectedSparseGraph {
28    pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
29    where
30        N: Fn(usize) -> NA,
31        E: Fn(usize) -> EA,
32        NA: Display,
33        EA: Display,
34    {
35        let mut s = String::new();
36        s.push_str("graph G {\n    graph [ splines=false, layout=neato ];\n");
37        for u in self.vertices() {
38            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
39        }
40        for (i, (u, v)) in self.edges.iter().cloned().enumerate() {
41            writeln!(s, "    {} -- {} [{}];", u, v, edge_attr(i)).ok();
42        }
43        s.push('}');
44        s
45    }
46}
47
48impl BidirectionalSparseGraph {
49    pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
50    where
51        N: Fn(usize) -> NA,
52        E: Fn(usize) -> EA,
53        NA: Display,
54        EA: Display,
55    {
56        let mut s = String::new();
57        s.push_str("digraph G {\n    graph [ splines=false, layout=neato ];\n");
58        for u in self.vertices() {
59            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
60        }
61        for u in self.vertices() {
62            for a in self.adjacencies(u) {
63                writeln!(s, "    {} -> {} [{}];", u, a.to, edge_attr(a.id)).ok();
64            }
65        }
66        s.push('}');
67        s
68    }

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

19    pub fn new(graph: &'a DirectedSparseGraph) -> Self {
20        let mut now_ord = 0;
21        let mut self_ = Self {
22            graph,
23            csize: 0,
24            visited: Vec::with_capacity(graph.vertices_size()),
25            low: vec![0; graph.vertices_size()],
26            ord: vec![usize::MAX; graph.vertices_size()],
27            comp: vec![0; graph.vertices_size()],
28        };
29        for u in graph.vertices() {
30            if self_.ord[u] == usize::MAX {
31                self_.dfs(u, &mut now_ord);
32            }
33        }
34        for x in self_.comp.iter_mut() {
35            *x = self_.csize - 1 - *x;
36        }
37        self_
38    }
39}
40impl StronglyConnectedComponent<'_> {
41    fn dfs(&mut self, u: usize, now_ord: &mut usize) {
42        self.low[u] = *now_ord;
43        self.ord[u] = *now_ord;
44        *now_ord += 1;
45        self.visited.push(u);
46        for a in self.graph.adjacencies(u) {
47            if self.ord[a.to] == usize::MAX {
48                self.dfs(a.to, now_ord);
49                self.low[u] = self.low[u].min(self.low[a.to]);
50            } else {
51                self.low[u] = self.low[u].min(self.ord[a.to]);
52            }
53        }
54        if self.low[u] == self.ord[u] {
55            while let Some(v) = self.visited.pop() {
56                self.ord[v] = self.graph.vertices_size();
57                self.comp[v] = self.csize;
58                if v == u {
59                    break;
60                }
61            }
62            self.csize += 1;
63        }
64    }
65    pub fn gen_cgraph(&self) -> DirectedSparseGraph {
66        let mut used = std::collections::HashSet::new();
67        let mut edges = vec![];
68        for u in self.graph.vertices() {
69            for a in self.graph.adjacencies(u) {
70                if self.comp[u] != self.comp[a.to] {
71                    let (x, y) = (self.comp[u], self.comp[a.to]);
72                    if !used.contains(&(x, y)) {
73                        used.insert((x, y));
74                        edges.push((x, y));
75                    }
76                }
77            }
78        }
79        DirectedSparseGraph::from_edges(self.size(), edges)
80    }
81    pub fn components(&self) -> Vec<Vec<usize>> {
82        let mut counts = vec![0; self.size()];
83        for &x in self.comp.iter() {
84            counts[x] += 1;
85        }
86        let mut groups = vec![vec![]; self.size()];
87        for (g, c) in groups.iter_mut().zip(counts.into_iter()) {
88            g.reserve(c);
89        }
90        for u in self.graph.vertices() {
91            groups[self[u]].push(u);
92        }
93        groups
94    }

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

9pub fn grl_1_b(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
13    let cost =
14        graph.bellman_ford_ss::<OptionSp<AdditiveOperation<_>>, _>(r, &|eid| Some(d[eid]), true);
15    if let Some(cost) = cost {
16        for u in graph.vertices() {
17            match cost[u] {
18                Some(d) => writeln!(writer, "{}", d).ok(),
19                None => writeln!(writer, "INF").ok(),
20            };
21        }
22    } else {
23        writeln!(writer, "NEGATIVE CYCLE").ok();
24    }
25}

crates/competitive/src/graph/topological_sort.rs (line 7)

4    pub fn topological_sort(&self) -> Vec<usize> {
5        let mut indeg = vec![0; self.vertices_size()];
6        let mut res = vec![];
7        for a in self.vertices().flat_map(|u| self.adjacencies(u)) {
8            indeg[a.to] += 1;
9        }
10        let mut stack = self
11            .vertices()
12            .filter(|&u| indeg[u] == 0)
13            .collect::<Vec<_>>();
14        while let Some(u) = stack.pop() {
15            res.push(u);
16            for a in self.adjacencies(u) {
17                indeg[a.to] -= 1;
18                if indeg[a.to] == 0 {
19                    stack.push(a.to);
20                }
21            }
22        }
23        res
24    }

Additional examples can be found in:

Source

pub fn adjacencies(&self, v: usize) -> Iter<'_, Adjacency>

Return a slice of adjacency vertices.

Examples found in repository ?

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

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    }
17}
18
19#[codesnip::entry("weighted_tree_depth", include("algebra", "SparseGraph"))]
20impl UndirectedSparseGraph {
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    }
47}
48
49#[codesnip::entry("tree_size", include("SparseGraph"))]
50impl UndirectedSparseGraph {
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    }

More examples

Hide additional examples

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

28    fn edge_tour(&mut self, u: usize, p: usize) {
29        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
30            self.par[a.to] = a.id;
31            self.eidx[a.id].0 = self.epos;
32            self.epos += 1;
33            self.edge_tour(a.to, u);
34            self.eidx[a.id].1 = self.epos;
35            self.epos += 1;
36        }
37    }
38}
39
40#[codesnip::entry("EulerTourForVertex", include("SparseGraph"))]
41#[derive(Clone, Debug)]
42pub struct EulerTourForVertex<'a> {
43    graph: &'a UndirectedSparseGraph,
44    pub vidx: Vec<(usize, usize)>,
45    vpos: usize,
46}
47#[codesnip::entry("EulerTourForVertex")]
48impl<'a> EulerTourForVertex<'a> {
49    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
50        Self {
51            graph,
52            vidx: vec![(0, 0); graph.vertices_size()],
53            vpos: 0,
54        }
55    }
56    pub fn length(&self) -> usize {
57        self.vpos
58    }
59    pub fn subtree_vertex_tour(&mut self, u: usize, p: usize) {
60        self.vidx[u].0 = self.vpos;
61        self.vpos += 1;
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            self.subtree_vertex_tour(a.to, u);
64        }
65        self.vidx[u].1 = self.vpos;
66    }
67    pub fn path_vertex_tour(&mut self, u: usize, p: usize) {
68        self.vidx[u].0 = self.vpos;
69        self.vpos += 1;
70        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
71            self.path_vertex_tour(a.to, u);
72        }
73        self.vidx[u].1 = self.vpos;
74        self.vpos += 1;
75    }
76    pub fn subtree_query<T, F: FnMut(usize, usize) -> T>(&self, u: usize, mut f: F) -> T {
77        let (l, r) = self.vidx[u];
78        f(l, r)
79    }
80    pub fn subtree_update<T, F: FnMut(usize, T)>(&self, u: usize, x: T, mut f: F) {
81        let (l, _r) = self.vidx[u];
82        f(l, x);
83    }
84    pub fn path_query<T, F: FnMut(usize, usize) -> T>(&self, u: usize, v: usize, mut f: F) -> T {
85        let (mut l, mut r) = (self.vidx[u].0, self.vidx[v].0);
86        if l > r {
87            std::mem::swap(&mut l, &mut r);
88        }
89        f(l, r + 1)
90    }
91    pub fn path_update<T, F: FnMut(usize, T)>(&self, u: usize, x: T, invx: T, mut f: F) {
92        let (l, r) = self.vidx[u];
93        f(l, x);
94        f(r, invx);
95    }
96}
97
98#[codesnip::entry("EulerTourForRichVertex", include("SparseGraph"))]
99#[derive(Clone, Debug)]
100pub struct EulerTourForRichVertex<'a> {
101    graph: &'a UndirectedSparseGraph,
102    pub root: usize,
103    pub vidx: Vec<(usize, usize)>,
104    vtrace: Vec<usize>,
105}
106#[codesnip::entry("EulerTourForRichVertex")]
107impl<'a> EulerTourForRichVertex<'a> {
108    pub fn new(root: usize, graph: &'a UndirectedSparseGraph) -> Self {
109        let mut self_ = Self {
110            graph,
111            root,
112            vidx: vec![(0, 0); graph.vertices_size()],
113            vtrace: vec![],
114        };
115        self_.vertex_tour(root, usize::MAX);
116        self_
117    }
118    pub fn length(&self) -> usize {
119        self.vtrace.len()
120    }
121    fn vertex_tour(&mut self, u: usize, p: usize) {
122        self.vidx[u].0 = self.vtrace.len();
123        self.vtrace.push(u);
124        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
125            self.vertex_tour(a.to, u);
126            self.vtrace.push(u);
127        }
128        self.vidx[u].1 = self.vtrace.len() - 1;
129    }

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

59    fn dfs(&mut self, pa: &Adjacency, p: usize) {
60        let u = pa.to;
61        let pi = self.eidx(p, pa);
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            let i = self.eidx(u, a);
64            self.dfs(a, u);
65            self.ep[pi] = self.merge(&self.ep[pi], &self.ep[i]);
66        }
67        self.ep[pi] = self.add_subroot(&self.ep[pi], u, pa.id);
68    }
69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }
91    fn rerooting(&mut self) {
92        for a in self.graph.adjacencies(0) {
93            self.dfs(a, 0);
94        }
95        self.efs(0, usize::MAX);
96    }

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

9        fn dfs<T, F>(g: &UndirectedSparseGraph, u: usize, p: usize, dp: &mut [T], f: &mut F)
10        where
11            F: FnMut(&mut T, &T),
12        {
13            for a in g.adjacencies(u) {
14                if a.to != p {
15                    dfs(g, a.to, u, dp, f);
16                    assert_ne!(u, a.to);
17                    let ptr = dp.as_mut_ptr();
18                    unsafe { f(&mut *ptr.add(u), &*ptr.add(a.to)) };
19                }
20            }
21        }
22        dfs(self, root, !0, dp, &mut f);
23    }
24    pub fn tree_dp_top_down<T, F>(&self, root: usize, dp: &mut [T], mut f: F)
25    where
26        F: FnMut(&mut T, &T),
27    {
28        fn dfs<T, F>(g: &UndirectedSparseGraph, u: usize, p: usize, dp: &mut [T], f: &mut F)
29        where
30            F: FnMut(&mut T, &T),
31        {
32            for a in g.adjacencies(u) {
33                if a.to != p {
34                    assert_ne!(u, a.to);
35                    let ptr = dp.as_mut_ptr();
36                    unsafe { f(&mut *ptr.add(a.to), &*ptr.add(u)) };
37                    dfs(g, a.to, u, dp, f);
38                }
39            }
40        }

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

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    }

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

6    pub fn tree_order(&self, root: usize) -> (Vec<usize>, Vec<usize>) {
7        let n = self.vertices_size();
8        let mut order = Vec::with_capacity(n);
9        let mut parents = vec![!0usize; n];
10        let mut stack = Vec::with_capacity(n);
11        stack.push(root);
12        while let Some(u) = stack.pop() {
13            order.push(u);
14            for a in self.adjacencies(u).rev() {
15                if a.to != parents[u] {
16                    parents[a.to] = u;
17                    stack.push(a.to);
18                }
19            }
20        }
21        (order, parents)
22    }

Additional examples can be found in:

Source

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

Source

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

Source §

impl<D> SparseGraph<D>
where D: SparseGraphConstruction,

Source

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

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

More examples

Hide additional examples

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

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

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

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

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

7    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
8        let n = rng.random(&self.0);
9        let edges = from_prufer_sequence(
10            n,
11            &rng.random_iter(0..n)
12                .take(n.saturating_sub(2))
13                .collect::<Vec<usize>>(),
14        );
15        UndirectedSparseGraph::from_edges(n, edges)
16    }
17}
18
19pub struct PathTree<T>(pub T);
20
21impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for PathTree<T> {
22    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
23        let n = rng.random(&self.0);
24        let edges = (1..n).map(|u| (u - 1, u)).collect();
25        UndirectedSparseGraph::from_edges(n, edges)
26    }
27}
28
29pub struct StarTree<T>(pub T);
30
31impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for StarTree<T> {
32    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
33        let n = rng.random(&self.0);
34        let edges = (1..n).map(|u| (0, u)).collect();
35        UndirectedSparseGraph::from_edges(n, edges)
36    }
37}
38
39pub struct MixedTree<T>(pub T);
40
41impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for MixedTree<T> {
42    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
43        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44            let mut edges = Vec::with_capacity(n.saturating_sub(1));
45            if n >= 2 {
46                let k = rng.random(1..n);
47                for n in [k, n - k].iter().cloned() {
48                    let ty = rng.rand(6);
49                    edges.extend(match ty {
50                        0 => from_prufer_sequence(
51                            n,
52                            &rng.random_iter(0..n)
53                                .take(n.saturating_sub(2))
54                                .collect::<Vec<usize>>(),
55                        ),
56                        1 => (1..n).map(|u| (u - 1, u)).collect(),
57                        2 => (1..n).map(|u| (0, u)).collect(),
58                        _ => rand_inner(n, rng),
59                    });
60                }
61                for (u, v) in edges[k - 1..].iter_mut() {
62                    *u += k;
63                    *v += k;
64                }
65                edges.push((rng.random(0..k), rng.random(k..n)));
66            }
67            edges
68        }
69        let n = rng.random(&self.0);
70        let edges = rand_inner(n, rng);
71        UndirectedSparseGraph::from_edges(n, edges)
72    }

crates/competitive/src/graph/two_satisfiability.rs (line 34)

33    pub fn two_satisfiability(self) -> Option<Vec<bool>> {
34        let graph = DirectedSparseGraph::from_edges(self.vsize * 2, self.edges);
35        let scc = StronglyConnectedComponent::new(&graph);
36        let mut res = vec![false; self.vsize];
37        for i in 0..self.vsize {
38            if scc[i * 2] == scc[i * 2 + 1] {
39                return None;
40            }
41            res[i] = scc[i * 2] > scc[i * 2 + 1];
42        }
43        Some(res)
44    }

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

6pub fn scc(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, vs, es, edges: [(usize, usize); es]);
10    let graph = DirectedSparseGraph::from_edges(vs, edges);
11    let scc = StronglyConnectedComponent::new(&graph);
12    let comp = scc.components();
13    writeln!(writer, "{}", comp.len()).ok();
14    for vs in comp.into_iter() {
15        iter_print!(writer, vs.len(), @it vs);
16    }
17}

Additional examples can be found in:

Source §

impl<D> SparseGraph<D>

Source

pub fn topological_sort(&self) -> Vec<usize>

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_4_a.rs (line 10)

6pub fn grl_4_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, vs, es, (graph, _): @DirectedGraphScanner::<usize, ()>::new(vs, es));
10    writeln!(writer, "{}", (graph.topological_sort().len() != vs) as u32).ok();
11}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_4_b.rs (line 10)

6pub fn grl_4_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, vs, es, (graph, _): @DirectedGraphScanner::<usize, ()>::new(vs, es));
10    for u in graph.topological_sort().into_iter() {
11        writeln!(writer, "{}", u).ok();
12    }
13}

Source §

impl SparseGraph<UndirectedEdge>

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

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

Source

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

Source §

impl SparseGraph<UndirectedEdge>

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    }