Re: [boost] [graph] kolmogorov_max_flow color map, gray state

Subject: Re: [boost] [graph] kolmogorov_max_flow color map, gray state
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-02-28 21:36:54

> 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_at_[hidden]