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

7 Mar 2007

      Hi François,

On 3/6/07, François Duranleau  wrote:
...
Hi!
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.
Yes, that's right.

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

Cheers,
Stephan

#include <iostream>
#include <string>
#include 
#include 
#include 
#include 

int
main()
{
    using namespace boost;

    typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
    typedef adjacency_list < vecS, vecS, directedS,
    property < vertex_name_t, std::string,
    property < vertex_index_t, long,
    property < vertex_color_t, boost::default_color_type,
    property < vertex_distance_t, long,
    property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,

    property < edge_capacity_t, long,
    property < edge_residual_capacity_t, long,
    property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;

    Graph g;
    property_map < Graph, edge_capacity_t >::type
            capacity = get(edge_capacity, g);
    property_map < Graph, edge_residual_capacity_t >::type
            residual_capacity = get(edge_residual_capacity, g);
    property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);

    property_map < Graph, vertex_color_t >::type col = get(vertex_color, g);
    Traits::vertex_descriptor s, t;
    read_dimacs_max_flow(g, capacity, rev, s, t);
    {
        std::cout << "Kolmogorov: " << std::endl;
        long flow = kolmogorov_max_flow(g ,s, t);

        std::cout << "c  The total flow:" << std::endl;
        std::cout << "s " << flow << std::endl;

        graph_traits < Graph >::vertex_iterator u_iter, u_end;

        typedef property_traits
...
::type>::value_type tColorValue;
        typedef boost::color_traits<tColorValue> tColorTraits;
        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
            if(col[*u_iter] == tColorTraits::white())
                std::cout << "White:" << *u_iter <
graph_traits < Graph >::vertex_iterator u_iter, u_end;

        typedef boost::color_traitsboost::default_color_type tColorTraits;
        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
            if(col[*u_iter] == tColorTraits::white())
                std::cout << "White:" << *u_iter <

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

Stephan Diederich