COIN-OR::LEMON - Graph Library

Ticket #168: res3.txt

File res3.txt, 20.6 KB (added by Poroszkai Daniel, 13 years ago)

Benchmark results

Line 
1lshw:
2     *-cpu
3          description: CPU
4          product: Intel(R) Core(TM)2 Duo CPU     T5550  @ 1.83GHz
5          vendor: Intel Corp.
6          physical id: 4
7          bus info: cpu@0
8          version: Intel(R) Core(TM)2 Duo CPU T5550 @ 1.83GHz
9          serial: PSN12345678901234567
10          slot: Socket 478
11          size: 1826MHz
12          capacity: 1837MHz
13          width: 64 bits
14          clock: 167MHz
15          capabilities: fpu fpu_exception wp vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx x86-64 constant_tsc arch_perfmon pebs bts rep_good nopl aperfmperf pni dtes64 monitor ds_cpl est tm2 ssse3 cx16 xtpr pdcm lahf_lm cpufreq
16        *-cache:0
17             description: L1 cache
18             physical id: 5
19             slot: L1-Cache
20             size: 64KiB
21             capacity: 64KiB
22             capabilities: internal write-back instruction
23        *-cache:1
24             description: L2 cache
25             physical id: 6
26             slot: L2-Cache
27             size: 2MiB
28             capacity: 2MiB
29             capabilities: internal write-back unified
30     *-memory
31          description: System Memory
32          physical id: 19
33          slot: System board or motherboard
34          size: 2GiB
35        *-bank:0
36             description: DIMM DDR Synchronous
37             product: PartNum0
38             vendor: Manufacturer0
39             physical id: 0
40             serial: SerNum0
41             slot: DIMM0
42             size: 1GiB
43             width: 64 bits
44        *-bank:1
45             description: DIMM DDR Synchronous
46             product: PartNum1
47             vendor: Manufacturer1
48             physical id: 1
49             serial: SerNum1
50             slot: DIMM1
51             size: 1GiB
52             width: 64 bits
53
54
55------------------------------------------------------------------
56./unweighted-bp-gen -red 10000 -blue 10000 -density 20000 -seed 1
57
58Benchmarking in unweighted case, using a bipartite graph
59with 10000 red, 10000 blue nodes, and 20000 edges.
60--------------------------------------------------------
61Algorithm used               Time
62Hopcroft-Karp            0.00439501
63General matching         0.00581098
64Push-relabel matching    0.0270121
65Pull-relabel matching    0.0195651
66Preflow                  0.0704179
67------------------------------------------------------------------
68./unweighted-bp-gen -red 10000 -blue 10000 -density 20000 -seed 10
69
70Benchmarking in unweighted case, using a bipartite graph
71with 10000 red, 10000 blue nodes, and 20000 edges.
72--------------------------------------------------------
73Algorithm used               Time
74Hopcroft-Karp            0.007617
75General matching         0.00865293
76Push-relabel matching    0.0281398
77Pull-relabel matching    0.022635
78Preflow                  0.084631
79------------------------------------------------------------------
80./unweighted-bp-gen -red 10000 -blue 10000 -density 200000 -seed 1
81
82Benchmarking in unweighted case, using a bipartite graph
83with 10000 red, 10000 blue nodes, and 200000 edges.
84--------------------------------------------------------
85Algorithm used               Time
86Hopcroft-Karp            0.0196722
87General matching         0.0496941
88Push-relabel matching    0.0402629
89Pull-relabel matching    0.023067
90Preflow                  0.084374
91------------------------------------------------------------------
92./unweighted-bp-gen -red 10000 -blue 10000 -density 200000 -seed 10
93
94Benchmarking in unweighted case, using a bipartite graph
95with 10000 red, 10000 blue nodes, and 200000 edges.
96--------------------------------------------------------
97Algorithm used               Time
98Hopcroft-Karp            0.0173001
99General matching         0.039665
100Push-relabel matching    0.0378501
101Pull-relabel matching    0.0209558
102Preflow                  0.083463
103------------------------------------------------------------------
104./unweighted-bp-gen -red 10000 -blue 10000 -density 5000000 -seed 1
105
106Benchmarking in unweighted case, using a bipartite graph
107with 10000 red, 10000 blue nodes, and 5000000 edges.
108--------------------------------------------------------
109Algorithm used               Time
110Hopcroft-Karp            0.140268
111General matching         0.757882
112Push-relabel matching    1.03231
113Pull-relabel matching    0.191497
114Preflow                  2.43836
115------------------------------------------------------------------
116./unweighted-bp-gen -red 10000 -blue 10000 -density 5000000 -seed 10
117
118Benchmarking in unweighted case, using a bipartite graph
119with 10000 red, 10000 blue nodes, and 5000000 edges.
120--------------------------------------------------------
121Algorithm used               Time
122Hopcroft-Karp            0.14244
123General matching         0.748836
124Push-relabel matching    1.01037
125Pull-relabel matching    0.177195
126Preflow                  2.43532
127------------------------------------------------------------------
128./unweighted-bp-gen -red 10000 -blue 50000 -density 100000 -seed 1
129
130Benchmarking in unweighted case, using a bipartite graph
131with 10000 red, 50000 blue nodes, and 100000 edges.
132--------------------------------------------------------
133Algorithm used               Time
134Hopcroft-Karp            0.00485301
135General matching         0.0332901
136Push-relabel matching    0.034101
137Pull-relabel matching    1.61998
138Preflow                  0.0291169
139------------------------------------------------------------------
140./unweighted-bp-gen -red 10000 -blue 50000 -density 100000 -seed 10
141
142Benchmarking in unweighted case, using a bipartite graph
143with 10000 red, 50000 blue nodes, and 100000 edges.
144--------------------------------------------------------
145Algorithm used               Time
146Hopcroft-Karp            0.00491309
147General matching         0.0323601
148Push-relabel matching    0.0341032
149Pull-relabel matching    1.64628
150Preflow                  0.02914
151------------------------------------------------------------------
152./unweighted-bp-gen -red 50000 -blue 10000 -density 100000 -seed 1
153
154Benchmarking in unweighted case, using a bipartite graph
155with 50000 red, 10000 blue nodes, and 100000 edges.
156--------------------------------------------------------
157Algorithm used               Time
158Hopcroft-Karp            0.0106671
159General matching         0.0234542
160Push-relabel matching    0.598726
161Pull-relabel matching    0.0256259
162Preflow                  0.441146
163------------------------------------------------------------------
164./unweighted-bp-gen -red 50000 -blue 10000 -density 100000 -seed 10
165
166Benchmarking in unweighted case, using a bipartite graph
167with 50000 red, 10000 blue nodes, and 100000 edges.
168--------------------------------------------------------
169Algorithm used               Time
170Hopcroft-Karp            0.00621796
171General matching         0.02387
172Push-relabel matching    0.013314
173Pull-relabel matching    0.0249431
174Preflow                  0.420767
175------------------------------------------------------------------
176./unweighted-bp-gen -red 50000 -blue 50000 -density 100000 -seed 1
177
178Benchmarking in unweighted case, using a bipartite graph
179with 50000 red, 50000 blue nodes, and 100000 edges.
180--------------------------------------------------------
181Algorithm used               Time
182Hopcroft-Karp            0.0959971
183General matching         0.0536282
184Push-relabel matching    0.564037
185Pull-relabel matching    0.409038
186Preflow                  2.87165
187------------------------------------------------------------------
188./unweighted-bp-gen -red 50000 -blue 50000 -density 100000 -seed 10
189
190Benchmarking in unweighted case, using a bipartite graph
191with 50000 red, 50000 blue nodes, and 100000 edges.
192--------------------------------------------------------
193Algorithm used               Time
194Hopcroft-Karp            0.0964329
195General matching         0.0539811
196Push-relabel matching    0.577723
197Pull-relabel matching    0.498138
198Preflow                  2.9425
199------------------------------------------------------------------
200./unweighted-bp-gen -red 50000 -blue 50000 -density 500000 -seed 1
201
202Benchmarking in unweighted case, using a bipartite graph
203with 50000 red, 50000 blue nodes, and 500000 edges.
204--------------------------------------------------------
205Algorithm used               Time
206Hopcroft-Karp            0.300473
207General matching         0.659012
208Push-relabel matching    0.285235
209Pull-relabel matching    0.716639
210Preflow                  0.659159
211------------------------------------------------------------------
212./unweighted-bp-gen -red 50000 -blue 50000 -density 500000 -seed 10
213
214Benchmarking in unweighted case, using a bipartite graph
215with 50000 red, 50000 blue nodes, and 500000 edges.
216--------------------------------------------------------
217Algorithm used               Time
218Hopcroft-Karp            0.290675
219General matching         0.799577
220Push-relabel matching    0.278713
221Pull-relabel matching    0.673765
222Preflow                  0.644327
223------------------------------------------------------------------
224./unweighted-bp-gen -red 100000 -blue 100000 -density 100000 -seed 1
225
226Benchmarking in unweighted case, using a bipartite graph
227with 100000 red, 100000 blue nodes, and 100000 edges.
228--------------------------------------------------------
229Algorithm used               Time
230Hopcroft-Karp            0.078588
231General matching         0.0866389
232Push-relabel matching    1.07703
233Pull-relabel matching    1.05606
234Preflow                  13.6679
235------------------------------------------------------------------
236./unweighted-bp-gen -red 100000 -blue 100000 -density 100000 -seed 10
237
238Benchmarking in unweighted case, using a bipartite graph
239with 100000 red, 100000 blue nodes, and 100000 edges.
240--------------------------------------------------------
241Algorithm used               Time
242Hopcroft-Karp            0.0867798
243General matching         0.0857451
244Push-relabel matching    1.14464
245Pull-relabel matching    1.1683
246Preflow                  15.3508
247------------------------------------------------------------------
248./unweighted-bp-gen -red 100000 -blue 100000 -density 500000 -seed 1
249
250Benchmarking in unweighted case, using a bipartite graph
251with 100000 red, 100000 blue nodes, and 500000 edges.
252--------------------------------------------------------
253Algorithm used               Time
254Hopcroft-Karp            0.738178
255General matching         6.79053
256Push-relabel matching    0.629064
257Pull-relabel matching    2.00591
258Preflow                  1.51949
259------------------------------------------------------------------
260./unweighted-bp-gen -red 100000 -blue 100000 -density 500000 -seed 10
261
262Benchmarking in unweighted case, using a bipartite graph
263with 100000 red, 100000 blue nodes, and 500000 edges.
264--------------------------------------------------------
265Algorithm used               Time
266Hopcroft-Karp            1.06521
267General matching         3.61031
268Push-relabel matching    1.86594
269Pull-relabel matching    0.550163
270Preflow                  3.38694
271------------------------------------------------------------------
272./unweighted-bp-gen -red 100000 -blue 100000 -density 1000000 -seed 1
273
274Benchmarking in unweighted case, using a bipartite graph
275with 100000 red, 100000 blue nodes, and 1000000 edges.
276--------------------------------------------------------
277Algorithm used               Time
278Hopcroft-Karp            0.946682
279General matching         1.92071
280Push-relabel matching    1.72593
281Pull-relabel matching    0.501604
282Preflow                  3.05918
283------------------------------------------------------------------
284./unweighted-bp-gen -red 100000 -blue 100000 -density 1000000 -seed 10
285
286Benchmarking in unweighted case, using a bipartite graph
287with 100000 red, 100000 blue nodes, and 1000000 edges.
288--------------------------------------------------------
289Algorithm used               Time
290Hopcroft-Karp            0.816804
291General matching         2.1141
292Push-relabel matching    0.720706
293Pull-relabel matching    0.558198
294Preflow                  1.57464
295------------------------------------------------------------------
296./unweighted-bp-gen -red 200000 -blue 100000 -density 1000000 -seed 1
297
298Benchmarking in unweighted case, using a bipartite graph
299with 200000 red, 100000 blue nodes, and 1000000 edges.
300--------------------------------------------------------
301Algorithm used               Time
302Hopcroft-Karp            0.301091
303General matching         0.394658
304Push-relabel matching    51.6478
305Pull-relabel matching    0.429368
306Preflow                  5.04168
307------------------------------------------------------------------
308./unweighted-bp-gen -red 200000 -blue 100000 -density 1000000 -seed 10
309
310Benchmarking in unweighted case, using a bipartite graph
311with 200000 red, 100000 blue nodes, and 1000000 edges.
312--------------------------------------------------------
313Algorithm used               Time
314Hopcroft-Karp            0.436297
315General matching         0.398948
316Push-relabel matching    51.8427
317Pull-relabel matching    0.433397
318Preflow                  5.25675
319------------------------------------------------------------------
320./unweighted-bp-gen -red 100000 -blue 200000 -density 1000000 -seed 1
321
322Benchmarking in unweighted case, using a bipartite graph
323with 100000 red, 200000 blue nodes, and 1000000 edges.
324--------------------------------------------------------
325Algorithm used               Time
326Hopcroft-Karp            0.10732
327General matching         6.44808
328Push-relabel matching    0.620226
329Pull-relabel matching    202.475
330Preflow                  0.631016
331------------------------------------------------------------------
332./unweighted-bp-gen -red 100000 -blue 200000 -density 1000000 -seed 10
333
334Benchmarking in unweighted case, using a bipartite graph
335with 100000 red, 200000 blue nodes, and 1000000 edges.
336--------------------------------------------------------
337Algorithm used               Time
338Hopcroft-Karp            0.106734
339General matching         7.05392
340Push-relabel matching    0.619569
341Pull-relabel matching    203.459
342Preflow                  0.631564
343------------------------------------------------------------------
344./unweighted-bp-gen -red 100000 -blue 100000 -density 5000000 -seed 1
345
346Benchmarking in unweighted case, using a bipartite graph
347with 100000 red, 100000 blue nodes, and 5000000 edges.
348--------------------------------------------------------
349Algorithm used               Time
350Hopcroft-Karp            0.92472
351General matching         2.1869
352Push-relabel matching    2.08447
353Pull-relabel matching    0.823065
354Preflow                  3.89623
355------------------------------------------------------------------
356./unweighted-bp-gen -red 100000 -blue 100000 -density 5000000 -seed 10
357
358Benchmarking in unweighted case, using a bipartite graph
359with 100000 red, 100000 blue nodes, and 5000000 edges.
360--------------------------------------------------------
361Algorithm used               Time
362Hopcroft-Karp            0.768868
363General matching         2.34836
364Push-relabel matching    2.04811
365Pull-relabel matching    0.856978
366Preflow                  3.81936
367------------------------------------------------------------------
368./unweighted-bp-gen -red 100000 -blue 100000 -density 10000000 -seed 1
369
370Benchmarking in unweighted case, using a bipartite graph
371with 100000 red, 100000 blue nodes, and 10000000 edges.
372--------------------------------------------------------
373Algorithm used               Time
374Hopcroft-Karp            1.35792
375General matching         3.95055
376Push-relabel matching    4.13391
377Pull-relabel matching    1.34968
378Preflow                  7.61363
379------------------------------------------------------------------
380./unweighted-bp-gen -red 100000 -blue 100000 -density 10000000 -seed 10
381
382Benchmarking in unweighted case, using a bipartite graph
383with 100000 red, 100000 blue nodes, and 10000000 edges.
384--------------------------------------------------------
385Algorithm used               Time
386Hopcroft-Karp            1.40444
387General matching         3.9244
388Push-relabel matching    4.12933
389Pull-relabel matching    1.37161
390Preflow                  7.68012
391------------------------------------------------------------------
392./unweighted-bp-gen -red 10000 -blue 10000 -density 20000000 -seed 1
393
394Benchmarking in unweighted case, using a bipartite graph
395with 10000 red, 10000 blue nodes, and 20000000 edges.
396--------------------------------------------------------
397Algorithm used               Time
398Hopcroft-Karp            0.622058
399General matching         3.5884
400Push-relabel matching    4.81846
401Pull-relabel matching    0.722273
402Preflow                  15.3129
403------------------------------------------------------------------
404./unweighted-bp-gen -red 10000 -blue 10000 -density 20000000 -seed 10
405
406Benchmarking in unweighted case, using a bipartite graph
407with 10000 red, 10000 blue nodes, and 20000000 edges.
408--------------------------------------------------------
409Algorithm used               Time
410Hopcroft-Karp            0.559423
411General matching         3.56505
412Push-relabel matching    4.82065
413Pull-relabel matching    0.719321
414Preflow                  14.6463
415------------------------------------------------------------------
416./unweighted-bp-gen -red 50000 -blue 50000 -density 10000000 -seed 1
417
418Benchmarking in unweighted case, using a bipartite graph
419with 50000 red, 50000 blue nodes, and 10000000 edges.
420--------------------------------------------------------
421Algorithm used               Time
422Hopcroft-Karp            0.865783
423General matching         2.86391
424Push-relabel matching    3.51891
425Pull-relabel matching    0.884747
426Preflow                  6.92598
427------------------------------------------------------------------
428./unweighted-bp-gen -red 50000 -blue 50000 -density 10000000 -seed 10
429
430Benchmarking in unweighted case, using a bipartite graph
431with 50000 red, 50000 blue nodes, and 10000000 edges.
432--------------------------------------------------------
433Algorithm used               Time
434Hopcroft-Karp            0.864196
435General matching         2.91178
436Push-relabel matching    3.55595
437Pull-relabel matching    0.880587
438Preflow                  6.95554
439------------------------------------------------------------------
440./unweighted-bp-gen -red 50000 -blue 50000 -density 30000000 -seed 1
441
442Benchmarking in unweighted case, using a bipartite graph
443with 50000 red, 50000 blue nodes, and 30000000 edges.
444--------------------------------------------------------
445Algorithm used               Time
446Hopcroft-Karp            2.3675
447General matching         8.98925
448Push-relabel matching    11.8477
449Pull-relabel matching    2.6124
450Preflow                  27.0935
451------------------------------------------------------------------
452./unweighted-bp-gen -red 50000 -blue 50000 -density 30000000 -seed 10
453
454Benchmarking in unweighted case, using a bipartite graph
455with 50000 red, 50000 blue nodes, and 30000000 edges.
456--------------------------------------------------------
457Algorithm used               Time
458Hopcroft-Karp            2.5767
459General matching         9.19034
460Push-relabel matching    12.1031
461Pull-relabel matching    2.72674
462Preflow                  27.1568
463------------------------------------------------------------------
464./unweighted-bp-gen -red 50000 -blue 100000 -density 30000000 -seed 1
465
466Benchmarking in unweighted case, using a bipartite graph
467with 50000 red, 100000 blue nodes, and 30000000 edges.
468--------------------------------------------------------
469Algorithm used               Time
470Hopcroft-Karp            3.72626
471General matching         13.7599
472Push-relabel matching    13.8212
473Pull-relabel matching    3.76943
474Preflow                  14.8385
475------------------------------------------------------------------
476./unweighted-bp-gen -red 50000 -blue 100000 -density 30000000 -seed 10
477
478Benchmarking in unweighted case, using a bipartite graph
479with 50000 red, 100000 blue nodes, and 30000000 edges.
480--------------------------------------------------------
481Algorithm used               Time
482Hopcroft-Karp            3.77606
483General matching         14.0525
484Push-relabel matching    14.0126
485Pull-relabel matching    3.80314
486Preflow                  14.8287
487------------------------------------------------------------------
488./unweighted-bp-gen -red 100000 -blue 50000 -density 30000000 -seed 1
489
490Benchmarking in unweighted case, using a bipartite graph
491with 100000 red, 50000 blue nodes, and 30000000 edges.
492--------------------------------------------------------
493Algorithm used               Time
494Hopcroft-Karp            1.56758
495General matching         4.84758
496Push-relabel matching    0.927193
497Pull-relabel matching    1.58256
498Preflow                  41.4949
499------------------------------------------------------------------
500./unweighted-bp-gen -red 100000 -blue 50000 -density 30000000 -seed 10
501
502Benchmarking in unweighted case, using a bipartite graph
503with 100000 red, 50000 blue nodes, and 30000000 edges.
504--------------------------------------------------------
505Algorithm used               Time
506Hopcroft-Karp            1.59166
507General matching         4.75917
508Push-relabel matching    0.924
509Pull-relabel matching    1.58148
510Preflow                  41.5419