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
Graph types (all generators can be obtained from here):
- ac: acyclic dense graphs; each node has outgoing edges to all of it's following nodes (example)
- ak(i): generator from Goldberg/Cherkassy; generates two subgraphs between source and sink which are both hard to solve (example)
- random graphs: used the genrmf random graph generator
- images: sample segmentation problems
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 ;))
