https://svn.boost.org/trac10/ticket/3478 <p> 1) The max flow can be obtained with: (any of the max_flow algorithms, kolmogorov is just used as an example) </p> <p> double flow = kolmogorov_max_flow(g, <a class="missing wiki">SourceNode</a>, <a class="missing wiki">SinkNode</a>); </p> <p> It would be nice to also interpret this max flow as a min cut. I.e. be able to tell which nodes of g belong to the "source side" of the graph and which nodes belong to the "sink side"? Maybe something like a std::vector&lt;unsigned int&gt; <a class="missing wiki">GetSourceSideNodes</a>(); <em>return the IDs of the nodes on the source side std::vector&lt;unsigned int&gt; <a class="missing wiki">GetSinkSideNodes</a>();</em>return the IDs of the nodes on the sink side std::vector&lt;unsigned int&gt; <a class="missing wiki">GetCutEdges</a>(); <em> return the IDs of the edges which were cut </em></p> <p> 2) Allow the min cut algorithm to accept multiple sources/sinks. The cut should simply be the minimum sum of edges that can be severed to split the graph so that all of the sinks are on one side of the cut and all of the sources are on the other side of the cut. </p> <p> 3) Find the minimum cut that partitions the graph into two parts without specifying a source/sink? I.e. the minimum of all of the possible source/sink pairs minium cuts. </p> <p> 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. </p> <p> 5) VERY simple examples (actually constructing a graph (not reading it from file) with &lt; 10 nodes) should be provided to demonstrate all of these cases. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/3478 Trac 1.4.3 Andrew Sutton Mon, 15 Mar 2010 11:32:17 GMT https://svn.boost.org/trac10/ticket/3478#comment:1 https://svn.boost.org/trac10/ticket/3478#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> <p> I think that this is similar related to <a class="new ticket" href="https://svn.boost.org/trac10/ticket/3152" title="#3152: Feature Requests: Obtaining a minimum s-t cut edge set (new)">#3152</a>, but expressed a little more explicitly. Addressing these issues will probably result in a new mincut/maxflow algorithm suite. </p> Ticket Jeremiah Willcock Wed, 08 Dec 2010 19:44:44 GMT https://svn.boost.org/trac10/ticket/3478#comment:2 https://svn.boost.org/trac10/ticket/3478#comment:2 <ul> <li><strong>milestone</strong> <span class="trac-field-old">Boost 1.41.0</span> → <span class="trac-field-new">To Be Determined</span> </li> </ul> Ticket