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
pip install hopcroftkarp
or from this source distribution, run
python setup.py install
Project details
Release 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.4.tar.gz
(17.0 kB
view hashes)
Built Distribution
Close
Hashes for hopcroftkarp-1.2.4-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 43144e5bfcafa94acaa4d127fbd1e7c83ce35c65d7268ab869d4524c7cf4b8c9 |
|
MD5 | 8c57f91efdc3db07498934dadee1481d |
|
BLAKE2b-256 | 44593efc05c6021b847b9f7d803432d499019b336a05f9bfcff90cf63c939356 |