Skip to main content

EdgeListGraph

competitive::graph::edge_list

Struct EdgeListGraph 

Source 
pub struct EdgeListGraph {
    vsize: usize,
    edges: Vec<(usize, usize)>,
}
Expand description

Graph represented by a list of edges.

Fields§

§vsize: usize§edges: Vec<(usize, usize)>

Implementations§

Source§

impl EdgeListGraph

Source

pub fn new(vsize: usize) -> Self

Construct empty graph.

Source

pub fn vertices_size(&self) -> usize

Return the number of vertices.

Examples found in repository?
crates/competitive/src/graph/edge_list.rs (line 28)
27    pub fn vertices(&self) -> Range<usize> {
28        0..self.vertices_size()
29    }
More examples
Hide additional examples
crates/competitive/src/graph/minimum_spanning_tree.rs (line 18)
14    pub fn minimum_spanning_tree_from_sorted_edges(
15        &self,
16        edges: impl IntoIterator<Item = usize>,
17    ) -> Vec<bool> {
18        let mut uf = UnionFind::new(self.vertices_size());
19        let mut res = vec![false; self.edges_size()];
20        let mut selected = 0;
21        for eid in edges {
22            let (u, v) = self[eid];
23            res[eid] = uf.unite(u, v);
24            if res[eid] {
25                selected += 1;
26                if selected + 1 == self.vertices_size() {
27                    break;
28                }
29            }
30        }
31        res
32    }
crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 32)
5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }
Source

pub fn edges_size(&self) -> usize

Return the number of edges.

Examples found in repository?
crates/competitive/src/graph/minimum_spanning_tree.rs (line 8)
4    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
5    where
6        T: Ord,
7    {
8        let mut edges: Vec<_> = (0..self.edges_size()).collect();
9        edges.sort_unstable_by_key(weight);
10        self.minimum_spanning_tree_from_sorted_edges(edges)
11    }
12
13    /// Runs Kruskal's algorithm on edge IDs sorted by nondecreasing weight.
14    pub fn minimum_spanning_tree_from_sorted_edges(
15        &self,
16        edges: impl IntoIterator<Item = usize>,
17    ) -> Vec<bool> {
18        let mut uf = UnionFind::new(self.vertices_size());
19        let mut res = vec![false; self.edges_size()];
20        let mut selected = 0;
21        for eid in edges {
22            let (u, v) = self[eid];
23            res[eid] = uf.unite(u, v);
24            if res[eid] {
25                selected += 1;
26                if selected + 1 == self.vertices_size() {
27                    break;
28                }
29            }
30        }
31        res
32    }
More examples
Hide additional examples
crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 41)
5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }
Source

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

Return an iterator over graph vertices.

Examples found in repository?
crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 46)
5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }
Source

pub fn edges(&self) -> Iter<'_, (usize, usize)> ⓘ

Examples found in repository?
crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 38)
5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }
Source

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

Construct graph from edges.

Examples found in repository?
crates/competitive/src/graph/edge_list.rs (line 70)
63    fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output> {
64        let mut edges = Vec::with_capacity(self.esize);
65        let mut rest = Vec::with_capacity(self.esize);
66        for _ in 0..self.esize {
67            edges.push((U::scan(iter)?, U::scan(iter)?));
68            rest.push(T::scan(iter)?);
69        }
70        let graph = EdgeListGraph::from_edges(self.vsize, edges);
71        Some((graph, rest))
72    }
Source§

impl EdgeListGraph

Source

pub fn minimum_spanning_arborescence<G, F>( &self, root: usize, weight: F, ) -> Option<(G::T, Vec<usize>)>
where G: Group<T: Ord>, F: Fn(usize) -> G::T,

tarjan

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_2_b.rs (line 8)
5pub fn grl_2_b(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, root, (graph, w): @EdgeListGraphScanner::<usize, i64>::new(vs, es));
8    let res = graph.minimum_spanning_arborescence::<AdditiveOperation<_>, _>(root, |u| w[u]);
9    pp!(res.unwrap().0);
10}
More examples
Hide additional examples
crates/library_checker/src/graph/directedmst.rs (line 9)
5pub fn directedmst(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, s, (graph, w): @EdgeListGraphScanner::<usize, i64>::new(n, m));
8    let res = graph
9        .minimum_spanning_arborescence::<AdditiveOperation<_>, _>(s, |u| w[u])
10        .unwrap();
11    pp!(res.0; @it res.1);
12}
Source§

impl EdgeListGraph

Source

pub fn minimum_spanning_tree<T>( &self, weight: impl Fn(&usize) -> T, ) -> Vec<bool>
where T: Ord,

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_2_a.rs (line 8)
5pub fn grl_2_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, (graph, w): @EdgeListGraphScanner::<usize, u32>::new(vs, es));
8    let span = graph.minimum_spanning_tree(|&eid| w[eid]);
9    let ans = (0..es)
10        .map(|eid| u64::from(w[eid]) * span[eid] as u64)
11        .sum::<u64>();
12    pp!(ans);
13}
Source

pub fn minimum_spanning_tree_from_sorted_edges( &self, edges: impl IntoIterator<Item = usize>, ) -> Vec<bool>

Runs Kruskal’s algorithm on edge IDs sorted by nondecreasing weight.

Examples found in repository?
crates/competitive/src/graph/minimum_spanning_tree.rs (line 10)
4    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
5    where
6        T: Ord,
7    {
8        let mut edges: Vec<_> = (0..self.edges_size()).collect();
9        edges.sort_unstable_by_key(weight);
10        self.minimum_spanning_tree_from_sorted_edges(edges)
11    }
More examples
Hide additional examples
crates/library_checker/src/graph/minimum_spanning_tree.rs (line 11)
5pub fn minimum_spanning_tree(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, (graph, w): @EdgeListGraphScanner::<usize, u32>::new(n, m));
8    let mut edges: Vec<_> = (0..m).map(|eid| (w[eid], eid as u32)).collect();
9    edges.radix_sort_by_key(|&(weight, _)| weight);
10    let span = graph
11        .minimum_spanning_tree_from_sorted_edges(edges.into_iter().map(|(_, eid)| eid as usize));
12    let ans = (0..m).filter(|&eid| span[eid]);
13    let total: u64 = ans.clone().map(|eid| u64::from(w[eid])).sum();
14    pp!(total; @it ans);
15}

Trait Implementations§

Source§

impl Clone for EdgeListGraph

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

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

Performs copy-assignment from source. Read more
Source§

impl Debug for EdgeListGraph

Source§

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

Formats the value using the given formatter. Read more
Source§

impl Index<usize> for EdgeListGraph

Source§

type Output = (usize, usize)

The returned type after indexing.
Source§

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.