SoC 2006 - Performance meassurements

Code access Performance meassurements Links

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)


  • 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 ;))