Re: [Boost-users] BGL: Undirected graphs and max flow

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-03-22 14:39:31

On Mar 22, 2005, at 1:48 PM, Cyrille Damez wrote:
> I realize this might sound a little dumb, but I can't find in the
> documentation how to use (if it is possible at all) the 
> push_relabel_max_flow
> function with undirected graphs. The problem is that 
> push_relabel_max_flow
> requires an edge property that maps each edge to a reverse edge, which 
> seems
> redundant when the graph type is undirected.

I've only seen max-flow problems formulated for directed graphs, so I'm 
not sure how we could apply those algorithms (or the problem itself) to 
an undirected graph. We would need some way to pick a direction for the 
undirected edges, and somehow "split" the edge so that it looked like 
separate forward and reverse edges. I'm sure we could come up with a 
graph adaptor for this, but it would not be easy.

        Doug