[graph] edmund_karp_max_flow vs kolmogorov_max_flow color map
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. 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 the difference in color tagging between the two algorithms? -- François Duranleau LIGUM, Université de Montréal
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; }
On Wed, 7 Mar 2007, Stephan Diederich wrote:
On 3/6/07, François Duranleau <duranlef@iro.umontreal.ca> 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
Hi, On 3/7/07, François Duranleau <duranlef@iro.umontreal.ca> wrote:
On Wed, 7 Mar 2007, Stephan Diederich wrote:
On 3/6/07, François Duranleau <duranlef@iro.umontreal.ca> wrote:
It seems there is an inconsistency (to me) between color tagging of vertices in edmund_karp_max_flow and kolmogorov_max_flow algorithms.
[snip] Hm, 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.
First, thanks for the example. I could reproduce this here. But I don't have the time to look into this deeper before the weekend. One thing I've seen is that edmunds_karp requires the reverse-edge weights to be zero. But changing it didn't make it better. Changing the edge_weights from max() to something smaller made edmunds_karp at least return the same flow as kolmogorov_mf does. I'll look into it at the weekend. Cheers, Stephan
Hi François, On 3/9/07, Stephan Diederich <stephan.diederich@googlemail.com> wrote:
Hi,
On 3/7/07, François Duranleau <duranlef@iro.umontreal.ca> wrote:
On Wed, 7 Mar 2007, Stephan Diederich wrote:
On 3/6/07, François Duranleau <duranlef@iro.umontreal.ca> wrote:
It seems there is an inconsistency (to me) between color tagging of vertices in edmund_karp_max_flow and kolmogorov_max_flow algorithms.
[snip]
Hm, 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.
You're absolutely right. kolmogorov_max_flow uses exactly the inversed colors - which is bad. My previous example had a bug. I found it after reading your comment about the color_map. edmunds_karp creates one of its own if it doesn't find it in the named properties. I'll change the colors of kolmogorov_max_flow and report it to the list, once it's done. Thanks for pointing out this inconsistency! Cheers, Stephan
Hi, On 3/10/07, Stephan Diederich <stephan.diederich@googlemail.com> wrote:
On 3/9/07, Stephan Diederich < stephan.diederich@googlemail.com> wrote:
On 3/7/07, François Duranleau <duranlef@iro.umontreal.ca> wrote:
On Wed, 7 Mar 2007, Stephan Diederich wrote:
On 3/6/07, François Duranleau <duranlef@iro.umontreal.ca > wrote:
It seems there is an inconsistency (to me) between color tagging of
vertices in edmund_karp_max_flow and kolmogorov_max_flow algorithms.
[snip]
Hm, 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.
You're absolutely right. kolmogorov_max_flow uses exactly the inversed colors - which is bad. My previous example had a bug. I found it after reading your comment about the color_map. edmunds_karp creates one of its own if it doesn't find it in the named properties. I'll change the colors of kolmogorov_max_flow and report it to the list, once it's done.
This is fixed in current CVS. (kolmogorov_max_flow coloring was changed) Thanks again for pointing this out! Cheers, Stephan
participants (5)
-
François Duranleau -
Stephan Diederich