competitive::graph

Struct EdgeListGraph

Source 
pub struct EdgeListGraph { /* private fields */ }
Expand description

Graph represented by a list of edges.

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 13)
7    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
8    where
9        T: Ord,
10    {
11        let mut idx: Vec<_> = (0..self.edges_size()).collect();
12        idx.sort_by_key(weight);
13        let mut uf = UnionFind::new(self.vertices_size());
14        let mut res = vec![false; self.edges_size()];
15        for eid in idx.into_iter() {
16            let (u, v) = self[eid];
17            res[eid] = uf.unite(u, v);
18        }
19        res
20    }
21}
22
23#[codesnip::entry(
24    "minimum_spanning_arborescence",
25    include("algebra", "EdgeListGraph", "UnionFind")
26)]
27impl EdgeListGraph {
28    /// tarjan
29    pub fn minimum_spanning_arborescence<G, F>(
30        &self,
31        root: usize,
32        weight: F,
33    ) -> Option<(G::T, Vec<usize>)>
34    where
35        G: Group,
36        G::T: Ord,
37        F: Fn(usize) -> G::T,
38    {
39        use std::{cmp::Reverse, collections::BinaryHeap};
40        let mut uf = MergingUnionFind::new_with_merger(
41            self.vertices_size(),
42            |_| (BinaryHeap::new(), G::unit()),
43            |x, y| {
44                let ny = G::rinv_operate(&y.1, &x.1);
45                x.0.extend(
46                    (y.0)
47                        .drain()
48                        .map(|(Reverse(ref w), i)| (Reverse(G::operate(w, &ny)), i)),
49                )
50            },
51        );
52        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
53        state[root] = 2;
54        for (id, &(_, to)) in self.edges().enumerate() {
55            uf.merge_data_mut(to).0.push((Reverse(weight(id)), id));
56        }
57        let mut paredge = vec![0; self.edges_size()];
58        let mut ord = vec![];
59        let mut leaf = vec![self.edges_size(); self.vertices_size()];
60        let mut cycle = 0usize;
61        let mut acc = G::unit();
62        for mut cur in self.vertices() {
63            if state[cur] != 0 {
64                continue;
65            }
66            let mut path = vec![];
67            let mut ch = vec![];
68            while state[cur] != 2 {
69                path.push(cur);
70                state[cur] = 1;
71                let (w, eid) = {
72                    let (heap, lazy) = &mut uf.merge_data_mut(cur);
73                    match heap.pop() {
74                        Some((Reverse(w), eid)) => (G::operate(&w, lazy), eid),
75                        None => return None,
76                    }
77                };
78                {
79                    let curw = &mut uf.merge_data_mut(cur).1;
80                    *curw = G::rinv_operate(curw, &w);
81                }
82                acc = G::operate(&acc, &w);
83                ord.push(eid);
84                let (u, v) = self[eid];
85                if leaf[v] >= self.edges_size() {
86                    leaf[v] = eid;
87                }
88                while cycle > 0 {
89                    paredge[ch.pop().unwrap()] = eid;
90                    cycle -= 1;
91                }
92                ch.push(eid);
93                if state[uf.find_root(u)] == 1 {
94                    while let Some(t) = path.pop() {
95                        state[t] = 2;
96                        cycle += 1;
97                        if !uf.unite(u, t) {
98                            break;
99                        }
100                    }
101                    state[uf.find_root(u)] = 1;
102                }
103                cur = uf.find_root(u);
104            }
105            for u in path.into_iter() {
106                state[u] = 2;
107            }
108        }
109        let mut tree = vec![root; self.vertices_size()];
110        let mut used = vec![false; self.edges_size()];
111        for eid in ord.into_iter().rev() {
112            if !used[eid] {
113                let (u, v) = self[eid];
114                tree[v] = u;
115                let mut x = leaf[v];
116                while x != eid {
117                    used[x] = true;
118                    x = paredge[x];
119                }
120            }
121        }
122        Some((acc, tree))
123    }
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 11)
7    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
8    where
9        T: Ord,
10    {
11        let mut idx: Vec<_> = (0..self.edges_size()).collect();
12        idx.sort_by_key(weight);
13        let mut uf = UnionFind::new(self.vertices_size());
14        let mut res = vec![false; self.edges_size()];
15        for eid in idx.into_iter() {
16            let (u, v) = self[eid];
17            res[eid] = uf.unite(u, v);
18        }
19        res
20    }
21}
22
23#[codesnip::entry(
24    "minimum_spanning_arborescence",
25    include("algebra", "EdgeListGraph", "UnionFind")
26)]
27impl EdgeListGraph {
28    /// tarjan
29    pub fn minimum_spanning_arborescence<G, F>(
30        &self,
31        root: usize,
32        weight: F,
33    ) -> Option<(G::T, Vec<usize>)>
34    where
35        G: Group,
36        G::T: Ord,
37        F: Fn(usize) -> G::T,
38    {
39        use std::{cmp::Reverse, collections::BinaryHeap};
40        let mut uf = MergingUnionFind::new_with_merger(
41            self.vertices_size(),
42            |_| (BinaryHeap::new(), G::unit()),
43            |x, y| {
44                let ny = G::rinv_operate(&y.1, &x.1);
45                x.0.extend(
46                    (y.0)
47                        .drain()
48                        .map(|(Reverse(ref w), i)| (Reverse(G::operate(w, &ny)), i)),
49                )
50            },
51        );
52        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
53        state[root] = 2;
54        for (id, &(_, to)) in self.edges().enumerate() {
55            uf.merge_data_mut(to).0.push((Reverse(weight(id)), id));
56        }
57        let mut paredge = vec![0; self.edges_size()];
58        let mut ord = vec![];
59        let mut leaf = vec![self.edges_size(); self.vertices_size()];
60        let mut cycle = 0usize;
61        let mut acc = G::unit();
62        for mut cur in self.vertices() {
63            if state[cur] != 0 {
64                continue;
65            }
66            let mut path = vec![];
67            let mut ch = vec![];
68            while state[cur] != 2 {
69                path.push(cur);
70                state[cur] = 1;
71                let (w, eid) = {
72                    let (heap, lazy) = &mut uf.merge_data_mut(cur);
73                    match heap.pop() {
74                        Some((Reverse(w), eid)) => (G::operate(&w, lazy), eid),
75                        None => return None,
76                    }
77                };
78                {
79                    let curw = &mut uf.merge_data_mut(cur).1;
80                    *curw = G::rinv_operate(curw, &w);
81                }
82                acc = G::operate(&acc, &w);
83                ord.push(eid);
84                let (u, v) = self[eid];
85                if leaf[v] >= self.edges_size() {
86                    leaf[v] = eid;
87                }
88                while cycle > 0 {
89                    paredge[ch.pop().unwrap()] = eid;
90                    cycle -= 1;
91                }
92                ch.push(eid);
93                if state[uf.find_root(u)] == 1 {
94                    while let Some(t) = path.pop() {
95                        state[t] = 2;
96                        cycle += 1;
97                        if !uf.unite(u, t) {
98                            break;
99                        }
100                    }
101                    state[uf.find_root(u)] = 1;
102                }
103                cur = uf.find_root(u);
104            }
105            for u in path.into_iter() {
106                state[u] = 2;
107            }
108        }
109        let mut tree = vec![root; self.vertices_size()];
110        let mut used = vec![false; self.edges_size()];
111        for eid in ord.into_iter().rev() {
112            if !used[eid] {
113                let (u, v) = self[eid];
114                tree[v] = u;
115                let mut x = leaf[v];
116                while x != eid {
117                    used[x] = true;
118                    x = paredge[x];
119                }
120            }
121        }
122        Some((acc, tree))
123    }
Source

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

Return an iterator over graph vertices.

Examples found in repository?
crates/competitive/src/graph/minimum_spanning_tree.rs (line 62)
29    pub fn minimum_spanning_arborescence<G, F>(
30        &self,
31        root: usize,
32        weight: F,
33    ) -> Option<(G::T, Vec<usize>)>
34    where
35        G: Group,
36        G::T: Ord,
37        F: Fn(usize) -> G::T,
38    {
39        use std::{cmp::Reverse, collections::BinaryHeap};
40        let mut uf = MergingUnionFind::new_with_merger(
41            self.vertices_size(),
42            |_| (BinaryHeap::new(), G::unit()),
43            |x, y| {
44                let ny = G::rinv_operate(&y.1, &x.1);
45                x.0.extend(
46                    (y.0)
47                        .drain()
48                        .map(|(Reverse(ref w), i)| (Reverse(G::operate(w, &ny)), i)),
49                )
50            },
51        );
52        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
53        state[root] = 2;
54        for (id, &(_, to)) in self.edges().enumerate() {
55            uf.merge_data_mut(to).0.push((Reverse(weight(id)), id));
56        }
57        let mut paredge = vec![0; self.edges_size()];
58        let mut ord = vec![];
59        let mut leaf = vec![self.edges_size(); self.vertices_size()];
60        let mut cycle = 0usize;
61        let mut acc = G::unit();
62        for mut cur in self.vertices() {
63            if state[cur] != 0 {
64                continue;
65            }
66            let mut path = vec![];
67            let mut ch = vec![];
68            while state[cur] != 2 {
69                path.push(cur);
70                state[cur] = 1;
71                let (w, eid) = {
72                    let (heap, lazy) = &mut uf.merge_data_mut(cur);
73                    match heap.pop() {
74                        Some((Reverse(w), eid)) => (G::operate(&w, lazy), eid),
75                        None => return None,
76                    }
77                };
78                {
79                    let curw = &mut uf.merge_data_mut(cur).1;
80                    *curw = G::rinv_operate(curw, &w);
81                }
82                acc = G::operate(&acc, &w);
83                ord.push(eid);
84                let (u, v) = self[eid];
85                if leaf[v] >= self.edges_size() {
86                    leaf[v] = eid;
87                }
88                while cycle > 0 {
89                    paredge[ch.pop().unwrap()] = eid;
90                    cycle -= 1;
91                }
92                ch.push(eid);
93                if state[uf.find_root(u)] == 1 {
94                    while let Some(t) = path.pop() {
95                        state[t] = 2;
96                        cycle += 1;
97                        if !uf.unite(u, t) {
98                            break;
99                        }
100                    }
101                    state[uf.find_root(u)] = 1;
102                }
103                cur = uf.find_root(u);
104            }
105            for u in path.into_iter() {
106                state[u] = 2;
107            }
108        }
109        let mut tree = vec![root; self.vertices_size()];
110        let mut used = vec![false; self.edges_size()];
111        for eid in ord.into_iter().rev() {
112            if !used[eid] {
113                let (u, v) = self[eid];
114                tree[v] = u;
115                let mut x = leaf[v];
116                while x != eid {
117                    used[x] = true;
118                    x = paredge[x];
119                }
120            }
121        }
122        Some((acc, tree))
123    }
Source

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

Examples found in repository?
crates/competitive/src/graph/minimum_spanning_tree.rs (line 54)
29    pub fn minimum_spanning_arborescence<G, F>(
30        &self,
31        root: usize,
32        weight: F,
33    ) -> Option<(G::T, Vec<usize>)>
34    where
35        G: Group,
36        G::T: Ord,
37        F: Fn(usize) -> G::T,
38    {
39        use std::{cmp::Reverse, collections::BinaryHeap};
40        let mut uf = MergingUnionFind::new_with_merger(
41            self.vertices_size(),
42            |_| (BinaryHeap::new(), G::unit()),
43            |x, y| {
44                let ny = G::rinv_operate(&y.1, &x.1);
45                x.0.extend(
46                    (y.0)
47                        .drain()
48                        .map(|(Reverse(ref w), i)| (Reverse(G::operate(w, &ny)), i)),
49                )
50            },
51        );
52        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
53        state[root] = 2;
54        for (id, &(_, to)) in self.edges().enumerate() {
55            uf.merge_data_mut(to).0.push((Reverse(weight(id)), id));
56        }
57        let mut paredge = vec![0; self.edges_size()];
58        let mut ord = vec![];
59        let mut leaf = vec![self.edges_size(); self.vertices_size()];
60        let mut cycle = 0usize;
61        let mut acc = G::unit();
62        for mut cur in self.vertices() {
63            if state[cur] != 0 {
64                continue;
65            }
66            let mut path = vec![];
67            let mut ch = vec![];
68            while state[cur] != 2 {
69                path.push(cur);
70                state[cur] = 1;
71                let (w, eid) = {
72                    let (heap, lazy) = &mut uf.merge_data_mut(cur);
73                    match heap.pop() {
74                        Some((Reverse(w), eid)) => (G::operate(&w, lazy), eid),
75                        None => return None,
76                    }
77                };
78                {
79                    let curw = &mut uf.merge_data_mut(cur).1;
80                    *curw = G::rinv_operate(curw, &w);
81                }
82                acc = G::operate(&acc, &w);
83                ord.push(eid);
84                let (u, v) = self[eid];
85                if leaf[v] >= self.edges_size() {
86                    leaf[v] = eid;
87                }
88                while cycle > 0 {
89                    paredge[ch.pop().unwrap()] = eid;
90                    cycle -= 1;
91                }
92                ch.push(eid);
93                if state[uf.find_root(u)] == 1 {
94                    while let Some(t) = path.pop() {
95                        state[t] = 2;
96                        cycle += 1;
97                        if !uf.unite(u, t) {
98                            break;
99                        }
100                    }
101                    state[uf.find_root(u)] = 1;
102                }
103                cur = uf.find_root(u);
104            }
105            for u in path.into_iter() {
106                state[u] = 2;
107            }
108        }
109        let mut tree = vec![root; self.vertices_size()];
110        let mut used = vec![false; self.edges_size()];
111        for eid in ord.into_iter().rev() {
112            if !used[eid] {
113                let (u, v) = self[eid];
114                tree[v] = u;
115                let mut x = leaf[v];
116                while x != eid {
117                    used[x] = true;
118                    x = paredge[x];
119                }
120            }
121        }
122        Some((acc, tree))
123    }
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<'a, I: Iterator<Item = &'a str>>(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_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 10)
6pub fn grl_2_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, w): @EdgeListGraphScanner::<usize, u64>::new(vs, es));
10    let span = graph.minimum_spanning_tree(|&eid| w[eid]);
11    let ans = (0..es).map(|eid| w[eid] * span[eid] as u64).sum::<u64>();
12    writeln!(writer, "{}", ans).ok();
13}
Source§

impl EdgeListGraph

Source

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

tarjan

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_2_b.rs (line 13)
9pub fn grl_2_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, root, (graph, w): @EdgeListGraphScanner::<usize, i64>::new(vs, es));
13    let res = graph.minimum_spanning_arborescence::<AdditiveOperation<_>, _>(root, |u| w[u]);
14    writeln!(writer, "{}", res.unwrap().0).ok();
15}
More examples
Hide additional examples
crates/library_checker/src/graph/directedmst.rs (line 11)
6pub fn directedmst(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, m, s, (graph, w): @EdgeListGraphScanner::<usize, i64>::new(n, m));
10    let res = graph
11        .minimum_spanning_arborescence::<AdditiveOperation<_>, _>(s, |u| w[u])
12        .unwrap();
13    iter_print!(writer, res.0; @it res.1);
14}

Trait Implementations§

Source§

impl Clone for EdgeListGraph

Source§

fn clone(&self) -> EdgeListGraph

Returns a duplicate of the value. Read more
1.0.0 · 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> 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 = Infallible

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

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

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.