COIN-OR::LEMON - Graph Library

Ticket #168: results.txt

File results.txt, 15.5 KB (added by Poroszkai Daniel, 9 years ago)

Benchmark results

Line 
1-------------------------------------------------------------------
2./unweighted-bp-gen -red 1000 -blue 1000 -density 2000 -seed 1
3
4Benchmarking in unweighted case, using a bipartite graph
5with 1000 red, 1000 blue nodes, and 2000 edges.
6--------------------------------------------------------
7Algorithm used       Matching size       Time
8Hopcroft-Karp            784         0.000851154
9General matching         784         0.000729084
10Preflow                  784         0.00254011
11-------------------------------------------------------------------
12./unweighted-bp-gen -red 1000 -blue 1000 -density 2000 -seed 10
13
14Benchmarking in unweighted case, using a bipartite graph
15with 1000 red, 1000 blue nodes, and 2000 edges.
16--------------------------------------------------------
17Algorithm used       Matching size       Time
18Hopcroft-Karp            784         0.00121498
19General matching         784         0.000818014
20Preflow                  784         0.00229502
21-------------------------------------------------------------------
22./unweighted-bp-gen -red 1000 -blue 1000 -density 20000 -seed 1
23
24Benchmarking in unweighted case, using a bipartite graph
25with 1000 red, 1000 blue nodes, and 20000 edges.
26--------------------------------------------------------
27Algorithm used       Matching size       Time
28Hopcroft-Karp            1000         0.000758171
29General matching         1000         0.00160909
30Preflow                  1000         0.00195909
31-------------------------------------------------------------------
32./unweighted-bp-gen -red 1000 -blue 1000 -density 20000 -seed 10
33
34Benchmarking in unweighted case, using a bipartite graph
35with 1000 red, 1000 blue nodes, and 20000 edges.
36--------------------------------------------------------
37Algorithm used       Matching size       Time
38Hopcroft-Karp            1000         0.000808001
39General matching         1000         0.00161505
40Preflow                  1000         0.00198388
41-------------------------------------------------------------------
42./unweighted-bp-gen -red 1000 -blue 5000 -density 10000 -seed 1
43
44Benchmarking in unweighted case, using a bipartite graph
45with 1000 red, 5000 blue nodes, and 10000 edges.
46--------------------------------------------------------
47Algorithm used       Matching size       Time
48Hopcroft-Karp            1000         0.000248909
49General matching         1000         0.00155497
50Preflow                  1000         0.00121379
51-------------------------------------------------------------------
52./unweighted-bp-gen -red 1000 -blue 5000 -density 10000 -seed 10
53
54Benchmarking in unweighted case, using a bipartite graph
55with 1000 red, 5000 blue nodes, and 10000 edges.
56--------------------------------------------------------
57Algorithm used       Matching size       Time
58Hopcroft-Karp            1000         0.000241995
59General matching         1000         0.00155282
60Preflow                  1000         0.00119209
61-------------------------------------------------------------------
62./unweighted-bp-gen -red 5000 -blue 1000 -density 10000 -seed 1
63
64Benchmarking in unweighted case, using a bipartite graph
65with 5000 red, 1000 blue nodes, and 10000 edges.
66--------------------------------------------------------
67Algorithm used       Matching size       Time
68Hopcroft-Karp            1000         0.000847101
69General matching         1000         0.00183296
70Preflow                  1000         0.00581908
71-------------------------------------------------------------------
72./unweighted-bp-gen -red 5000 -blue 1000 -density 10000 -seed 10
73
74Benchmarking in unweighted case, using a bipartite graph
75with 5000 red, 1000 blue nodes, and 10000 edges.
76--------------------------------------------------------
77Algorithm used       Matching size       Time
78Hopcroft-Karp            1000         0.000849009
79General matching         1000         0.00151014
80Preflow                  1000         0.00520992
81-------------------------------------------------------------------
82./unweighted-bp-gen -red 5000 -blue 5000 -density 10000 -seed 1
83
84Benchmarking in unweighted case, using a bipartite graph
85with 5000 red, 5000 blue nodes, and 10000 edges.
86--------------------------------------------------------
87Algorithm used       Matching size       Time
88Hopcroft-Karp            3948         0.00666904
89General matching         3948         0.00219297
90Preflow                  3948         0.0174839
91-------------------------------------------------------------------
92./unweighted-bp-gen -red 5000 -blue 5000 -density 10000 -seed 10
93
94Benchmarking in unweighted case, using a bipartite graph
95with 5000 red, 5000 blue nodes, and 10000 edges.
96--------------------------------------------------------
97Algorithm used       Matching size       Time
98Hopcroft-Karp            3941         0.00654697
99General matching         3941         0.0024631
100Preflow                  3941         0.0184231
101-------------------------------------------------------------------
102./unweighted-bp-gen -red 5000 -blue 5000 -density 50000 -seed 1
103
104Benchmarking in unweighted case, using a bipartite graph
105with 5000 red, 5000 blue nodes, and 50000 edges.
106--------------------------------------------------------
107Algorithm used       Matching size       Time
108Hopcroft-Karp            5000         0.00720811
109General matching         5000         0.0129621
110Preflow                  5000         0.011977
111-------------------------------------------------------------------
112./unweighted-bp-gen -red 5000 -blue 5000 -density 50000 -seed 10
113
114Benchmarking in unweighted case, using a bipartite graph
115with 5000 red, 5000 blue nodes, and 50000 edges.
116--------------------------------------------------------
117Algorithm used       Matching size       Time
118Hopcroft-Karp            4999         0.00665498
119General matching         4999         0.0124369
120Preflow                  4999         0.011713
121-------------------------------------------------------------------
122./unweighted-bp-gen -red 10000 -blue 10000 -density 50000 -seed 1
123
124Benchmarking in unweighted case, using a bipartite graph
125with 10000 red, 10000 blue nodes, and 50000 edges.
126--------------------------------------------------------
127Algorithm used       Matching size       Time
128Hopcroft-Karp            9934         0.030973
129General matching         9934         0.0354669
130Preflow                  9934         0.0726831
131-------------------------------------------------------------------
132./unweighted-bp-gen -red 10000 -blue 10000 -density 50000 -seed 10
133
134Benchmarking in unweighted case, using a bipartite graph
135with 10000 red, 10000 blue nodes, and 50000 edges.
136--------------------------------------------------------
137Algorithm used       Matching size       Time
138Hopcroft-Karp            9920         0.025604
139General matching         9920         0.0658369
140Preflow                  9920         0.026011
141-------------------------------------------------------------------
142./unweighted-bp-gen -red 10000 -blue 10000 -density 100000 -seed 1
143
144Benchmarking in unweighted case, using a bipartite graph
145with 10000 red, 10000 blue nodes, and 100000 edges.
146--------------------------------------------------------
147Algorithm used       Matching size       Time
148Hopcroft-Karp            10000         0.0252571
149General matching         10000         0.031213
150Preflow                  10000         0.0406179
151-------------------------------------------------------------------
152./unweighted-bp-gen -red 10000 -blue 10000 -density 100000 -seed 10
153
154Benchmarking in unweighted case, using a bipartite graph
155with 10000 red, 10000 blue nodes, and 100000 edges.
156--------------------------------------------------------
157Algorithm used       Matching size       Time
158Hopcroft-Karp            9999         0.0199139
159General matching         9999         0.0558238
160Preflow                  9999         0.038918
161
162
163-----------------------------------------------------------------------------------------------
164./weighted-bp-gen -red 1000 -blue 1000 -density 2000 -minweight 10 -maxweight 1000 -seed 1
165
166Benchmarking on weighted bipartite matching problem on a graph
167with 1000 red, 1000 blue nodes and 2000 edges
168--------------------------------------------------------
169Algorithm used       Maximum weight       Time
170Bipartite matching       472576         0.000921011
171General matching         472576         0.00331783
172-----------------------------------------------------------------------------------------------
173./weighted-bp-gen -red 1000 -blue 1000 -density 2000 -minweight 10 -maxweight 1000 -seed 10
174
175Benchmarking on weighted bipartite matching problem on a graph
176with 1000 red, 1000 blue nodes and 2000 edges
177--------------------------------------------------------
178Algorithm used       Maximum weight       Time
179Bipartite matching       490695         0.000863791
180General matching         490695         0.003304
181-----------------------------------------------------------------------------------------------
182./weighted-bp-gen -red 1000 -blue 1000 -density 20000 -minweight 10 -maxweight 1000 -seed 1
183
184Benchmarking on weighted bipartite matching problem on a graph
185with 1000 red, 1000 blue nodes and 20000 edges
186--------------------------------------------------------
187Algorithm used       Maximum weight       Time
188Bipartite matching       914524         0.0185199
189General matching         914524         0.0252349
190-----------------------------------------------------------------------------------------------
191./weighted-bp-gen -red 1000 -blue 1000 -density 20000 -minweight 10 -maxweight 1000 -seed 10
192
193Benchmarking on weighted bipartite matching problem on a graph
194with 1000 red, 1000 blue nodes and 20000 edges
195--------------------------------------------------------
196Algorithm used       Maximum weight       Time
197Bipartite matching       919943         0.0174081
198General matching         919943         0.020571
199-----------------------------------------------------------------------------------------------
200./weighted-bp-gen -red 1000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
201
202Benchmarking on weighted bipartite matching problem on a graph
203with 1000 red, 5000 blue nodes and 10000 edges
204--------------------------------------------------------
205Algorithm used       Maximum weight       Time
206Bipartite matching       890836         0.000678062
207General matching         890836         0.0125511
208-----------------------------------------------------------------------------------------------
209./weighted-bp-gen -red 1000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
210
211Benchmarking on weighted bipartite matching problem on a graph
212with 1000 red, 5000 blue nodes and 10000 edges
213--------------------------------------------------------
214Algorithm used       Maximum weight       Time
215Bipartite matching       897412         0.000607967
216General matching         897412         0.012522
217-----------------------------------------------------------------------------------------------
218./weighted-bp-gen -red 5000 -blue 1000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
219
220Benchmarking on weighted bipartite matching problem on a graph
221with 5000 red, 1000 blue nodes and 10000 edges
222--------------------------------------------------------
223Algorithm used       Maximum weight       Time
224Bipartite matching       895469         0.00667906
225General matching         895469         0.0124631
226-----------------------------------------------------------------------------------------------
227./weighted-bp-gen -red 5000 -blue 1000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
228
229Benchmarking on weighted bipartite matching problem on a graph
230with 5000 red, 1000 blue nodes and 10000 edges
231--------------------------------------------------------
232Algorithm used       Maximum weight       Time
233Bipartite matching       893040         0.00669312
234General matching         893040         0.0129621
235-----------------------------------------------------------------------------------------------
236./weighted-bp-gen -red 5000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
237
238Benchmarking on weighted bipartite matching problem on a graph
239with 5000 red, 5000 blue nodes and 10000 edges
240--------------------------------------------------------
241Algorithm used       Maximum weight       Time
242Bipartite matching       2383509         0.0071671
243General matching         2383509         0.02267
244-----------------------------------------------------------------------------------------------
245./weighted-bp-gen -red 5000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
246
247Benchmarking on weighted bipartite matching problem on a graph
248with 5000 red, 5000 blue nodes and 10000 edges
249--------------------------------------------------------
250Algorithm used       Maximum weight       Time
251Bipartite matching       2394615         0.00722313
252General matching         2394615         0.022392
253-----------------------------------------------------------------------------------------------
254./weighted-bp-gen -red 5000 -blue 5000 -density 50000 -minweight 10 -maxweight 1000 -seed 1
255
256Benchmarking on weighted bipartite matching problem on a graph
257with 5000 red, 5000 blue nodes and 50000 edges
258--------------------------------------------------------
259Algorithm used       Maximum weight       Time
260Bipartite matching       4205491         0.0941398
261General matching         4205491         0.112351
262-----------------------------------------------------------------------------------------------
263./weighted-bp-gen -red 5000 -blue 5000 -density 50000 -minweight 10 -maxweight 1000 -seed 10
264
265Benchmarking on weighted bipartite matching problem on a graph
266with 5000 red, 5000 blue nodes and 50000 edges
267--------------------------------------------------------
268Algorithm used       Maximum weight       Time
269Bipartite matching       4197432         0.101236
270General matching         4197432         0.12102
271-----------------------------------------------------------------------------------------------
272./weighted-bp-gen -red 10000 -blue 10000 -density 50000 -minweight 10 -maxweight 1000 -seed 1
273
274Benchmarking on weighted bipartite matching problem on a graph
275with 10000 red, 10000 blue nodes and 50000 edges
276--------------------------------------------------------
277Algorithm used       Maximum weight       Time
278Bipartite matching       7029959         0.0417528
279General matching         7029959         0.130245
280-----------------------------------------------------------------------------------------------
281./weighted-bp-gen -red 10000 -blue 10000 -density 50000 -minweight 10 -maxweight 1000 -seed 10
282
283Benchmarking on weighted bipartite matching problem on a graph
284with 10000 red, 10000 blue nodes and 50000 edges
285--------------------------------------------------------
286Algorithm used       Maximum weight       Time
287Bipartite matching       7056257         0.0420868
288General matching         7056257         0.129265
289-----------------------------------------------------------------------------------------------
290./weighted-bp-gen -red 10000 -blue 10000 -density 100000 -minweight 10 -maxweight 1000 -seed 1
291
292Benchmarking on weighted bipartite matching problem on a graph
293with 10000 red, 10000 blue nodes and 100000 edges
294--------------------------------------------------------
295Algorithm used       Maximum weight       Time
296Bipartite matching       8396190         0.277562
297General matching         8396190         0.37123
298-----------------------------------------------------------------------------------------------
299./weighted-bp-gen -red 10000 -blue 10000 -density 100000 -minweight 10 -maxweight 1000 -seed 10
300
301Benchmarking on weighted bipartite matching problem on a graph
302with 10000 red, 10000 blue nodes and 100000 edges
303--------------------------------------------------------
304Algorithm used       Maximum weight       Time
305Bipartite matching       8393092         0.254069
306General matching         8393092         0.370639