Skip to main content

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

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}

Installation

Simply execute

pip install hopcroftkarp

or from this source distribution, run

python setup.py install

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
hopcroftkarp-1.2.4-py2.py3-none-any.whl (6.8 kB) Copy SHA256 hash SHA256 Wheel py2.py3 Oct 27, 2015
hopcroftkarp-1.2.4.tar.gz (17.0 kB) Copy SHA256 hash SHA256 Source None Oct 27, 2015

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page