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