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

From: cyrille.damez_at_[hidden]
Date: 2005-03-22 15:08:18

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.