I am a newbie to boost.
I am trying to build a graph and to compute the max_flow using
boost/graph/kolomogorov_max_flow.hpp.
Blow is my code:
-------------------------------------------------------------CODE-------------------------------------------------------------------------------
#include
#include <iostream>
#include <string>
#include
#include
#include
int
main()
{
using namespace boost;
typedef adjacency_list_traits Traits;
typedef adjacency_list,
property > >
Graph;
typedef graph_traits <Graph>::edge_descriptor edge_descriptor;
typedef Traits::vertex_descriptor vertex_descriptor;
typedef std::pair EdgePair;
typedef std::pair Pair;
Graph g;
long flow;
property_map::type
name = get(vertex_name, g);
property_map::type
capacity = get(edge_capacity, g);
property_map::type
rev = get(edge_reverse, g);
property_map::type
residual_capacity = get(edge_residual_capacity, g);
vertex_descriptor s, t;
Pair edge_array[6] = { Pair(0,1), Pair(0,2), Pair(0,3),
Pair(2,4),
Pair(1,3), Pair(4,3),
};
EdgePair edge_desc_obj;
EdgePair
edge_from_first=add_edge(edge_array[0].first,edge_array[0].second,g);
put(capacity,edge_from_first.first,1);
for (int i = 1; i < 5; ++i){
edge_desc_obj=add_edge(edge_array[i].first,
edge_array[i].second,g);
put(capacity,edge_desc_obj.first,i+1);
}
EdgePair
edge_to_last=add_edge(edge_array[5].first,edge_array[5].second,g);
put(capacity,edge_to_last.first,4);
char str[2];
for (int i=0;i<5;++i)
{
sprintf(str,"%d",i);
put(name,i,str);
}
edge_descriptor from_s,to_t;
from_s=edge_from_first.first;
to_t=edge_to_last.first;
s=source(from_s,g);
t=target(to_t,g);
flow = kolmogorov_max_flow(g, s, t);
return 0;
}
---------------------------------------------------------------------END OF
CODE---------------------------------------------------------------
The compilation output of the code above includes errors and can be found
here:
http://www.cs.huji.ac.il/~lweizm45/compile_output.txt
if I remove the call to kolmogorv_max_flow, everyting is fine. If I replace
the call to kolmogorov_max_flow with the line:
write_dimacs_max_flow(g, capacity, identity_property_map(),s, t, std::cout);
The output is:
-------------------------------------- OUTPUT
------------------------------------------------------
c DIMACS max-flow file generated from boost::write_dimacs_max_flow
p max 5 6
n 1 s
n 4 t
a 1 2 1
a 1 3 2
a 1 4 3
a 2 4 5
a 3 5 4
a 5 4 4
---------------------------------------- END OF OUTPUT
--------------------------------------------------
Which means that the graph was created correctly.
Calling the example "libs/graph/example/kolmogorov-eg.cpp" with the dimacs
output above as input, also works fine. This fact leads me to the assumption
that my graph is fine.
Does anyone know what is wrong with my graph when I perform a direct call to
kolmogorov_max_flow?
Thanks,
Lior
