Skip to main content

Python Implementation of HopcroftKarp’s Algorithm

hopcroftkarp is a library based on Hopcroft Karp’s Algorithm. It takes as input a bipartite graph and produces a maximum cardinality matching as output.

Since a bipartite graph might have more than one maximum matching, it is worth noting that the algorithm may output any one of all possible maximum matchings.

Pseudo code gotten from https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

Example

https://raw.githubusercontent.com/sofiat-olaosebikan/hopcroftkarp/master/image/bipartite_graph.png
>>> from hopcroftkarp import HopcroftKarp
>>> graph = {'a': {1}, 'b': {1, 2}, 'c': {1, 2}, 'd': {2, 3, 4}, 'e': {3, 4}, 'f': {4, 5, 6}, 'g': {5, 6, 7}, 'h': {8}}
>>> HopcroftKarp(graph).maximum_matching()
        {1: 'a', 2: 'b', 3: 'e', 4: 'd', 5: 'g', 6: 'f', 8: 'h', 'a': 1, 'd': 4, 'e': 3, 'h': 8, 'b': 2, 'f': 6, 'g': 5}

Keys Only

By default, .maximum_matching() returns a dictionary in which every edge (match) is represented twice:

{left: right,
 right: left}

To return a dictionary with each edge represented only once, pass in keys_only=True.

>>> graph = {'a': {1}, 'b': {1, 2}, 'c': {1, 2}, 'd': {2, 3, 4}, 'e': {3, 4}, 'f': {4, 5, 6}, 'g': {5, 6, 7}, 'h': {8}}
>>> HopcroftKarp(graph).maximum_matching(keys_only=True)
    {'a': 1, 'd': 4, 'e': 3, 'h': 8, 'b': 2, 'f': 6, 'g': 5}

Installation

Simply execute

pip install hopcroftkarp

or from this source distribution, run

python setup.py install

This project was completed while the author was studying at the African Institute for Mathematical Sciences, Ghana. Thanks to AIMS-Ghana for the funding. Also, thanks to Prof Nancy Neudauer and Frantisek Hajnovic for the supervision.

Thanks to Adam Wood (github.com/adammichaelwood) for suggesting the keys only option.

Metadata

Release files for hopcroftkarp 1.2.5

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for hopcroftkarp 1.2.5
File Size Uploaded Provenance Actions
hopcroftkarp-1.2.5.tar.gz 16.9 kB Without provenance Details for hopcroftkarp-1.2.5.tar.gz

Release files / hopcroftkarp-1.2.5.tar.gz

Download URL hopcroftkarp-1.2.5.tar.gz
Size 16.9 kB
Tags Source
SHA-256 checksum
How to use checksums
28a7887db81ad995ccd36a1b5164a4c542b16d2781e8c49334dc9d141968c0e7
BLAKE2b-256 checksum
How to use checksums
6b567b03eba3c43008c490c9d52e69ea5334b65955f66836eb4f1962f3b0d421
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/1.10.0 pkginfo/1.2.1 requests/2.18.4 setuptools/39.0.1 requests-toolbelt/0.8.0 tqdm/4.19.5 CPython/3.6.8

Security for hopcroftkarp 1.2.5

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page