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

From: Stephan Diederich (S.Diederich_at_[hidden])
Date: 2006-08-30 13:30:07

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-maxflow/trunk/libs/graph/src/max_flow_graph_gen/genrmf/genrmf.c
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