#matching #graph #algorithm #bipartite #edge #karp #hopcroft

hopcroft-karp

A minimal implementation of the Hopcrof-Karp bipartite matching algorithm

4 releases

0.2.1 Sep 7, 2022
0.2.0 Sep 1, 2022
0.1.1 Aug 31, 2022
0.1.0 Aug 31, 2022

#1600 in Algorithms

Download history 13/week @ 2024-03-11 18/week @ 2024-03-18 27/week @ 2024-04-01 14/week @ 2024-04-08 19/week @ 2024-04-15 13/week @ 2024-04-22 5/week @ 2024-04-29 8/week @ 2024-05-06 10/week @ 2024-05-13 15/week @ 2024-05-20 77/week @ 2024-05-27 30/week @ 2024-06-03 19/week @ 2024-06-10 14/week @ 2024-06-17 17/week @ 2024-06-24

86 downloads per month
Used in shikane

MIT license

17KB
306 lines

crates.io github

This crate implements the Hopcroft-Karp algorithm to find maximum unweighted matchings in bipartite graph.

Basic usage

The crate provides the function hopcroft_karp::matching (plus a few variants) which takes as input a vector of edges (encoding the bipartite graph) and returns a maximum matching as a vector of edges.

Example usage:

    use hopcroft_karp::matching;

    fn main() {
        let edges = vec![(0,10), (0,11), (0,12), (1,11), (2,12)];
        let res = matching(&edges);
        assert_eq!(res.len(), 3);
    }

matching is generic over the vertex type, the trait bounds are Hash + Copy + Eq. For types where the copy operation is potentially expensive (e.g. strings) the crate provides the function hopcrof_karp::matching_mapped which internally maps the vertices onto integers and mostly avoids copying the type.

use hopcroft_karp::{matching, matching_mapped};

fn main() {
    let edges = vec![("spiderman", "doc octopus"), ("spiderman", "sandman"), ("spiderman", "green goblin"),
                     ("silk", "doc octopus"), ("silk", "green goblin"),  ("daredevil", "sandman")];
    let res = matching(&edges);
    assert_eq!(res.len(), 3);

    // For types where copying is expensive, use this instead
    let res = matching_mapped(&edges);
    assert_eq!(res.len(), 3);
}

Variants

The crate exposes further methods geared towards specific use-cases. If only the size of the matching is needed, hopcroft_karp::matching_size avoids constructing the solution matching. If only a matching above a certain size is needed, hopcroft_karp::bounded_matching returns a result as soon as the matching size lies above the provided bound.

These variants come in all possible combinations, e.g. hopcroft_karp::bounded_matching_mapped_size returns the size of a matching above the provided bound (or a smaller value if the bound is larger than the maximum matching) while internally re-mapping the graph's vertices to avoid expensive copy operations.

Dependencies

~135KB