Implementation of HopcroftKarp's algorithm
Project description
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 matchings. It is worth noting that the algorithm can output any of the maximum matching.
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}
Installation
Simply execute
easy_install hopcroftkarp
or from this source distribution, run
python setup.py install
Project details
NoneRelease history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
hopcroftkarp-1.2.3.tar.gz
(16.9 kB
view hashes)
Built Distribution
Close
Hashes for hopcroftkarp-1.2.3-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eac610960dafa3645eb876b4390dd1f2f707508e75570bdd7c3a1ccb168763db |
|
MD5 | 6054b894f111a5afd67282dad97c038d |
|
BLAKE2b-256 | 5cc5d546c25de6ee8f92bf614dc20098d4e5ebe726b369d986e9023a82618d51 |