| 1 | lshw: |
|---|
| 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 | |
|---|
| 58 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 59 | with 10000 red, 10000 blue nodes, and 20000 edges. |
|---|
| 60 | -------------------------------------------------------- |
|---|
| 61 | Algorithm used Time |
|---|
| 62 | Hopcroft-Karp 0.00439501 |
|---|
| 63 | General matching 0.00581098 |
|---|
| 64 | Push-relabel matching 0.0270121 |
|---|
| 65 | Pull-relabel matching 0.0195651 |
|---|
| 66 | Preflow 0.0704179 |
|---|
| 67 | ------------------------------------------------------------------ |
|---|
| 68 | ./unweighted-bp-gen -red 10000 -blue 10000 -density 20000 -seed 10 |
|---|
| 69 | |
|---|
| 70 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 71 | with 10000 red, 10000 blue nodes, and 20000 edges. |
|---|
| 72 | -------------------------------------------------------- |
|---|
| 73 | Algorithm used Time |
|---|
| 74 | Hopcroft-Karp 0.007617 |
|---|
| 75 | General matching 0.00865293 |
|---|
| 76 | Push-relabel matching 0.0281398 |
|---|
| 77 | Pull-relabel matching 0.022635 |
|---|
| 78 | Preflow 0.084631 |
|---|
| 79 | ------------------------------------------------------------------ |
|---|
| 80 | ./unweighted-bp-gen -red 10000 -blue 10000 -density 200000 -seed 1 |
|---|
| 81 | |
|---|
| 82 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 83 | with 10000 red, 10000 blue nodes, and 200000 edges. |
|---|
| 84 | -------------------------------------------------------- |
|---|
| 85 | Algorithm used Time |
|---|
| 86 | Hopcroft-Karp 0.0196722 |
|---|
| 87 | General matching 0.0496941 |
|---|
| 88 | Push-relabel matching 0.0402629 |
|---|
| 89 | Pull-relabel matching 0.023067 |
|---|
| 90 | Preflow 0.084374 |
|---|
| 91 | ------------------------------------------------------------------ |
|---|
| 92 | ./unweighted-bp-gen -red 10000 -blue 10000 -density 200000 -seed 10 |
|---|
| 93 | |
|---|
| 94 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 95 | with 10000 red, 10000 blue nodes, and 200000 edges. |
|---|
| 96 | -------------------------------------------------------- |
|---|
| 97 | Algorithm used Time |
|---|
| 98 | Hopcroft-Karp 0.0173001 |
|---|
| 99 | General matching 0.039665 |
|---|
| 100 | Push-relabel matching 0.0378501 |
|---|
| 101 | Pull-relabel matching 0.0209558 |
|---|
| 102 | Preflow 0.083463 |
|---|
| 103 | ------------------------------------------------------------------ |
|---|
| 104 | ./unweighted-bp-gen -red 10000 -blue 10000 -density 5000000 -seed 1 |
|---|
| 105 | |
|---|
| 106 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 107 | with 10000 red, 10000 blue nodes, and 5000000 edges. |
|---|
| 108 | -------------------------------------------------------- |
|---|
| 109 | Algorithm used Time |
|---|
| 110 | Hopcroft-Karp 0.140268 |
|---|
| 111 | General matching 0.757882 |
|---|
| 112 | Push-relabel matching 1.03231 |
|---|
| 113 | Pull-relabel matching 0.191497 |
|---|
| 114 | Preflow 2.43836 |
|---|
| 115 | ------------------------------------------------------------------ |
|---|
| 116 | ./unweighted-bp-gen -red 10000 -blue 10000 -density 5000000 -seed 10 |
|---|
| 117 | |
|---|
| 118 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 119 | with 10000 red, 10000 blue nodes, and 5000000 edges. |
|---|
| 120 | -------------------------------------------------------- |
|---|
| 121 | Algorithm used Time |
|---|
| 122 | Hopcroft-Karp 0.14244 |
|---|
| 123 | General matching 0.748836 |
|---|
| 124 | Push-relabel matching 1.01037 |
|---|
| 125 | Pull-relabel matching 0.177195 |
|---|
| 126 | Preflow 2.43532 |
|---|
| 127 | ------------------------------------------------------------------ |
|---|
| 128 | ./unweighted-bp-gen -red 10000 -blue 50000 -density 100000 -seed 1 |
|---|
| 129 | |
|---|
| 130 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 131 | with 10000 red, 50000 blue nodes, and 100000 edges. |
|---|
| 132 | -------------------------------------------------------- |
|---|
| 133 | Algorithm used Time |
|---|
| 134 | Hopcroft-Karp 0.00485301 |
|---|
| 135 | General matching 0.0332901 |
|---|
| 136 | Push-relabel matching 0.034101 |
|---|
| 137 | Pull-relabel matching 1.61998 |
|---|
| 138 | Preflow 0.0291169 |
|---|
| 139 | ------------------------------------------------------------------ |
|---|
| 140 | ./unweighted-bp-gen -red 10000 -blue 50000 -density 100000 -seed 10 |
|---|
| 141 | |
|---|
| 142 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 143 | with 10000 red, 50000 blue nodes, and 100000 edges. |
|---|
| 144 | -------------------------------------------------------- |
|---|
| 145 | Algorithm used Time |
|---|
| 146 | Hopcroft-Karp 0.00491309 |
|---|
| 147 | General matching 0.0323601 |
|---|
| 148 | Push-relabel matching 0.0341032 |
|---|
| 149 | Pull-relabel matching 1.64628 |
|---|
| 150 | Preflow 0.02914 |
|---|
| 151 | ------------------------------------------------------------------ |
|---|
| 152 | ./unweighted-bp-gen -red 50000 -blue 10000 -density 100000 -seed 1 |
|---|
| 153 | |
|---|
| 154 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 155 | with 50000 red, 10000 blue nodes, and 100000 edges. |
|---|
| 156 | -------------------------------------------------------- |
|---|
| 157 | Algorithm used Time |
|---|
| 158 | Hopcroft-Karp 0.0106671 |
|---|
| 159 | General matching 0.0234542 |
|---|
| 160 | Push-relabel matching 0.598726 |
|---|
| 161 | Pull-relabel matching 0.0256259 |
|---|
| 162 | Preflow 0.441146 |
|---|
| 163 | ------------------------------------------------------------------ |
|---|
| 164 | ./unweighted-bp-gen -red 50000 -blue 10000 -density 100000 -seed 10 |
|---|
| 165 | |
|---|
| 166 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 167 | with 50000 red, 10000 blue nodes, and 100000 edges. |
|---|
| 168 | -------------------------------------------------------- |
|---|
| 169 | Algorithm used Time |
|---|
| 170 | Hopcroft-Karp 0.00621796 |
|---|
| 171 | General matching 0.02387 |
|---|
| 172 | Push-relabel matching 0.013314 |
|---|
| 173 | Pull-relabel matching 0.0249431 |
|---|
| 174 | Preflow 0.420767 |
|---|
| 175 | ------------------------------------------------------------------ |
|---|
| 176 | ./unweighted-bp-gen -red 50000 -blue 50000 -density 100000 -seed 1 |
|---|
| 177 | |
|---|
| 178 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 179 | with 50000 red, 50000 blue nodes, and 100000 edges. |
|---|
| 180 | -------------------------------------------------------- |
|---|
| 181 | Algorithm used Time |
|---|
| 182 | Hopcroft-Karp 0.0959971 |
|---|
| 183 | General matching 0.0536282 |
|---|
| 184 | Push-relabel matching 0.564037 |
|---|
| 185 | Pull-relabel matching 0.409038 |
|---|
| 186 | Preflow 2.87165 |
|---|
| 187 | ------------------------------------------------------------------ |
|---|
| 188 | ./unweighted-bp-gen -red 50000 -blue 50000 -density 100000 -seed 10 |
|---|
| 189 | |
|---|
| 190 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 191 | with 50000 red, 50000 blue nodes, and 100000 edges. |
|---|
| 192 | -------------------------------------------------------- |
|---|
| 193 | Algorithm used Time |
|---|
| 194 | Hopcroft-Karp 0.0964329 |
|---|
| 195 | General matching 0.0539811 |
|---|
| 196 | Push-relabel matching 0.577723 |
|---|
| 197 | Pull-relabel matching 0.498138 |
|---|
| 198 | Preflow 2.9425 |
|---|
| 199 | ------------------------------------------------------------------ |
|---|
| 200 | ./unweighted-bp-gen -red 50000 -blue 50000 -density 500000 -seed 1 |
|---|
| 201 | |
|---|
| 202 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 203 | with 50000 red, 50000 blue nodes, and 500000 edges. |
|---|
| 204 | -------------------------------------------------------- |
|---|
| 205 | Algorithm used Time |
|---|
| 206 | Hopcroft-Karp 0.300473 |
|---|
| 207 | General matching 0.659012 |
|---|
| 208 | Push-relabel matching 0.285235 |
|---|
| 209 | Pull-relabel matching 0.716639 |
|---|
| 210 | Preflow 0.659159 |
|---|
| 211 | ------------------------------------------------------------------ |
|---|
| 212 | ./unweighted-bp-gen -red 50000 -blue 50000 -density 500000 -seed 10 |
|---|
| 213 | |
|---|
| 214 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 215 | with 50000 red, 50000 blue nodes, and 500000 edges. |
|---|
| 216 | -------------------------------------------------------- |
|---|
| 217 | Algorithm used Time |
|---|
| 218 | Hopcroft-Karp 0.290675 |
|---|
| 219 | General matching 0.799577 |
|---|
| 220 | Push-relabel matching 0.278713 |
|---|
| 221 | Pull-relabel matching 0.673765 |
|---|
| 222 | Preflow 0.644327 |
|---|
| 223 | ------------------------------------------------------------------ |
|---|
| 224 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 100000 -seed 1 |
|---|
| 225 | |
|---|
| 226 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 227 | with 100000 red, 100000 blue nodes, and 100000 edges. |
|---|
| 228 | -------------------------------------------------------- |
|---|
| 229 | Algorithm used Time |
|---|
| 230 | Hopcroft-Karp 0.078588 |
|---|
| 231 | General matching 0.0866389 |
|---|
| 232 | Push-relabel matching 1.07703 |
|---|
| 233 | Pull-relabel matching 1.05606 |
|---|
| 234 | Preflow 13.6679 |
|---|
| 235 | ------------------------------------------------------------------ |
|---|
| 236 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 100000 -seed 10 |
|---|
| 237 | |
|---|
| 238 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 239 | with 100000 red, 100000 blue nodes, and 100000 edges. |
|---|
| 240 | -------------------------------------------------------- |
|---|
| 241 | Algorithm used Time |
|---|
| 242 | Hopcroft-Karp 0.0867798 |
|---|
| 243 | General matching 0.0857451 |
|---|
| 244 | Push-relabel matching 1.14464 |
|---|
| 245 | Pull-relabel matching 1.1683 |
|---|
| 246 | Preflow 15.3508 |
|---|
| 247 | ------------------------------------------------------------------ |
|---|
| 248 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 500000 -seed 1 |
|---|
| 249 | |
|---|
| 250 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 251 | with 100000 red, 100000 blue nodes, and 500000 edges. |
|---|
| 252 | -------------------------------------------------------- |
|---|
| 253 | Algorithm used Time |
|---|
| 254 | Hopcroft-Karp 0.738178 |
|---|
| 255 | General matching 6.79053 |
|---|
| 256 | Push-relabel matching 0.629064 |
|---|
| 257 | Pull-relabel matching 2.00591 |
|---|
| 258 | Preflow 1.51949 |
|---|
| 259 | ------------------------------------------------------------------ |
|---|
| 260 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 500000 -seed 10 |
|---|
| 261 | |
|---|
| 262 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 263 | with 100000 red, 100000 blue nodes, and 500000 edges. |
|---|
| 264 | -------------------------------------------------------- |
|---|
| 265 | Algorithm used Time |
|---|
| 266 | Hopcroft-Karp 1.06521 |
|---|
| 267 | General matching 3.61031 |
|---|
| 268 | Push-relabel matching 1.86594 |
|---|
| 269 | Pull-relabel matching 0.550163 |
|---|
| 270 | Preflow 3.38694 |
|---|
| 271 | ------------------------------------------------------------------ |
|---|
| 272 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 1000000 -seed 1 |
|---|
| 273 | |
|---|
| 274 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 275 | with 100000 red, 100000 blue nodes, and 1000000 edges. |
|---|
| 276 | -------------------------------------------------------- |
|---|
| 277 | Algorithm used Time |
|---|
| 278 | Hopcroft-Karp 0.946682 |
|---|
| 279 | General matching 1.92071 |
|---|
| 280 | Push-relabel matching 1.72593 |
|---|
| 281 | Pull-relabel matching 0.501604 |
|---|
| 282 | Preflow 3.05918 |
|---|
| 283 | ------------------------------------------------------------------ |
|---|
| 284 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 1000000 -seed 10 |
|---|
| 285 | |
|---|
| 286 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 287 | with 100000 red, 100000 blue nodes, and 1000000 edges. |
|---|
| 288 | -------------------------------------------------------- |
|---|
| 289 | Algorithm used Time |
|---|
| 290 | Hopcroft-Karp 0.816804 |
|---|
| 291 | General matching 2.1141 |
|---|
| 292 | Push-relabel matching 0.720706 |
|---|
| 293 | Pull-relabel matching 0.558198 |
|---|
| 294 | Preflow 1.57464 |
|---|
| 295 | ------------------------------------------------------------------ |
|---|
| 296 | ./unweighted-bp-gen -red 200000 -blue 100000 -density 1000000 -seed 1 |
|---|
| 297 | |
|---|
| 298 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 299 | with 200000 red, 100000 blue nodes, and 1000000 edges. |
|---|
| 300 | -------------------------------------------------------- |
|---|
| 301 | Algorithm used Time |
|---|
| 302 | Hopcroft-Karp 0.301091 |
|---|
| 303 | General matching 0.394658 |
|---|
| 304 | Push-relabel matching 51.6478 |
|---|
| 305 | Pull-relabel matching 0.429368 |
|---|
| 306 | Preflow 5.04168 |
|---|
| 307 | ------------------------------------------------------------------ |
|---|
| 308 | ./unweighted-bp-gen -red 200000 -blue 100000 -density 1000000 -seed 10 |
|---|
| 309 | |
|---|
| 310 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 311 | with 200000 red, 100000 blue nodes, and 1000000 edges. |
|---|
| 312 | -------------------------------------------------------- |
|---|
| 313 | Algorithm used Time |
|---|
| 314 | Hopcroft-Karp 0.436297 |
|---|
| 315 | General matching 0.398948 |
|---|
| 316 | Push-relabel matching 51.8427 |
|---|
| 317 | Pull-relabel matching 0.433397 |
|---|
| 318 | Preflow 5.25675 |
|---|
| 319 | ------------------------------------------------------------------ |
|---|
| 320 | ./unweighted-bp-gen -red 100000 -blue 200000 -density 1000000 -seed 1 |
|---|
| 321 | |
|---|
| 322 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 323 | with 100000 red, 200000 blue nodes, and 1000000 edges. |
|---|
| 324 | -------------------------------------------------------- |
|---|
| 325 | Algorithm used Time |
|---|
| 326 | Hopcroft-Karp 0.10732 |
|---|
| 327 | General matching 6.44808 |
|---|
| 328 | Push-relabel matching 0.620226 |
|---|
| 329 | Pull-relabel matching 202.475 |
|---|
| 330 | Preflow 0.631016 |
|---|
| 331 | ------------------------------------------------------------------ |
|---|
| 332 | ./unweighted-bp-gen -red 100000 -blue 200000 -density 1000000 -seed 10 |
|---|
| 333 | |
|---|
| 334 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 335 | with 100000 red, 200000 blue nodes, and 1000000 edges. |
|---|
| 336 | -------------------------------------------------------- |
|---|
| 337 | Algorithm used Time |
|---|
| 338 | Hopcroft-Karp 0.106734 |
|---|
| 339 | General matching 7.05392 |
|---|
| 340 | Push-relabel matching 0.619569 |
|---|
| 341 | Pull-relabel matching 203.459 |
|---|
| 342 | Preflow 0.631564 |
|---|
| 343 | ------------------------------------------------------------------ |
|---|
| 344 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 5000000 -seed 1 |
|---|
| 345 | |
|---|
| 346 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 347 | with 100000 red, 100000 blue nodes, and 5000000 edges. |
|---|
| 348 | -------------------------------------------------------- |
|---|
| 349 | Algorithm used Time |
|---|
| 350 | Hopcroft-Karp 0.92472 |
|---|
| 351 | General matching 2.1869 |
|---|
| 352 | Push-relabel matching 2.08447 |
|---|
| 353 | Pull-relabel matching 0.823065 |
|---|
| 354 | Preflow 3.89623 |
|---|
| 355 | ------------------------------------------------------------------ |
|---|
| 356 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 5000000 -seed 10 |
|---|
| 357 | |
|---|
| 358 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 359 | with 100000 red, 100000 blue nodes, and 5000000 edges. |
|---|
| 360 | -------------------------------------------------------- |
|---|
| 361 | Algorithm used Time |
|---|
| 362 | Hopcroft-Karp 0.768868 |
|---|
| 363 | General matching 2.34836 |
|---|
| 364 | Push-relabel matching 2.04811 |
|---|
| 365 | Pull-relabel matching 0.856978 |
|---|
| 366 | Preflow 3.81936 |
|---|
| 367 | ------------------------------------------------------------------ |
|---|
| 368 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 10000000 -seed 1 |
|---|
| 369 | |
|---|
| 370 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 371 | with 100000 red, 100000 blue nodes, and 10000000 edges. |
|---|
| 372 | -------------------------------------------------------- |
|---|
| 373 | Algorithm used Time |
|---|
| 374 | Hopcroft-Karp 1.35792 |
|---|
| 375 | General matching 3.95055 |
|---|
| 376 | Push-relabel matching 4.13391 |
|---|
| 377 | Pull-relabel matching 1.34968 |
|---|
| 378 | Preflow 7.61363 |
|---|
| 379 | ------------------------------------------------------------------ |
|---|
| 380 | ./unweighted-bp-gen -red 100000 -blue 100000 -density 10000000 -seed 10 |
|---|
| 381 | |
|---|
| 382 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 383 | with 100000 red, 100000 blue nodes, and 10000000 edges. |
|---|
| 384 | -------------------------------------------------------- |
|---|
| 385 | Algorithm used Time |
|---|
| 386 | Hopcroft-Karp 1.40444 |
|---|
| 387 | General matching 3.9244 |
|---|
| 388 | Push-relabel matching 4.12933 |
|---|
| 389 | Pull-relabel matching 1.37161 |
|---|
| 390 | Preflow 7.68012 |
|---|
| 391 | ------------------------------------------------------------------ |
|---|
| 392 | ./unweighted-bp-gen -red 10000 -blue 10000 -density 20000000 -seed 1 |
|---|
| 393 | |
|---|
| 394 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 395 | with 10000 red, 10000 blue nodes, and 20000000 edges. |
|---|
| 396 | -------------------------------------------------------- |
|---|
| 397 | Algorithm used Time |
|---|
| 398 | Hopcroft-Karp 0.622058 |
|---|
| 399 | General matching 3.5884 |
|---|
| 400 | Push-relabel matching 4.81846 |
|---|
| 401 | Pull-relabel matching 0.722273 |
|---|
| 402 | Preflow 15.3129 |
|---|
| 403 | ------------------------------------------------------------------ |
|---|
| 404 | ./unweighted-bp-gen -red 10000 -blue 10000 -density 20000000 -seed 10 |
|---|
| 405 | |
|---|
| 406 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 407 | with 10000 red, 10000 blue nodes, and 20000000 edges. |
|---|
| 408 | -------------------------------------------------------- |
|---|
| 409 | Algorithm used Time |
|---|
| 410 | Hopcroft-Karp 0.559423 |
|---|
| 411 | General matching 3.56505 |
|---|
| 412 | Push-relabel matching 4.82065 |
|---|
| 413 | Pull-relabel matching 0.719321 |
|---|
| 414 | Preflow 14.6463 |
|---|
| 415 | ------------------------------------------------------------------ |
|---|
| 416 | ./unweighted-bp-gen -red 50000 -blue 50000 -density 10000000 -seed 1 |
|---|
| 417 | |
|---|
| 418 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 419 | with 50000 red, 50000 blue nodes, and 10000000 edges. |
|---|
| 420 | -------------------------------------------------------- |
|---|
| 421 | Algorithm used Time |
|---|
| 422 | Hopcroft-Karp 0.865783 |
|---|
| 423 | General matching 2.86391 |
|---|
| 424 | Push-relabel matching 3.51891 |
|---|
| 425 | Pull-relabel matching 0.884747 |
|---|
| 426 | Preflow 6.92598 |
|---|
| 427 | ------------------------------------------------------------------ |
|---|
| 428 | ./unweighted-bp-gen -red 50000 -blue 50000 -density 10000000 -seed 10 |
|---|
| 429 | |
|---|
| 430 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 431 | with 50000 red, 50000 blue nodes, and 10000000 edges. |
|---|
| 432 | -------------------------------------------------------- |
|---|
| 433 | Algorithm used Time |
|---|
| 434 | Hopcroft-Karp 0.864196 |
|---|
| 435 | General matching 2.91178 |
|---|
| 436 | Push-relabel matching 3.55595 |
|---|
| 437 | Pull-relabel matching 0.880587 |
|---|
| 438 | Preflow 6.95554 |
|---|
| 439 | ------------------------------------------------------------------ |
|---|
| 440 | ./unweighted-bp-gen -red 50000 -blue 50000 -density 30000000 -seed 1 |
|---|
| 441 | |
|---|
| 442 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 443 | with 50000 red, 50000 blue nodes, and 30000000 edges. |
|---|
| 444 | -------------------------------------------------------- |
|---|
| 445 | Algorithm used Time |
|---|
| 446 | Hopcroft-Karp 2.3675 |
|---|
| 447 | General matching 8.98925 |
|---|
| 448 | Push-relabel matching 11.8477 |
|---|
| 449 | Pull-relabel matching 2.6124 |
|---|
| 450 | Preflow 27.0935 |
|---|
| 451 | ------------------------------------------------------------------ |
|---|
| 452 | ./unweighted-bp-gen -red 50000 -blue 50000 -density 30000000 -seed 10 |
|---|
| 453 | |
|---|
| 454 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 455 | with 50000 red, 50000 blue nodes, and 30000000 edges. |
|---|
| 456 | -------------------------------------------------------- |
|---|
| 457 | Algorithm used Time |
|---|
| 458 | Hopcroft-Karp 2.5767 |
|---|
| 459 | General matching 9.19034 |
|---|
| 460 | Push-relabel matching 12.1031 |
|---|
| 461 | Pull-relabel matching 2.72674 |
|---|
| 462 | Preflow 27.1568 |
|---|
| 463 | ------------------------------------------------------------------ |
|---|
| 464 | ./unweighted-bp-gen -red 50000 -blue 100000 -density 30000000 -seed 1 |
|---|
| 465 | |
|---|
| 466 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 467 | with 50000 red, 100000 blue nodes, and 30000000 edges. |
|---|
| 468 | -------------------------------------------------------- |
|---|
| 469 | Algorithm used Time |
|---|
| 470 | Hopcroft-Karp 3.72626 |
|---|
| 471 | General matching 13.7599 |
|---|
| 472 | Push-relabel matching 13.8212 |
|---|
| 473 | Pull-relabel matching 3.76943 |
|---|
| 474 | Preflow 14.8385 |
|---|
| 475 | ------------------------------------------------------------------ |
|---|
| 476 | ./unweighted-bp-gen -red 50000 -blue 100000 -density 30000000 -seed 10 |
|---|
| 477 | |
|---|
| 478 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 479 | with 50000 red, 100000 blue nodes, and 30000000 edges. |
|---|
| 480 | -------------------------------------------------------- |
|---|
| 481 | Algorithm used Time |
|---|
| 482 | Hopcroft-Karp 3.77606 |
|---|
| 483 | General matching 14.0525 |
|---|
| 484 | Push-relabel matching 14.0126 |
|---|
| 485 | Pull-relabel matching 3.80314 |
|---|
| 486 | Preflow 14.8287 |
|---|
| 487 | ------------------------------------------------------------------ |
|---|
| 488 | ./unweighted-bp-gen -red 100000 -blue 50000 -density 30000000 -seed 1 |
|---|
| 489 | |
|---|
| 490 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 491 | with 100000 red, 50000 blue nodes, and 30000000 edges. |
|---|
| 492 | -------------------------------------------------------- |
|---|
| 493 | Algorithm used Time |
|---|
| 494 | Hopcroft-Karp 1.56758 |
|---|
| 495 | General matching 4.84758 |
|---|
| 496 | Push-relabel matching 0.927193 |
|---|
| 497 | Pull-relabel matching 1.58256 |
|---|
| 498 | Preflow 41.4949 |
|---|
| 499 | ------------------------------------------------------------------ |
|---|
| 500 | ./unweighted-bp-gen -red 100000 -blue 50000 -density 30000000 -seed 10 |
|---|
| 501 | |
|---|
| 502 | Benchmarking in unweighted case, using a bipartite graph |
|---|
| 503 | with 100000 red, 50000 blue nodes, and 30000000 edges. |
|---|
| 504 | -------------------------------------------------------- |
|---|
| 505 | Algorithm used Time |
|---|
| 506 | Hopcroft-Karp 1.59166 |
|---|
| 507 | General matching 4.75917 |
|---|
| 508 | Push-relabel matching 0.924 |
|---|
| 509 | Pull-relabel matching 1.58148 |
|---|
| 510 | Preflow 41.5419 |
|---|
