All tests were performed with an Intel P4-2.8GHz, 1GB RAM, gcc 4.1 -O3
(I tried both the msvc-8.0 and the icc 9.1 compilers, but each of them gave worse results than gcc)
Data file (with tables from which charts below were generated)
Glossary:
- kolmogorov: Vladimir Kolmgorov's implementation of his algorithm
- pushrelabel: boost::push_relabel_max_flow
- b_kolmog: boost::kolmogorov_max_flow
- b_kolmo_no_term: Not yet released version of boost::kolmogorov_max_flow where edges to terminal are implicitly modelled through capacities attached to each vertex (useful where source and sink vertices have huge out_degree())
- hi_pr, hi_prw: Efficient C implementations of the push-relabel-algorithm from Andrew Goldberg
- leda: default graphs from LEDA; static graphs (which should be faster) don't compile on gcc-4.1 yet
What can be read from those charts:
- graph-cut algorithms runtime depends dramatically on the type of the graph
- boost's generic version of Kolmogorov's algorithm is just slightly slower (and this will change in future ;))
