BGL: Undirected graphs and max flow
Hi all, 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. Thanks,
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
On Tuesday 22 March 2005 20:39, Doug Gregor wrote:
On Mar 22, 2005, at 1:48 PM, Cyrille Damez wrote: 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.
In fact, I'm not looking for the max flow but for a min cut. The application here is image segmentation (edges are pixel and edges cost/capacity are differences between pixels). This is a quite common use for graph cuts in computer vision and computer graphics.
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.
Yes, it doesn't seem straightforward. Thanks for your help.
participants (3)
-
Cyrille Damez -
cyrille.damez＠laposte.net
-
Doug Gregor