Re: [Boost-users] [BGL] kolmogorov_max_flow: vertices output colors

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