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

From: François Duranleau (duranlef_at_[hidden])
Date: 2007-03-07 17:49:32

On Wed, 7 Mar 2007, Stephan Diederich wrote:

> On 3/6/07, François Duranleau <duranlef_at_[hidden]> 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 <boost/graph/adjacency_list.hpp>
#include <boost/graph/edmunds_karp_max_flow.hpp>
#include <boost/graph/kolmogorov_max_flow.hpp>
#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