COIN-OR::LEMON - Graph Library

Ticket #168: res2.txt

File res2.txt, 17.8 KB (added by Poroszkai Daniel, 9 years ago)

Benchmark result (extended with min cost flow)

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.000739098
9General matching         784         0.000475883
10Preflow                  784         0.00199008
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.00112009
19General matching         784         0.000510931
20Preflow                  784         0.00170302
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.000752211
29General matching         1000         0.00172114
30Preflow                  1000         0.00203085
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.00080514
39General matching         1000         0.00175405
40Preflow                  1000         0.00201392
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.000276089
49General matching         1000         0.00143814
50Preflow                  1000         0.00099206
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.000265121
59General matching         1000         0.00148916
60Preflow                  1000         0.000981092
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.000825882
69General matching         1000         0.001441
70Preflow                  1000         0.00522804
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.000828981
79General matching         1000         0.00143099
80Preflow                  1000         0.00503492
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.00673199
89General matching         3948         0.00218701
90Preflow                  3948         0.0176799
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.00656819
99General matching         3941         0.00237894
100Preflow                  3941         0.018575
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.00694299
109General matching         5000         0.01403
110Preflow                  5000         0.0148079
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.0068872
119General matching         4999         0.0141132
120Preflow                  4999         0.014971
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.0315061
129General matching         9934         0.0357502
130Preflow                  9934         0.114448
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.0244858
139General matching         9920         0.0659032
140Preflow                  9920         0.0363429
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.026413
149General matching         10000         0.032402
150Preflow                  10000         0.0555508
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.0207119
159General matching         9999         0.0564229
160Preflow                  9999         0.054014
161-----------------------------------------------------------------------------------------------
162./weighted-bp-gen -red 1000 -blue 1000 -density 2000 -minweight 10 -maxweight 1000 -seed 1
163
164Benchmarking on weighted bipartite matching problem on a graph
165with 1000 red, 1000 blue nodes and 2000 edges
166--------------------------------------------------------
167Algorithm used       Maximum weight       Time
168Bipartite matching       472576         0.139076
169General matching         472576         0.00326991
170Capacity scaling         472576         0.0879331
171Cost scaling             472576         0.0118301
172Network simplex          472576         0.00567198
173-----------------------------------------------------------------------------------------------
174./weighted-bp-gen -red 1000 -blue 1000 -density 2000 -minweight 10 -maxweight 1000 -seed 10
175
176Benchmarking on weighted bipartite matching problem on a graph
177with 1000 red, 1000 blue nodes and 2000 edges
178--------------------------------------------------------
179Algorithm used       Maximum weight       Time
180Bipartite matching       490695         0.136649
181General matching         490695         0.00336504
182Capacity scaling         490695         0.088218
183Cost scaling             490695         0.0123198
184Network simplex          490695         0.00531006
185-----------------------------------------------------------------------------------------------
186./weighted-bp-gen -red 1000 -blue 1000 -density 20000 -minweight 10 -maxweight 1000 -seed 1
187
188Benchmarking on weighted bipartite matching problem on a graph
189with 1000 red, 1000 blue nodes and 20000 edges
190--------------------------------------------------------
191Algorithm used       Maximum weight       Time
192Bipartite matching       914524         0.197766
193General matching         914524         0.027005
194Capacity scaling         914524         0.100053
195Cost scaling             914524         0.0668819
196Network simplex          914524         0.0146241
197-----------------------------------------------------------------------------------------------
198./weighted-bp-gen -red 1000 -blue 1000 -density 20000 -minweight 10 -maxweight 1000 -seed 10
199
200Benchmarking on weighted bipartite matching problem on a graph
201with 1000 red, 1000 blue nodes and 20000 edges
202--------------------------------------------------------
203Algorithm used       Maximum weight       Time
204Bipartite matching       919943         0.181663
205General matching         919943         0.022315
206Capacity scaling         919943         0.0937889
207Cost scaling             919943         0.074887
208Network simplex          919943         0.0133469
209-----------------------------------------------------------------------------------------------
210./weighted-bp-gen -red 1000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
211
212Benchmarking on weighted bipartite matching problem on a graph
213with 1000 red, 5000 blue nodes and 10000 edges
214--------------------------------------------------------
215Algorithm used       Maximum weight       Time
216Bipartite matching       890836         0.505637
217General matching         890836         0.0145609
218Capacity scaling         890836         1.70609
219Cost scaling             890836         0.0605259
220Network simplex          890836         0.00779986
221-----------------------------------------------------------------------------------------------
222./weighted-bp-gen -red 1000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
223
224Benchmarking on weighted bipartite matching problem on a graph
225with 1000 red, 5000 blue nodes and 10000 edges
226--------------------------------------------------------
227Algorithm used       Maximum weight       Time
228Bipartite matching       897412         0.502237
229General matching         897412         0.0146611
230Capacity scaling         897412         1.71704
231Cost scaling             897412         0.0664949
232Network simplex          897412         0.00781202
233-----------------------------------------------------------------------------------------------
234./weighted-bp-gen -red 5000 -blue 1000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
235
236Benchmarking on weighted bipartite matching problem on a graph
237with 5000 red, 1000 blue nodes and 10000 edges
238--------------------------------------------------------
239Algorithm used       Maximum weight       Time
240Bipartite matching       895469         0.202065
241General matching         895469         0.014302
242Capacity scaling         895469         0.134837
243Cost scaling             895469         0.0462389
244Network simplex          895469         0.00812817
245-----------------------------------------------------------------------------------------------
246./weighted-bp-gen -red 5000 -blue 1000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
247
248Benchmarking on weighted bipartite matching problem on a graph
249with 5000 red, 1000 blue nodes and 10000 edges
250--------------------------------------------------------
251Algorithm used       Maximum weight       Time
252Bipartite matching       893040         0.192539
253General matching         893040         0.014688
254Capacity scaling         893040         0.142115
255Cost scaling             893040         0.0465879
256Network simplex          893040         0.00778508
257-----------------------------------------------------------------------------------------------
258./weighted-bp-gen -red 5000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
259
260Benchmarking on weighted bipartite matching problem on a graph
261with 5000 red, 5000 blue nodes and 10000 edges
262--------------------------------------------------------
263Algorithm used       Maximum weight       Time
264Bipartite matching       2383509         1.52556
265General matching         2383509         0.0276449
266Capacity scaling         2383509         2.19282
267Cost scaling             2383509         0.129686
268Network simplex          2383509         0.22806
269-----------------------------------------------------------------------------------------------
270./weighted-bp-gen -red 5000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
271
272Benchmarking on weighted bipartite matching problem on a graph
273with 5000 red, 5000 blue nodes and 10000 edges
274--------------------------------------------------------
275Algorithm used       Maximum weight       Time
276Bipartite matching       2394615         1.48321
277General matching         2394615         0.0271301
278Capacity scaling         2394615         2.19058
279Cost scaling             2394615         0.152851
280Network simplex          2394615         0.263314
281-----------------------------------------------------------------------------------------------
282./weighted-bp-gen -red 5000 -blue 5000 -density 50000 -minweight 10 -maxweight 1000 -seed 1
283
284Benchmarking on weighted bipartite matching problem on a graph
285with 5000 red, 5000 blue nodes and 50000 edges
286--------------------------------------------------------
287Algorithm used       Maximum weight       Time
288Bipartite matching       4205491         2.20795
289General matching         4205491         0.128231
290Capacity scaling         4205491         1.58734
291Cost scaling             4205491         0.489221
292Network simplex          4205491         0.091192
293-----------------------------------------------------------------------------------------------
294./weighted-bp-gen -red 5000 -blue 5000 -density 50000 -minweight 10 -maxweight 1000 -seed 10
295
296Benchmarking on weighted bipartite matching problem on a graph
297with 5000 red, 5000 blue nodes and 50000 edges
298--------------------------------------------------------
299Algorithm used       Maximum weight       Time
300Bipartite matching       4197432         2.46947
301General matching         4197432         0.140808
302Capacity scaling         4197432         1.59073
303Cost scaling             4197432         0.682716
304Network simplex          4197432         0.0957692
305-----------------------------------------------------------------------------------------------
306./weighted-bp-gen -red 10000 -blue 10000 -density 50000 -minweight 10 -maxweight 1000 -seed 1
307
308Benchmarking on weighted bipartite matching problem on a graph
309with 10000 red, 10000 blue nodes and 50000 edges
310--------------------------------------------------------
311Algorithm used       Maximum weight       Time
312Bipartite matching       7029959         6.61569
313General matching         7029959         0.170723
314Capacity scaling         7029959         10.8181
315Cost scaling             7029959         0.831383
316Network simplex          7029959         0.240637
317-----------------------------------------------------------------------------------------------
318./weighted-bp-gen -red 10000 -blue 10000 -density 50000 -minweight 10 -maxweight 1000 -seed 10
319
320Benchmarking on weighted bipartite matching problem on a graph
321with 10000 red, 10000 blue nodes and 50000 edges
322--------------------------------------------------------
323Algorithm used       Maximum weight       Time
324Bipartite matching       7056257         6.26456
325General matching         7056257         0.167678
326Capacity scaling         7056257         10.9781
327Cost scaling             7056257         0.889265
328Network simplex          7056257         0.25909
329-----------------------------------------------------------------------------------------------
330./weighted-bp-gen -red 10000 -blue 10000 -density 100000 -minweight 10 -maxweight 1000 -seed 1
331
332Benchmarking on weighted bipartite matching problem on a graph
333with 10000 red, 10000 blue nodes and 100000 edges
334--------------------------------------------------------
335Algorithm used       Maximum weight       Time
336Bipartite matching       8396190         8.96618
337General matching         8396190         0.441941
338Capacity scaling         8396190         6.48904
339Cost scaling             8396190         1.83858
340Network simplex          8396190         0.317024
341-----------------------------------------------------------------------------------------------
342./weighted-bp-gen -red 10000 -blue 10000 -density 100000 -minweight 10 -maxweight 1000 -seed 10
343
344Benchmarking on weighted bipartite matching problem on a graph
345with 10000 red, 10000 blue nodes and 100000 edges
346--------------------------------------------------------
347Algorithm used       Maximum weight       Time
348Bipartite matching       8393092         9.69202
349General matching         8393092         0.444463
350Capacity scaling         8393092         6.55828
351Cost scaling             8393092         1.99005
352Network simplex          8393092         0.313474