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.