Struct BipartiteMatching

pub struct BipartiteMatching { /* private fields */ }

Implementations

impl BipartiteMatching

pub fn new(left_size: usize, right_size: usize) -> Self

pub fn add_edge(&mut self, l: usize, r: usize)

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

pub fn bipartitematching(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, l, r, m, ab: [(usize, usize); m]);
    let mut bm = BipartiteMatching::from_edges(l, r, &ab);
    let matching = bm.maximum_matching();
    writeln!(writer, "{}", matching.len()).ok();
    for (x, y) in matching {
        writeln!(writer, "{} {}", x, y).ok();
    }
}

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

pub fn dulmage_mendelsohn_decomposition(
    l: usize,
    r: usize,
    edges: &[(usize, usize)],
) -> Vec<(Vec<usize>, Vec<usize>)> {
    let mut matching = vec![!0usize; l + r];
    let mut medges: Vec<_> = edges.iter().map(|&(u, v)| (u, v + l)).collect();
    for (u, v) in BipartiteMatching::from_edges(l, r, edges).maximum_matching() {
        medges.push((v + l, u));
        matching[u] = v + l;
        matching[v + l] = u;
    }
    let rmedges = medges.iter().map(|&(u, v)| (v, u)).collect();

    let g = DirectedSparseGraph::from_edges(l + r, medges);
    let rg = DirectedSparseGraph::from_edges(l + r, rmedges);
    let scc = StronglyConnectedComponent::new(&g);
    let csize = scc.size();

    let mut cmap = vec![!0usize - 1; csize];
    let mut visited = vec![false; l + r];
    let mut stack = vec![];
    for u in 0..l {
        if matching[u] == !0 && !visited[u] {
            visited[u] = true;
            stack.push(u);
            while let Some(u) = stack.pop() {
                cmap[scc[u]] = !0;
                for a in g.adjacencies(u) {
                    if !visited[a.to] {
                        visited[a.to] = true;
                        stack.push(a.to);
                    }
                }
            }
        }
    }
    for u in l..l + r {
        if matching[u] == !0 && !visited[u] {
            visited[u] = true;
            stack.push(u);
            while let Some(u) = stack.pop() {
                cmap[scc[u]] = 0;
                for a in rg.adjacencies(u) {
                    if !visited[a.to] {
                        visited[a.to] = true;
                        stack.push(a.to);
                    }
                }
            }
        }
    }

    let mut nset = 1usize;
    for v in &mut cmap {
        if *v == !0 - 1 {
            *v = nset;
            nset += 1;
        }
    }
    for v in &mut cmap {
        if *v == !0 {
            *v = nset;
        }
    }
    nset += 1;

    let mut groups = vec![(vec![], vec![]); nset];
    for u in 0..l {
        if matching[u] != !0 {
            let c = cmap[scc[u]];
            groups[c].0.push(u);
            groups[c].1.push(matching[u] - l);
        }
    }
    for u in 0..l {
        if matching[u] == !0 {
            let c = cmap[scc[u]];
            groups[c].0.push(u);
        }
    }
    for u in 0..r {
        if matching[u + l] == !0 {
            let c = cmap[scc[u + l]];
            groups[c].1.push(u);
        }
    }
    groups
}

pub fn hopcroft_karp(&mut self)

pub fn kuhn_multi_start_bfs(&mut self)

Examples found in repository

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

    pub fn maximum_matching(&mut self) -> Vec<(usize, usize)> {
        self.kuhn_multi_start_bfs();
        self.left_match
            .iter()
            .enumerate()
            .filter_map(|(l, r)| r.map(|r| (l, r)))
            .collect()
    }
    pub fn minimum_edge_cover(&mut self) -> Vec<(usize, usize)> {
        self.kuhn_multi_start_bfs();
        let mut res = Vec::with_capacity(self.left_size + self.right_size - self.matching_size);
        let mut left_used: Vec<_> = self.left_match.iter().map(Option::is_some).collect();
        let mut right_used: Vec<_> = self.right_match.iter().map(Option::is_some).collect();
        for (l, lg) in self.left_graph.iter().enumerate() {
            if let Some(r) = self.left_match[l] {
                res.push((l, r));
            }
            for &r in lg {
                if !left_used[l] || !right_used[r] {
                    left_used[l] = true;
                    right_used[r] = true;
                    res.push((l, r));
                }
            }
        }
        res
    }
    fn reachable(&mut self) -> (Vec<bool>, Vec<bool>) {
        #[derive(Clone, Copy)]
        enum Either {
            Left(usize),
            Right(usize),
        }
        self.kuhn_multi_start_bfs();
        let mut left_used = vec![false; self.left_size];
        let mut right_used = vec![false; self.right_size];
        let mut deq = VecDeque::new();
        for (l, r) in self.left_match.iter().enumerate() {
            if r.is_none() {
                left_used[l] = true;
                deq.push_back(Either::Left(l));
            }
        }
        loop {
            match deq.pop_front() {
                Some(Either::Left(l)) => {
                    for &r in &self.left_graph[l] {
                        if self.left_match[l] != Some(r) && !right_used[r] {
                            right_used[r] = true;
                            deq.push_back(Either::Right(r));
                        }
                    }
                }
                Some(Either::Right(r)) => {
                    if let Some(l) = self.right_match[r] {
                        if !left_used[l] {
                            left_used[l] = true;
                            deq.push_back(Either::Left(l));
                        }
                    }
                }
                None => break,
            }
        }
        (left_used, right_used)
    }

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

Examples found in repository

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

pub fn bipartitematching(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, l, r, m, ab: [(usize, usize); m]);
    let mut bm = BipartiteMatching::from_edges(l, r, &ab);
    let matching = bm.maximum_matching();
    writeln!(writer, "{}", matching.len()).ok();
    for (x, y) in matching {
        writeln!(writer, "{} {}", x, y).ok();
    }
}

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

pub fn dulmage_mendelsohn_decomposition(
    l: usize,
    r: usize,
    edges: &[(usize, usize)],
) -> Vec<(Vec<usize>, Vec<usize>)> {
    let mut matching = vec![!0usize; l + r];
    let mut medges: Vec<_> = edges.iter().map(|&(u, v)| (u, v + l)).collect();
    for (u, v) in BipartiteMatching::from_edges(l, r, edges).maximum_matching() {
        medges.push((v + l, u));
        matching[u] = v + l;
        matching[v + l] = u;
    }
    let rmedges = medges.iter().map(|&(u, v)| (v, u)).collect();

    let g = DirectedSparseGraph::from_edges(l + r, medges);
    let rg = DirectedSparseGraph::from_edges(l + r, rmedges);
    let scc = StronglyConnectedComponent::new(&g);
    let csize = scc.size();

    let mut cmap = vec![!0usize - 1; csize];
    let mut visited = vec![false; l + r];
    let mut stack = vec![];
    for u in 0..l {
        if matching[u] == !0 && !visited[u] {
            visited[u] = true;
            stack.push(u);
            while let Some(u) = stack.pop() {
                cmap[scc[u]] = !0;
                for a in g.adjacencies(u) {
                    if !visited[a.to] {
                        visited[a.to] = true;
                        stack.push(a.to);
                    }
                }
            }
        }
    }
    for u in l..l + r {
        if matching[u] == !0 && !visited[u] {
            visited[u] = true;
            stack.push(u);
            while let Some(u) = stack.pop() {
                cmap[scc[u]] = 0;
                for a in rg.adjacencies(u) {
                    if !visited[a.to] {
                        visited[a.to] = true;
                        stack.push(a.to);
                    }
                }
            }
        }
    }

    let mut nset = 1usize;
    for v in &mut cmap {
        if *v == !0 - 1 {
            *v = nset;
            nset += 1;
        }
    }
    for v in &mut cmap {
        if *v == !0 {
            *v = nset;
        }
    }
    nset += 1;

    let mut groups = vec![(vec![], vec![]); nset];
    for u in 0..l {
        if matching[u] != !0 {
            let c = cmap[scc[u]];
            groups[c].0.push(u);
            groups[c].1.push(matching[u] - l);
        }
    }
    for u in 0..l {
        if matching[u] == !0 {
            let c = cmap[scc[u]];
            groups[c].0.push(u);
        }
    }
    for u in 0..r {
        if matching[u + l] == !0 {
            let c = cmap[scc[u + l]];
            groups[c].1.push(u);
        }
    }
    groups
}

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

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

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

Trait Implementations

impl Clone for BipartiteMatching

fn clone(&self) -> BipartiteMatching

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for BipartiteMatching

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

Formats the value using the given formatter.