Py Bipartite Matching
Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs.
Algorithm described in “Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs” By Takeaki Uno in “Algorithms and Computation: 8th International Symposium, ISAAC ‘97 Singapore, December 17-19, 1997 Proceedings” See http://dx.doi.org/10.1007/3-540-63890-3_11
Free software: MIT license
Documentation: https://py-bipartite-matching.readthedocs.io.
Features
- Functions available:
enum_perfect_matchings
enum_maximum_matchings
usage
To use Py Bipartite Matching in a project the networkx package is needed as well
>>> import py_bipartite_matching as pbm
>>> import networkx as nxUse enum_perfect_matchings to enumerate all perfect matchings
>>> n = 2
>>> graph = nx.complete_bipartite_graph(n, n, nx.Graph)
>>> for matching in pbm.enum_perfect_matchings(graph):
>>> print(matching)
{0: 2, 1: 3}
{0: 3, 1: 2}Use enum_maximum_matchings to enumerate all maximum matchings
>>> n = 2
>>> m = 3
>>> graph = nx.complete_bipartite_graph(n, m, nx.Graph)
>>> for matching in enum_maximum_matchings(graph):
>>> print(matching)
{0: 3, 1: 4}
{0: 4, 1: 3}
{0: 3, 2: 4}
{1: 3, 2: 4}
{0: 4, 2: 3}
{2: 3, 1: 4}Credits
This package was created with Cookiecutter and the audreyr/cookiecutter-pypackage project template.
History
0.2.0 (2021-04-25)
Implemented brute force functions
Increased testing of perfect and maximum matching enumerators
Fixed maximum matching enumeration (some results were missing)
improve code cleanness
0.1.16 (2021-04-04)
Iterators extended: top_nodes, bottom_nodes
More graphics utils
Removed plot_bipartite, only draw functions now
0.1.15 (2021-04-04)
Iterators implemented: top_nodes, bottom_nodes
Utils to plot with matplotlib: draw_bipartite, plot_bipartite
0.1.10 (2021-04-02)
Functions already available: enum_perfect_matchings and enum_maximum_matchings
Readme files updated
0.1.0 (2021-02-14)
First release on PyPI.
1 maintainer
Metadata
1 maintainer
Release files for py-bipartite-matching 0.2.0
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| py_bipartite_matching-0.2.0.tar.gz | 17.6 kB | Details |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Reset |
|---|---|---|---|---|
| py_bipartite_matching-0.2.0-py2.py3-none-any.whl | Python 3, Python 2 | none | any | Details |
Total release size: 27.8 kB
Release files / py_bipartite_matching-0.2.0.tar.gz
| Download URL | py_bipartite_matching-0.2.0.tar.gz |
|---|---|
| Size | 17.6 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
8dcd087dfd2061977618bb6bdb770ff37a935ef1e71a3e122f8edfac3c5825c4
|
|
BLAKE2b-256 checksum How to use checksums |
d1e187064bd38bbb3efa2b2f87fc56da06c68cbe5a150d704a029203b3d2e065
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/3.4.1 importlib_metadata/4.0.1 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.60.0 CPython/3.8.7
|
Release files / py_bipartite_matching-0.2.0-py2.py3-none-any.whl
| Download URL | py_bipartite_matching-0.2.0-py2.py3-none-any.whl |
|---|---|
| Size | 10.3 kB |
| Tags | Python 2 Python 3 |
|
SHA-256 checksum How to use checksums |
4ae8212bbd2ef4b24950d754010272d339645afdb2c140edf309134f2ef68c0c
|
|
BLAKE2b-256 checksum How to use checksums |
bacf6a9ee4f7fa143649c8f2802c9ff0c69b019a249583621de0d805e7df4ade
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/3.4.1 importlib_metadata/4.0.1 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.60.0 CPython/3.8.7
|
