Hi François,

On 3/6/07, François Duranleau <duranlef@iro.umontreal.ca > 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;
}