Re: [Boost-users] [graph] edmund_karp_max_flow vs kolmogorov_max_flow color map

7 Mar 2007

      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