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