1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
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
|
