{ "info": { "author": "Sofiat Olaosebikan", "author_email": "sofiat@aims.edu.gh", "bugtrack_url": null, "classifiers": [ "Development Status :: 3 - Alpha", "Intended Audience :: Science/Research", "License :: OSI Approved :: GNU General Public License v3 (GPLv3)", "Programming Language :: Python :: 2.6", "Programming Language :: Python :: 2.7", "Programming Language :: Python :: 3.2", "Programming Language :: Python :: 3.3", "Programming Language :: Python :: 3.4", "Programming Language :: Python :: 3.5", "Programming Language :: Python :: 3.6" ], "description": "Python Implementation of HopcroftKarp's Algorithm\n=================================================\n\nhopcroftkarp is a library based on Hopcroft Karp's Algorithm. It takes as input a bipartite graph and produces a maximum cardinality matching as output. \n\nSince 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.\n\nPseudo code gotten from https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm\n \n\n \nExample\n~~~~~~~\n\n.. image:: https://raw.githubusercontent.com/sofiat-olaosebikan/hopcroftkarp/master/image/bipartite_graph.png\n \n.. code::\n\n\t>>> from hopcroftkarp import HopcroftKarp\n\t>>> 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}}\n\t>>> HopcroftKarp(graph).maximum_matching()\n\t\t{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}\n\t\t\nKeys Only\n\"\"\"\"\"\"\"\"\"\n\nBy default, `.maximum_matching()` returns a dictionary in which every edge (match) is represented twice:\n\n.. code::\n\n {left: right,\n right: left}\n \nTo return a dictionary with each edge represented only once, pass in `keys_only=True`.\n\n.. code::\n\n >>> 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}}\n >>> HopcroftKarp(graph).maximum_matching(keys_only=True)\n {'a': 1, 'd': 4, 'e': 3, 'h': 8, 'b': 2, 'f': 6, 'g': 5} \n\t\t\n\t\t\n\t\t\nInstallation\n~~~~~~~~~~~~\n\nSimply execute\n\n.. code::\n\n pip install hopcroftkarp\n\n\nor from this source distribution, run\n\n.. code::\n\n python setup.py install\n\n\n\nThis 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.\n\n\nThanks to Adam Wood (github.com/adammichaelwood) for suggesting the keys only option.", "description_content_type": "", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/sofiat-olaosebikan/hopcroftkarp", "keywords": "hopcroftkarp algorithm,maximum cardinality matching,bipartite graphs", "license": "GPL", "maintainer": "", "maintainer_email": "", "name": "hopcroftkarp", "package_url": "https://pypi.org/project/hopcroftkarp/", "platform": "", "project_url": "https://pypi.org/project/hopcroftkarp/", "project_urls": { "Homepage": "https://github.com/sofiat-olaosebikan/hopcroftkarp" }, "release_url": "https://pypi.org/project/hopcroftkarp/1.2.5/", "requires_dist": null, "requires_python": "", "summary": "Implementation of HopcroftKarp's algorithm", "version": "1.2.5" }, "last_serial": 5960369, "releases": { "1.2.3": [ { "comment_text": "", "digests": { "md5": "6054b894f111a5afd67282dad97c038d", "sha256": "eac610960dafa3645eb876b4390dd1f2f707508e75570bdd7c3a1ccb168763db" }, "downloads": -1, "filename": "hopcroftkarp-1.2.3-py2.py3-none-any.whl", "has_sig": false, "md5_digest": "6054b894f111a5afd67282dad97c038d", "packagetype": "bdist_wheel", "python_version": "py2.py3", "requires_python": null, "size": 6803, "upload_time": "2015-08-30T20:57:25", "url": "https://files.pythonhosted.org/packages/5c/c5/d546c25de6ee8f92bf614dc20098d4e5ebe726b369d986e9023a82618d51/hopcroftkarp-1.2.3-py2.py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "d81d4d2baed99d933cd59b9b9cab0df1", "sha256": "b1ee254329b853b91bd5e91bc07a30990672b7c2765f414f3f61b4c8b6f3298b" }, "downloads": -1, "filename": "hopcroftkarp-1.2.3.tar.gz", "has_sig": false, "md5_digest": "d81d4d2baed99d933cd59b9b9cab0df1", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 16908, "upload_time": "2015-08-30T20:57:57", "url": "https://files.pythonhosted.org/packages/a9/bb/9800aab5f558c6d138e0496f3d2291906754d562fcff3f56317e3bc1865d/hopcroftkarp-1.2.3.tar.gz" } ], "1.2.4": [ { "comment_text": "", "digests": { "md5": "8c57f91efdc3db07498934dadee1481d", "sha256": "43144e5bfcafa94acaa4d127fbd1e7c83ce35c65d7268ab869d4524c7cf4b8c9" }, "downloads": -1, "filename": "hopcroftkarp-1.2.4-py2.py3-none-any.whl", "has_sig": false, "md5_digest": "8c57f91efdc3db07498934dadee1481d", "packagetype": "bdist_wheel", "python_version": "py2.py3", "requires_python": null, "size": 6787, "upload_time": "2015-10-27T15:17:25", "url": "https://files.pythonhosted.org/packages/44/59/3efc05c6021b847b9f7d803432d499019b336a05f9bfcff90cf63c939356/hopcroftkarp-1.2.4-py2.py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "56f57520a742615f3b0e2663c4fe0d62", "sha256": "cc6fc7ad348bbe5c9451f8116845c46ae26290c92b2dd14690aae2d55ba5e3a6" }, "downloads": -1, "filename": "hopcroftkarp-1.2.4.tar.gz", "has_sig": false, "md5_digest": "56f57520a742615f3b0e2663c4fe0d62", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 17029, "upload_time": "2015-10-27T15:17:49", "url": "https://files.pythonhosted.org/packages/4f/b1/5e28651fbecd419638e26c348b9d17bc7af7fc77d126ea39050ca3a37e30/hopcroftkarp-1.2.4.tar.gz" } ], "1.2.5": [ { "comment_text": "", "digests": { "md5": "f5a8c38fd16363715c687bc462c12510", "sha256": "28a7887db81ad995ccd36a1b5164a4c542b16d2781e8c49334dc9d141968c0e7" }, "downloads": -1, "filename": "hopcroftkarp-1.2.5.tar.gz", "has_sig": false, "md5_digest": "f5a8c38fd16363715c687bc462c12510", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 16856, "upload_time": "2019-10-11T13:36:15", "url": "https://files.pythonhosted.org/packages/6b/56/7b03eba3c43008c490c9d52e69ea5334b65955f66836eb4f1962f3b0d421/hopcroftkarp-1.2.5.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "f5a8c38fd16363715c687bc462c12510", "sha256": "28a7887db81ad995ccd36a1b5164a4c542b16d2781e8c49334dc9d141968c0e7" }, "downloads": -1, "filename": "hopcroftkarp-1.2.5.tar.gz", "has_sig": false, "md5_digest": "f5a8c38fd16363715c687bc462c12510", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 16856, "upload_time": "2019-10-11T13:36:15", "url": "https://files.pythonhosted.org/packages/6b/56/7b03eba3c43008c490c9d52e69ea5334b65955f66836eb4f1962f3b0d421/hopcroftkarp-1.2.5.tar.gz" } ] }