------------------------------------------------------------------ ./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.000739098 General matching 784 0.000475883 Preflow 784 0.00199008 ------------------------------------------------------------------ ./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.00112009 General matching 784 0.000510931 Preflow 784 0.00170302 ------------------------------------------------------------------ ./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.000752211 General matching 1000 0.00172114 Preflow 1000 0.00203085 ------------------------------------------------------------------ ./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.00080514 General matching 1000 0.00175405 Preflow 1000 0.00201392 ------------------------------------------------------------------ ./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.000276089 General matching 1000 0.00143814 Preflow 1000 0.00099206 ------------------------------------------------------------------ ./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.000265121 General matching 1000 0.00148916 Preflow 1000 0.000981092 ------------------------------------------------------------------ ./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.000825882 General matching 1000 0.001441 Preflow 1000 0.00522804 ------------------------------------------------------------------ ./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.000828981 General matching 1000 0.00143099 Preflow 1000 0.00503492 ------------------------------------------------------------------ ./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.00673199 General matching 3948 0.00218701 Preflow 3948 0.0176799 ------------------------------------------------------------------ ./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.00656819 General matching 3941 0.00237894 Preflow 3941 0.018575 ------------------------------------------------------------------ ./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.00694299 General matching 5000 0.01403 Preflow 5000 0.0148079 ------------------------------------------------------------------ ./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.0068872 General matching 4999 0.0141132 Preflow 4999 0.014971 ------------------------------------------------------------------ ./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.0315061 General matching 9934 0.0357502 Preflow 9934 0.114448 ------------------------------------------------------------------ ./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.0244858 General matching 9920 0.0659032 Preflow 9920 0.0363429 ------------------------------------------------------------------ ./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.026413 General matching 10000 0.032402 Preflow 10000 0.0555508 ------------------------------------------------------------------ ./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.0207119 General matching 9999 0.0564229 Preflow 9999 0.054014 ----------------------------------------------------------------------------------------------- ./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.139076 General matching 472576 0.00326991 Capacity scaling 472576 0.0879331 Cost scaling 472576 0.0118301 Network simplex 472576 0.00567198 ----------------------------------------------------------------------------------------------- ./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.136649 General matching 490695 0.00336504 Capacity scaling 490695 0.088218 Cost scaling 490695 0.0123198 Network simplex 490695 0.00531006 ----------------------------------------------------------------------------------------------- ./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.197766 General matching 914524 0.027005 Capacity scaling 914524 0.100053 Cost scaling 914524 0.0668819 Network simplex 914524 0.0146241 ----------------------------------------------------------------------------------------------- ./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.181663 General matching 919943 0.022315 Capacity scaling 919943 0.0937889 Cost scaling 919943 0.074887 Network simplex 919943 0.0133469 ----------------------------------------------------------------------------------------------- ./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.505637 General matching 890836 0.0145609 Capacity scaling 890836 1.70609 Cost scaling 890836 0.0605259 Network simplex 890836 0.00779986 ----------------------------------------------------------------------------------------------- ./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.502237 General matching 897412 0.0146611 Capacity scaling 897412 1.71704 Cost scaling 897412 0.0664949 Network simplex 897412 0.00781202 ----------------------------------------------------------------------------------------------- ./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.202065 General matching 895469 0.014302 Capacity scaling 895469 0.134837 Cost scaling 895469 0.0462389 Network simplex 895469 0.00812817 ----------------------------------------------------------------------------------------------- ./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.192539 General matching 893040 0.014688 Capacity scaling 893040 0.142115 Cost scaling 893040 0.0465879 Network simplex 893040 0.00778508 ----------------------------------------------------------------------------------------------- ./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 1.52556 General matching 2383509 0.0276449 Capacity scaling 2383509 2.19282 Cost scaling 2383509 0.129686 Network simplex 2383509 0.22806 ----------------------------------------------------------------------------------------------- ./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 1.48321 General matching 2394615 0.0271301 Capacity scaling 2394615 2.19058 Cost scaling 2394615 0.152851 Network simplex 2394615 0.263314 ----------------------------------------------------------------------------------------------- ./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 2.20795 General matching 4205491 0.128231 Capacity scaling 4205491 1.58734 Cost scaling 4205491 0.489221 Network simplex 4205491 0.091192 ----------------------------------------------------------------------------------------------- ./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 2.46947 General matching 4197432 0.140808 Capacity scaling 4197432 1.59073 Cost scaling 4197432 0.682716 Network simplex 4197432 0.0957692 ----------------------------------------------------------------------------------------------- ./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 6.61569 General matching 7029959 0.170723 Capacity scaling 7029959 10.8181 Cost scaling 7029959 0.831383 Network simplex 7029959 0.240637 ----------------------------------------------------------------------------------------------- ./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 6.26456 General matching 7056257 0.167678 Capacity scaling 7056257 10.9781 Cost scaling 7056257 0.889265 Network simplex 7056257 0.25909 ----------------------------------------------------------------------------------------------- ./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 8.96618 General matching 8396190 0.441941 Capacity scaling 8396190 6.48904 Cost scaling 8396190 1.83858 Network simplex 8396190 0.317024 ----------------------------------------------------------------------------------------------- ./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 9.69202 General matching 8393092 0.444463 Capacity scaling 8393092 6.55828 Cost scaling 8393092 1.99005 Network simplex 8393092 0.313474