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

Project details


Download files

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

Files for hopcroftkarp, version 1.2.5
Filename, size File type Python version Upload date Hashes
Filename, size hopcroftkarp-1.2.5.tar.gz (16.9 kB) File type Source Python version None Upload date Hashes View hashes

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 DigiCert DigiCert EV certificate StatusPage StatusPage Status page