Subject: [boost] Graph cut questions
From: David Doria (daviddoria+boost_at_[hidden])
Date: 2009-09-15 11:57:06
1) If I do this: (with any of the max_flow algorithms, kolmogorov is just
used as an example)
double flow = kolmogorov_max_flow(g, SourceNode, SinkNode);
I get the value of the max flow, but how do I tell which nodes of g belong
to the "source side" of the graph and which nodes belong to the "sink side"?
(thinking of it as a min cut rather than a max flow problem)
2) Is it possible to tell the max flow algorithm to use multiple
3) The max_flow functions seem to require a source and sink to be specified.
Shouldn't you be able to find the minimum cut that partitions the graph into
two parts even without specifying a source/sink?
4) Currently you must use a bidirectional graph, and specify an
edge_reverse_t in the graph traits, then set the reverse edge for every
edge. a) this is pretty complicated for someone who is unfamiliar with
generic programming. b) If an undirected graph is used, the algorithm should
automatically take care of adding these reverse edges if they are required
for the cut to be performed.
Can these be considered as feature requests if they are not currently
possible? I have not found a more promising graph library for c++, so it
would be nice if BGL could be molded into the one everyone would like to
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk