[SoC][BGL] new mincut/maxflow algorithm
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/kolmogoro... 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... and browsed via https://www.boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/mincut... Algorithm's implementation only from: https://www.boost-consulting.com:8443/svn/main/boost/soc/2006/mincut-maxflow... 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
On 8/28/06, Stephan Diederich <S.Diederich@gmx.de> wrote:
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/kolmogoro...
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).
Stephan, Thanks! Looks like a very good implementation. Can you elaborate a little on your experimentation? What are ac-graphs and ak(i)-graphs, and what parameters did you use to generate the random graphs? I skimmed Komolgorov's thesis, and based on his experiments, it seems that this is a very efficient algorithm for 2-D and 3-D grid graphs arising in image processing applications - did you get a sense for what other types of graphs this algorithm might be competitive on? Maybe graphs with low degree in general? Thanks again for your contribution! Aaron
Hi Aaron, [snip]
Stephan,
Thanks! Looks like a very good implementation. Can you elaborate a little on your experimentation?
I came to those graph types from a comparison which was published by LEDA and I wanted to have some not-from-image-processing graphs for comparisons, too. Most of those graph-generators came from an DIMACS implementation contest in 1991 (http://dimacs.rutgers.edu/Challenges/) The sources and scripts for graph generation and performance measurements are in the repository, located at libs/graph/src/{max_flow_graph_gen,max_flow_performance}.
What are ac-graphs and ak(i)-graphs, and what parameters did you use to generate the random graphs? ac-graphs (acyclic-dense-graphs): Each node has outgoing edges to all of it's following nodes. (it's only parameter is the number of nodes) ak(i)-graphs: Starting from the source vertex they split up in two subgraphs, where one is more ugly than the other for maxflow solvers ;). Especially Kolmogorov's algorithm can't point here as the built up search trees are destroyed in each round. genrmf (the random graph generator): A good description of the parameters can be found in the implementation at https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/mincut-max... The values I tested with: Framesize = {50, 100, 200}, Depth = {1, 2, 4}.
I skimmed Komolgorov's thesis, and based on his experiments, it seems that this is a very efficient algorithm for 2-D and 3-D grid graphs arising in image processing applications - did you get a sense for what other types of graphs this algorithm might be competitive on? Maybe graphs with low degree in general?
The algorithm builds up two search trees. One is starting from the source, one from the sink. If the algorithm can keep those two search trees after the augment-phase through adoption, the runtime is pretty good. If they are destroyed in each iteration it can't get worse. That said, a graph should have "homogeneous areas" which are connected to the source or sink. In those areas, most of the edges should have high capacities so that adoption can be successful. Recently there has been a discussion about dynamically selecting the better suited algorithm. I thought about that for mincut/maxflow, too. But at the moment I've no idea / criteria on how I'd select the right one. Cheers, Stephan
participants (2)
-
Aaron Windsor -
Stephan Diederich