Struct BipartiteMatching

Source

pub struct BipartiteMatching {
    left_size: usize,
    right_size: usize,
    left_graph: Vec<Vec<usize>>,
    right_graph: Vec<Vec<usize>>,
    left_match: Vec<Option<usize>>,
    right_match: Vec<Option<usize>>,
    matching_size: usize,
}

Fields§

§left_size: usize§right_size: usize§left_graph: Vec<Vec<usize>>§right_graph: Vec<Vec<usize>>§left_match: Vec<Option<usize>>§right_match: Vec<Option<usize>>§matching_size: usize

Implementations§

Source §

pub fn from_edges( left_size: usize, right_size: usize, lr: &[(usize, usize)], ) -> Self

Examples found in repository ?

crates/library_checker/src/graph/bipartitematching.rs (line 34)

31pub fn bipartitematching(reader: impl Read, writer: impl Write) {
32    prepare_io!(reader, writer);
33    sc!(l, r, m, ab: [(usize, usize); m]);
34    let mut bm = BipartiteMatching::from_edges(l, r, &ab);
35    let matching = bm.maximum_matching();
36    pp!(matching.len(); @ittup matching);
37}

More examples

Hide additional examples

crates/competitive/src/graph/dulmage_mendelsohn_decomposition.rs (line 10)

3pub fn dulmage_mendelsohn_decomposition(
4    l: usize,
5    r: usize,
6    edges: &[(usize, usize)],
7) -> Vec<(Vec<usize>, Vec<usize>)> {
8    let mut matching = vec![!0usize; l + r];
9    let mut medges: Vec<_> = edges.iter().map(|&(u, v)| (u, v + l)).collect();
10    for (u, v) in BipartiteMatching::from_edges(l, r, edges).maximum_matching() {
11        medges.push((v + l, u));
12        matching[u] = v + l;
13        matching[v + l] = u;
14    }
15    let rmedges = medges.iter().map(|&(u, v)| (v, u)).collect();
16
17    let g = DirectedSparseGraph::from_edges(l + r, medges);
18    let rg = DirectedSparseGraph::from_edges(l + r, rmedges);
19    let scc = StronglyConnectedComponent::new(&g);
20    let csize = scc.size();
21
22    let mut cmap = vec![!0usize - 1; csize];
23    let mut visited = vec![false; l + r];
24    let mut stack = vec![];
25    for u in 0..l {
26        if matching[u] == !0 && !visited[u] {
27            visited[u] = true;
28            stack.push(u);
29            while let Some(u) = stack.pop() {
30                cmap[scc[u]] = !0;
31                for a in g.neighbors(u) {
32                    if !visited[a.to] {
33                        visited[a.to] = true;
34                        stack.push(a.to);
35                    }
36                }
37            }
38        }
39    }
40    for u in l..l + r {
41        if matching[u] == !0 && !visited[u] {
42            visited[u] = true;
43            stack.push(u);
44            while let Some(u) = stack.pop() {
45                cmap[scc[u]] = 0;
46                for a in rg.neighbors(u) {
47                    if !visited[a.to] {
48                        visited[a.to] = true;
49                        stack.push(a.to);
50                    }
51                }
52            }
53        }
54    }
55
56    let mut nset = 1usize;
57    for v in &mut cmap {
58        if *v == !0 - 1 {
59            *v = nset;
60            nset += 1;
61        }
62    }
63    for v in &mut cmap {
64        if *v == !0 {
65            *v = nset;
66        }
67    }
68    nset += 1;
69
70    let mut groups = vec![(vec![], vec![]); nset];
71    for u in 0..l {
72        if matching[u] != !0 {
73            let c = cmap[scc[u]];
74            groups[c].0.push(u);
75            groups[c].1.push(matching[u] - l);
76        }
77    }
78    for u in 0..l {
79        if matching[u] == !0 {
80            let c = cmap[scc[u]];
81            groups[c].0.push(u);
82        }
83    }
84    for u in 0..r {
85        if matching[u + l] == !0 {
86            let c = cmap[scc[u + l]];
87            groups[c].1.push(u);
88        }
89    }
90    groups
91}

Source

pub fn hopcroft_karp(&mut self)

Source

pub fn kuhn_multi_start_bfs(&mut self)

Source

pub fn push_relabel(&mut self)

Examples found in repository ?

crates/competitive/src/graph/bipartite_matching.rs (line 249)

248    pub fn maximum_matching(&mut self) -> Vec<(usize, usize)> {
249        self.push_relabel();
250        self.left_match
251            .iter()
252            .enumerate()
253            .filter_map(|(l, r)| r.map(|r| (l, r)))
254            .collect()
255    }
256    pub fn minimum_edge_cover(&mut self) -> Vec<(usize, usize)> {
257        self.push_relabel();
258        let mut res = Vec::with_capacity(self.left_size + self.right_size - self.matching_size);
259        let mut left_used: Vec<_> = self.left_match.iter().map(Option::is_some).collect();
260        let mut right_used: Vec<_> = self.right_match.iter().map(Option::is_some).collect();
261        for (l, lg) in self.left_graph.iter().enumerate() {
262            if let Some(r) = self.left_match[l] {
263                res.push((l, r));
264            }
265            for &r in lg {
266                if !left_used[l] || !right_used[r] {
267                    left_used[l] = true;
268                    right_used[r] = true;
269                    res.push((l, r));
270                }
271            }
272        }
273        res
274    }
275    fn reachable(&mut self) -> (Vec<bool>, Vec<bool>) {
276        #[derive(Clone, Copy)]
277        enum Either {
278            Left(usize),
279            Right(usize),
280        }
281        self.push_relabel();
282        let mut left_used = vec![false; self.left_size];
283        let mut right_used = vec![false; self.right_size];
284        let mut deq = VecDeque::new();
285        for (l, r) in self.left_match.iter().enumerate() {
286            if r.is_none() {
287                left_used[l] = true;
288                deq.push_back(Either::Left(l));
289            }
290        }
291        loop {
292            match deq.pop_front() {
293                Some(Either::Left(l)) => {
294                    for &r in &self.left_graph[l] {
295                        if self.left_match[l] != Some(r) && !right_used[r] {
296                            right_used[r] = true;
297                            deq.push_back(Either::Right(r));
298                        }
299                    }
300                }
301                Some(Either::Right(r)) => {
302                    if let Some(l) = self.right_match[r]
303                        && !left_used[l]
304                    {
305                        left_used[l] = true;
306                        deq.push_back(Either::Left(l));
307                    }
308                }
309                None => break,
310            }
311        }
312        (left_used, right_used)
313    }

Source

pub fn maximum_matching(&mut self) -> Vec<(usize, usize)>

Examples found in repository ?

crates/library_checker/src/graph/bipartitematching.rs (line 35)

31pub fn bipartitematching(reader: impl Read, writer: impl Write) {
32    prepare_io!(reader, writer);
33    sc!(l, r, m, ab: [(usize, usize); m]);
34    let mut bm = BipartiteMatching::from_edges(l, r, &ab);
35    let matching = bm.maximum_matching();
36    pp!(matching.len(); @ittup matching);
37}

More examples

Hide additional examples

crates/competitive/src/graph/dulmage_mendelsohn_decomposition.rs (line 10)

3pub fn dulmage_mendelsohn_decomposition(
4    l: usize,
5    r: usize,
6    edges: &[(usize, usize)],
7) -> Vec<(Vec<usize>, Vec<usize>)> {
8    let mut matching = vec![!0usize; l + r];
9    let mut medges: Vec<_> = edges.iter().map(|&(u, v)| (u, v + l)).collect();
10    for (u, v) in BipartiteMatching::from_edges(l, r, edges).maximum_matching() {
11        medges.push((v + l, u));
12        matching[u] = v + l;
13        matching[v + l] = u;
14    }
15    let rmedges = medges.iter().map(|&(u, v)| (v, u)).collect();
16
17    let g = DirectedSparseGraph::from_edges(l + r, medges);
18    let rg = DirectedSparseGraph::from_edges(l + r, rmedges);
19    let scc = StronglyConnectedComponent::new(&g);
20    let csize = scc.size();
21
22    let mut cmap = vec![!0usize - 1; csize];
23    let mut visited = vec![false; l + r];
24    let mut stack = vec![];
25    for u in 0..l {
26        if matching[u] == !0 && !visited[u] {
27            visited[u] = true;
28            stack.push(u);
29            while let Some(u) = stack.pop() {
30                cmap[scc[u]] = !0;
31                for a in g.neighbors(u) {
32                    if !visited[a.to] {
33                        visited[a.to] = true;
34                        stack.push(a.to);
35                    }
36                }
37            }
38        }
39    }
40    for u in l..l + r {
41        if matching[u] == !0 && !visited[u] {
42            visited[u] = true;
43            stack.push(u);
44            while let Some(u) = stack.pop() {
45                cmap[scc[u]] = 0;
46                for a in rg.neighbors(u) {
47                    if !visited[a.to] {
48                        visited[a.to] = true;
49                        stack.push(a.to);
50                    }
51                }
52            }
53        }
54    }
55
56    let mut nset = 1usize;
57    for v in &mut cmap {
58        if *v == !0 - 1 {
59            *v = nset;
60            nset += 1;
61        }
62    }
63    for v in &mut cmap {
64        if *v == !0 {
65            *v = nset;
66        }
67    }
68    nset += 1;
69
70    let mut groups = vec![(vec![], vec![]); nset];
71    for u in 0..l {
72        if matching[u] != !0 {
73            let c = cmap[scc[u]];
74            groups[c].0.push(u);
75            groups[c].1.push(matching[u] - l);
76        }
77    }
78    for u in 0..l {
79        if matching[u] == !0 {
80            let c = cmap[scc[u]];
81            groups[c].0.push(u);
82        }
83    }
84    for u in 0..r {
85        if matching[u + l] == !0 {
86            let c = cmap[scc[u + l]];
87            groups[c].1.push(u);
88        }
89    }
90    groups
91}

Source

pub fn minimum_edge_cover(&mut self) -> Vec<(usize, usize)>

Source

fn reachable(&mut self) -> (Vec<bool>, Vec<bool>)

Examples found in repository ?

crates/competitive/src/graph/bipartite_matching.rs (line 315)

314    pub fn minimum_vertex_cover(&mut self) -> (Vec<usize>, Vec<usize>) {
315        let (left_used, right_used) = self.reachable();
316        (
317            left_used
318                .into_iter()
319                .enumerate()
320                .filter_map(|(l, b)| if !b { Some(l) } else { None })
321                .collect(),
322            right_used
323                .into_iter()
324                .enumerate()
325                .filter_map(|(r, b)| if b { Some(r) } else { None })
326                .collect(),
327        )
328    }
329    pub fn maximum_independent_set(&mut self) -> (Vec<usize>, Vec<usize>) {
330        let (left_used, right_used) = self.reachable();
331        (
332            left_used
333                .into_iter()
334                .enumerate()
335                .filter_map(|(l, b)| if b { Some(l) } else { None })
336                .collect(),
337            right_used
338                .into_iter()
339                .enumerate()
340                .filter_map(|(r, b)| if !b { Some(r) } else { None })
341                .collect(),
342        )
343    }