On Wed, 7 Mar 2007, Stephan Diederich wrote:

On 3/6/07, François Duranleau wrote:

...

It seems there is an inconsistency (to me) between color tagging of vertices in edmund_karp_max_flow and kolmogorov_max_flow algorithms.

In the documentation of kolmogorov_max_flow, it says:

"If the color of a vertex after running the algorithm is white the vertex belongs to the source tree else it belongs to the sink-tree (used for minimum cuts)."

In short, vertices linked to the source are white.

However, for edmund_karp_max_flow, it says:

"At the end of the algorithm, the white vertices define the minimum cut set."

Thus in this case, it's the vertices connected to the sink that are white.

Why? Maybe the docs are not really accurate here. But I think this could also mean, that this are the vertices connected to the source.

Why the difference in color tagging between the two algorithms?

For the reasons above, I think there are no differences. Below is a short example which uses kolmogorov_mf and edmunds_karp_mf. It can be run with the *.dat files from $(BOOST_ROOT)/libs/graph/examples like this: edmunds_karp_maxflow < max_flow.dat

[snip example] Mm, I am confused. I compiled and run your example, and yes, the results are identical... But with the following example, I get inversed colors, and the flow returned by edmund_karp_max_flow is 0. What am I doing wrong? I use gcc-4.0.3 and Boost head cvs. I also tried with 1.33.1+kolmogorov, same thing. #include #include #include #include <limits> #include <iostream> template < typename Graph , typename Weight > void add_uedge( Graph& g , typename ::boost::graph_traits< Graph >::vertex_descriptor u , typename ::boost::graph_traits< Graph >::vertex_descriptor v , const Weight& w ) { using namespace ::boost ; typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor ; edge_descriptor e1 = add_edge( u , v , g ).first ; edge_descriptor e2 = add_edge( v , u , g ).first ; put( edge_capacity , g , e1 , w ) ; put( edge_capacity , g , e2 , w ) ; put( edge_reverse , g , e1 , e2 ) ; put( edge_reverse , g , e2 , e1 ) ; } template < typename Graph > void dump_coloring( const Graph& g ) { using namespace ::boost ; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator ; for ( ::std::pair< vertex_iterator , vertex_iterator > v = vertices( g ) ; v.first != v.second ; ++ v.first ) { if ( get( vertex_color , g , * v.first ) == color_traits< default_color_type >::white() ) { ::std::cout << "White: " << * v.first << ::std::endl ; } else { ::std::cout << "Black: " << * v.first << ::std::endl ; } } } int main() { using namespace ::boost ; typedef adjacency_list_traits< vecS , vecS , directedS > adj_list_traits ; typedef adjacency_list< vecS , vecS , directedS , property< vertex_color_t , default_color_type > , property< edge_capacity_t , double , property< edge_residual_capacity_t , double , property< edge_reverse_t , adj_list_traits::edge_descriptor > > > > graph_type ; graph_type g( 11 ) ; typedef ::std::numeric_limits< double > limits ; typedef graph_traits< graph_type >::edge_descriptor edge_descriptor ; add_uedge( g , 0 , 1 , limits::max() ) ; add_uedge( g , 0 , 2 , limits::max() ) ; add_uedge( g , 0 , 3 , limits::max() ) ; add_uedge( g , 1 , 2 , 1.0 ) ; add_uedge( g , 2 , 3 , 1.0 ) ; add_uedge( g , 1 , 4 , 0.1 ) ; add_uedge( g , 2 , 5 , 1.0 ) ; add_uedge( g , 3 , 6 , 1.0 ) ; add_uedge( g , 4 , 5 , 0.1 ) ; add_uedge( g , 5 , 6 , 1.0 ) ; add_uedge( g , 4 , 7 , 1.0 ) ; add_uedge( g , 5 , 8 , 0.1 ) ; add_uedge( g , 6 , 9 , 0.1 ) ; add_uedge( g , 7 , 8 , 1.0 ) ; add_uedge( g , 8 , 9 , 1.0 ) ; add_uedge( g , 5 , 9 , 1.0 ) ; add_uedge( g , 6 , 8 , 1.0 ) ; add_uedge( g , 7 , 10 , limits::max() ) ; add_uedge( g , 8 , 10 , limits::max() ) ; add_uedge( g , 9 , 10 , limits::max() ) ; double flow = edmunds_karp_max_flow( g , 0 , 10 , // If I do not set this explicitly, all // vertices are white color_map( get( vertex_color , g ) ) ) ; ::std::cout << "flow Edmund-Karp = " << flow << ::std::endl ; dump_coloring( g ) ; ::std::vector< unsigned int > distances( num_vertices( g ) ) ; ::std::vector< edge_descriptor > preds( num_vertices( g ) ) ; flow = kolmogorov_max_flow( g , 0 , 10 , distance_map( & distances[ 0 ] ) .predecessor_map( & preds[ 0 ] ) ) ; ::std::cout << "flow Kolmogorov = " << flow << ::std::endl ; dump_coloring( g ) ; return 0 ; } -- François Duranleau LIGUM, Université de Montréal

Hi François, On 3/9/07, Stephan Diederich wrote:

Hi,

On 3/7/07, François Duranleau wrote:

...

On Wed, 7 Mar 2007, Stephan Diederich wrote:

...

On 3/6/07, François Duranleau wrote:

...

It seems there is an inconsistency (to me) between color tagging of vertices in edmund_karp_max_flow and kolmogorov_max_flow algorithms.

[snip]

Hm, I am confused. I compiled and run your example, and yes, the results

...

are identical... But with the following example, I get inversed colors, and the flow returned by edmund_karp_max_flow is 0. What am I doing wrong? I use gcc-4.0.3 and Boost head cvs. I also tried with 1.33.1+kolmogorov, same thing.

You're absolutely right. kolmogorov_max_flow uses exactly the inversed colors - which is bad. My previous example had a bug. I found it after reading your comment about the color_map. edmunds_karp creates one of its own if it doesn't find it in the named properties. I'll change the colors of kolmogorov_max_flow and report it to the list, once it's done. Thanks for pointing out this inconsistency! Cheers, Stephan