diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | python-hopcroftkarp.spec | 147 | ||||
| -rw-r--r-- | sources | 1 |
3 files changed, 149 insertions, 0 deletions
@@ -0,0 +1 @@ +/hopcroftkarp-1.2.5.tar.gz diff --git a/python-hopcroftkarp.spec b/python-hopcroftkarp.spec new file mode 100644 index 0000000..14ad69a --- /dev/null +++ b/python-hopcroftkarp.spec @@ -0,0 +1,147 @@ +%global _empty_manifest_terminate_build 0 +Name: python-hopcroftkarp +Version: 1.2.5 +Release: 1 +Summary: Implementation of HopcroftKarp's algorithm +License: GPL +URL: https://github.com/sofiat-olaosebikan/hopcroftkarp +Source0: https://mirrors.nju.edu.cn/pypi/web/packages/6b/56/7b03eba3c43008c490c9d52e69ea5334b65955f66836eb4f1962f3b0d421/hopcroftkarp-1.2.5.tar.gz +BuildArch: noarch + + +%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 +~~~~~~~ + >>> 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. + +%package -n python3-hopcroftkarp +Summary: Implementation of HopcroftKarp's algorithm +Provides: python-hopcroftkarp +BuildRequires: python3-devel +BuildRequires: python3-setuptools +BuildRequires: python3-pip +%description -n python3-hopcroftkarp +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 +~~~~~~~ + >>> 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. + +%package help +Summary: Development documents and examples for hopcroftkarp +Provides: python3-hopcroftkarp-doc +%description help +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 +~~~~~~~ + >>> 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. + +%prep +%autosetup -n hopcroftkarp-1.2.5 + +%build +%py3_build + +%install +%py3_install +install -d -m755 %{buildroot}/%{_pkgdocdir} +if [ -d doc ]; then cp -arf doc %{buildroot}/%{_pkgdocdir}; fi +if [ -d docs ]; then cp -arf docs %{buildroot}/%{_pkgdocdir}; fi +if [ -d example ]; then cp -arf example %{buildroot}/%{_pkgdocdir}; fi +if [ -d examples ]; then cp -arf examples %{buildroot}/%{_pkgdocdir}; fi +pushd %{buildroot} +if [ -d usr/lib ]; then + find usr/lib -type f -printf "/%h/%f\n" >> filelist.lst +fi +if [ -d usr/lib64 ]; then + find usr/lib64 -type f -printf "/%h/%f\n" >> filelist.lst +fi +if [ -d usr/bin ]; then + find usr/bin -type f -printf "/%h/%f\n" >> filelist.lst +fi +if [ -d usr/sbin ]; then + find usr/sbin -type f -printf "/%h/%f\n" >> filelist.lst +fi +touch doclist.lst +if [ -d usr/share/man ]; then + find usr/share/man -type f -printf "/%h/%f.gz\n" >> doclist.lst +fi +popd +mv %{buildroot}/filelist.lst . +mv %{buildroot}/doclist.lst . + +%files -n python3-hopcroftkarp -f filelist.lst +%dir %{python3_sitelib}/* + +%files help -f doclist.lst +%{_docdir}/* + +%changelog +* Fri May 05 2023 Python_Bot <Python_Bot@openeuler.org> - 1.2.5-1 +- Package Spec generated @@ -0,0 +1 @@ +f5a8c38fd16363715c687bc462c12510 hopcroftkarp-1.2.5.tar.gz |