Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] kolmogorov_max_flow: vertices output colors
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-10-30 16:26:00


On Fri, 29 Oct 2010, Olivier Tournaire wrote:

> Hi all,
> I am currently havong a problem with the Kolmogorov max flow usage in the BGL. The probelm is that at the end of the algorithm, some vertices are gray. What is
> there real status: do they belong to the tree or sink. None of both? Why?

Does <URL:https://svn.boost.org/trac/boost/ticket/3152> describe something
similar to what you're seeing? I do not understand the algorithm so I
can't answer your question; the documentation claims that the min-cut is
between black and non-black vertices. You might want to look at the
original Boykov and Kolmogorov paper at
<URL:http://www.csd.uwo.ca/faculty/yuri/Abstracts/pami04-abs.html>. That
paper (p. 11) suggests that you can choose any cut as the minimum one as
long as all black vertices are on one side and all white ones are on the
other. However, that may not apply to the Boost version since people have
reported that it produces suboptimal results (see the ticket above as well
as <URL:https://svn.boost.org/trac/boost/ticket/3468>).

-- Jeremiah Willcock


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net