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