I can rule out this possibility: every node except the source and sink node is connected to both the source and sink. That is, there exist a directed path (source,node,sink) for all nodes.
Could those correspond to cycles? I know that with BFS/DFS (and Dijkstra's?), gray vertices tend to indicate that they're still in a buffer, which could indicate that the algorithm is re-pushing some vertices or edges. I'm just guessing here.
The difficulty is that the boost graph library does not seem to provide a way to easily obtain an edge cut set from the max flow solution. This is not trivial, because the edge cut set might not be unique. (That is, just taking all edges with zero residual capacity does not work.)
This isn't particularly surprising. The people that write the algorithms tend to have a specific set of needs and they don't often generalize to tasks that should be easy. Consider the task of tracing the edges from one vertex to another along the shortest path. It should be easy, but its not, nor is there a clear example that demonstrates how its done. There's the potential to build a little library around each algorithm, but things haven't quite worked out that way. If you're interested in contributing a framework for this task, we'll certainly try to get it integrated. Andrew Sutton andrew.n.sutton@gmail.com