[boost] [SoC][BGL] new mincut/maxflow algorithm

From: Stephan Diederich (S.Diederich_at_[hidden])
Date: 2006-08-28 11:22:49

Hello,

with this mail I want to point to my work done during this year's SoC:
"Implementing a state of the art mincut/maxflow algorithm".

Mentored by Douglas Gregor I implemented a maxflow/mincut algorithm
for BGL which was originally presented by Vladimir Kolmogorov[1].

The documentation and description of the implementation can be found at:
http://mp-vipa5.informatik.uni-mannheim.de/~diederich/data/soc/doc/kolmogorov_max_flow.html

The goal of the project was to have an algorithm with a runtime which is
comparable to other standard maxflow/mincut implementations.
Performance measurements
(http://stephan.diederich.googlepages.com/soc2006222) show that this
goal was reached.
What can be read from those charts is, that the runtime of the
algorithms clearly depends on the underlying problem type. For graphs
found in image segmentation problems and random graphs, the newly
developed algorithm outperforms the existing alternative(s).

Future work:
In an extra version (kolmogogorv_max_flow_no_terminals.hpp) I changed
the algorithm to omit all vertex-terminal edges. This is very
interesting for graphs where many vertices are connected to the
terminals. Instead of having those edges present in the graph, these
capacities are stored directly as properties of the vertices. This
gives a nice performance boost. The goal is to merge those two
implementations into one.

Full repository can be checked out from
https://www.boost-consulting.com:8443/svn/main/boost/soc/2006/mincut-maxflow/trunk
and browsed via
https://www.boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/mincut-maxflow/trunk
Algorithm's implementation only from:
https://www.boost-consulting.com:8443/svn/main/boost/soc/2006/mincut-maxflow/trunk/boost/graph/kolmogorov_max_flow.hpp

As this is my very first contribution to Boost I would like to get as
much feedback as possible. The learning curve is the steepest in the
beginning... ;)

Thanks a lot,
Stephan

[1] http://www.adastral.ucl.ac.uk/~vladkolm/papers/PHD.html