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

From: Stephan Diederich (stephan.diederich_at_[hidden])
Date: 2007-03-07 16:00:47

Hi François,

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

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<property_map < Graph, vertex_color_t
>::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 <<std::endl;
        else{
            std::cout << "Black:" << *u_iter <<std::endl;
        }
    }
    {
        std::cout << "Edmund: " << std::endl;
        long flow = edmunds_karp_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 boost::color_traits<boost::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 <<std::endl;
        else{
            std::cout << "Black:" << *u_iter <<std::endl;
        }
    }
    return EXIT_SUCCESS;
}