------------------------------------------------------------------- ./unweighted-bp-gen -red 1000 -blue 1000 -density 2000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 1000 red, 1000 blue nodes, and 2000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 784 0.000851154 General matching 784 0.000729084 Preflow 784 0.00254011 ------------------------------------------------------------------- ./unweighted-bp-gen -red 1000 -blue 1000 -density 2000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 1000 red, 1000 blue nodes, and 2000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 784 0.00121498 General matching 784 0.000818014 Preflow 784 0.00229502 ------------------------------------------------------------------- ./unweighted-bp-gen -red 1000 -blue 1000 -density 20000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 1000 red, 1000 blue nodes, and 20000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 1000 0.000758171 General matching 1000 0.00160909 Preflow 1000 0.00195909 ------------------------------------------------------------------- ./unweighted-bp-gen -red 1000 -blue 1000 -density 20000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 1000 red, 1000 blue nodes, and 20000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 1000 0.000808001 General matching 1000 0.00161505 Preflow 1000 0.00198388 ------------------------------------------------------------------- ./unweighted-bp-gen -red 1000 -blue 5000 -density 10000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 1000 red, 5000 blue nodes, and 10000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 1000 0.000248909 General matching 1000 0.00155497 Preflow 1000 0.00121379 ------------------------------------------------------------------- ./unweighted-bp-gen -red 1000 -blue 5000 -density 10000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 1000 red, 5000 blue nodes, and 10000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 1000 0.000241995 General matching 1000 0.00155282 Preflow 1000 0.00119209 ------------------------------------------------------------------- ./unweighted-bp-gen -red 5000 -blue 1000 -density 10000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 5000 red, 1000 blue nodes, and 10000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 1000 0.000847101 General matching 1000 0.00183296 Preflow 1000 0.00581908 ------------------------------------------------------------------- ./unweighted-bp-gen -red 5000 -blue 1000 -density 10000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 5000 red, 1000 blue nodes, and 10000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 1000 0.000849009 General matching 1000 0.00151014 Preflow 1000 0.00520992 ------------------------------------------------------------------- ./unweighted-bp-gen -red 5000 -blue 5000 -density 10000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 5000 red, 5000 blue nodes, and 10000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 3948 0.00666904 General matching 3948 0.00219297 Preflow 3948 0.0174839 ------------------------------------------------------------------- ./unweighted-bp-gen -red 5000 -blue 5000 -density 10000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 5000 red, 5000 blue nodes, and 10000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 3941 0.00654697 General matching 3941 0.0024631 Preflow 3941 0.0184231 ------------------------------------------------------------------- ./unweighted-bp-gen -red 5000 -blue 5000 -density 50000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 5000 red, 5000 blue nodes, and 50000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 5000 0.00720811 General matching 5000 0.0129621 Preflow 5000 0.011977 ------------------------------------------------------------------- ./unweighted-bp-gen -red 5000 -blue 5000 -density 50000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 5000 red, 5000 blue nodes, and 50000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 4999 0.00665498 General matching 4999 0.0124369 Preflow 4999 0.011713 ------------------------------------------------------------------- ./unweighted-bp-gen -red 10000 -blue 10000 -density 50000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 50000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 9934 0.030973 General matching 9934 0.0354669 Preflow 9934 0.0726831 ------------------------------------------------------------------- ./unweighted-bp-gen -red 10000 -blue 10000 -density 50000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 50000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 9920 0.025604 General matching 9920 0.0658369 Preflow 9920 0.026011 ------------------------------------------------------------------- ./unweighted-bp-gen -red 10000 -blue 10000 -density 100000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 10000 0.0252571 General matching 10000 0.031213 Preflow 10000 0.0406179 ------------------------------------------------------------------- ./unweighted-bp-gen -red 10000 -blue 10000 -density 100000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Matching size Time Hopcroft-Karp 9999 0.0199139 General matching 9999 0.0558238 Preflow 9999 0.038918 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 1000 -blue 1000 -density 2000 -minweight 10 -maxweight 1000 -seed 1 Benchmarking on weighted bipartite matching problem on a graph with 1000 red, 1000 blue nodes and 2000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 472576 0.000921011 General matching 472576 0.00331783 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 1000 -blue 1000 -density 2000 -minweight 10 -maxweight 1000 -seed 10 Benchmarking on weighted bipartite matching problem on a graph with 1000 red, 1000 blue nodes and 2000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 490695 0.000863791 General matching 490695 0.003304 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 1000 -blue 1000 -density 20000 -minweight 10 -maxweight 1000 -seed 1 Benchmarking on weighted bipartite matching problem on a graph with 1000 red, 1000 blue nodes and 20000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 914524 0.0185199 General matching 914524 0.0252349 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 1000 -blue 1000 -density 20000 -minweight 10 -maxweight 1000 -seed 10 Benchmarking on weighted bipartite matching problem on a graph with 1000 red, 1000 blue nodes and 20000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 919943 0.0174081 General matching 919943 0.020571 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 1000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 1 Benchmarking on weighted bipartite matching problem on a graph with 1000 red, 5000 blue nodes and 10000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 890836 0.000678062 General matching 890836 0.0125511 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 1000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 10 Benchmarking on weighted bipartite matching problem on a graph with 1000 red, 5000 blue nodes and 10000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 897412 0.000607967 General matching 897412 0.012522 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 5000 -blue 1000 -density 10000 -minweight 10 -maxweight 1000 -seed 1 Benchmarking on weighted bipartite matching problem on a graph with 5000 red, 1000 blue nodes and 10000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 895469 0.00667906 General matching 895469 0.0124631 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 5000 -blue 1000 -density 10000 -minweight 10 -maxweight 1000 -seed 10 Benchmarking on weighted bipartite matching problem on a graph with 5000 red, 1000 blue nodes and 10000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 893040 0.00669312 General matching 893040 0.0129621 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 5000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 1 Benchmarking on weighted bipartite matching problem on a graph with 5000 red, 5000 blue nodes and 10000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 2383509 0.0071671 General matching 2383509 0.02267 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 5000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 10 Benchmarking on weighted bipartite matching problem on a graph with 5000 red, 5000 blue nodes and 10000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 2394615 0.00722313 General matching 2394615 0.022392 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 5000 -blue 5000 -density 50000 -minweight 10 -maxweight 1000 -seed 1 Benchmarking on weighted bipartite matching problem on a graph with 5000 red, 5000 blue nodes and 50000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 4205491 0.0941398 General matching 4205491 0.112351 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 5000 -blue 5000 -density 50000 -minweight 10 -maxweight 1000 -seed 10 Benchmarking on weighted bipartite matching problem on a graph with 5000 red, 5000 blue nodes and 50000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 4197432 0.101236 General matching 4197432 0.12102 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 10000 -blue 10000 -density 50000 -minweight 10 -maxweight 1000 -seed 1 Benchmarking on weighted bipartite matching problem on a graph with 10000 red, 10000 blue nodes and 50000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 7029959 0.0417528 General matching 7029959 0.130245 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 10000 -blue 10000 -density 50000 -minweight 10 -maxweight 1000 -seed 10 Benchmarking on weighted bipartite matching problem on a graph with 10000 red, 10000 blue nodes and 50000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 7056257 0.0420868 General matching 7056257 0.129265 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 10000 -blue 10000 -density 100000 -minweight 10 -maxweight 1000 -seed 1 Benchmarking on weighted bipartite matching problem on a graph with 10000 red, 10000 blue nodes and 100000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 8396190 0.277562 General matching 8396190 0.37123 ----------------------------------------------------------------------------------------------- ./weighted-bp-gen -red 10000 -blue 10000 -density 100000 -minweight 10 -maxweight 1000 -seed 10 Benchmarking on weighted bipartite matching problem on a graph with 10000 red, 10000 blue nodes and 100000 edges -------------------------------------------------------- Algorithm used Maximum weight Time Bipartite matching 8393092 0.254069 General matching 8393092 0.370639