[Boost-users] [Graph] newbie to graph

Subject: [Boost-users] [Graph] newbie to graph
From: Lior Weizman (lior.weizman_at_[hidden])
Date: 2008-10-30 05:41:51

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 <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/graph/kolmogorov_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/write_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<edge_capacity_t, long,
      property<edge_residual_capacity_t, long,
        property<edge_reverse_t, Traits::edge_descriptor> > >
  > Graph;

  typedef graph_traits <Graph>::edge_descriptor edge_descriptor;
  typedef Traits::vertex_descriptor vertex_descriptor;
  typedef std::pair<edge_descriptor, bool> EdgePair;
  typedef std::pair<int,int> Pair;
  Graph g;
  long flow;
  property_map<Graph, vertex_name_t>::type
      name = get(vertex_name, g);
  property_map<Graph, edge_capacity_t>::type
    capacity = get(edge_capacity, g);
  property_map<Graph, edge_reverse_t>::type
    rev = get(edge_reverse, g);
  property_map<Graph, edge_residual_capacity_t>::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