### 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

**86** downloads per month

Used in shikane

**MIT**license

17KB

306 lines

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

## Basic usage

The crate provides the function

(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.`hopcroft_karp ::`matching

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``)``;`
`}`

is generic over the vertex type, the trait bounds are `matching`

. For types where the copy operation
is potentially expensive (e.g. strings) the crate provides the function `Hash + Copy + Eq`

`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,

avoids constructing the solution matching. If only a matching above a certain size is needed,
`hopcroft_karp ::`matching_size

`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.

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.`hopcroft_karp ::`bounded_matching_mapped_size

#### Dependencies

~135KB