[Boost-users] Removing edges using remove_edge in adjacency list

Subject: [Boost-users] Removing edges using remove_edge in adjacency list
From: giridhar (giridharms_at_[hidden])
Date: 2010-11-01 15:29:12

Hello All,

        I am completely new to using BGL and STL. I know the concept of STL
but had never used it before. I have to implement an algorithm for my thesis
and I am trying to use BGL for that. I have made use of Dijkstra's algorithm
that is inbuilt in BGL. Below is the code, which is similar to that in the
reference manual with few changes.

#include <iostream>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace std;
using namespace boost;

/*struct flow_t
{
    typedef edge_property_tag kind;
};

struct capacity_t
{
    typedef edge_property_tag kind;
};

namespace boost
{
    enum edge_flow_t { edge_flow};
    enum edge_capacity_t {edge_capacity};
    BOOST_INSTALL_PROPERTY(edge,capacity);
} */
int main()
{
    typedef property<vertex_distance_t,int, property
<vertex_name_t,std::string> > VertexProperty;
//    typedef property<flow_t,capacity_t, int> Cap;
    typedef property<edge_weight_t,int> EdgeProperty;
  typedef adjacency_list < listS, vecS, directedS,
    VertexProperty, EdgeProperty > graph_t;
  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
 // typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
  typedef std::pair<int, int> Edge;

  const int num_nodes = 5;
  enum nodes { A, B, C, D, E };
  char name[] = "ABCDE";
  Edge edge_array[] = { Edge(A, B), Edge(A, C), Edge(B, E), Edge(C, B),
    Edge(C, D), Edge(D, E)
//    , Edge(D, E), Edge(E, A), Edge(E, B)
  };
  int weights[] = { 4, 1, 3, 2, 2, 3};
  int num_arcs = sizeof(edge_array) / sizeof(Edge);
  graph_t g( edge_array, edge_array+num_arcs, weights, num_nodes);
  std::vector<vertex_descriptor> p(num_vertices(g));
  std::vector<int> d(num_vertices(g));
  vertex_descriptor s= vertex(A,g);
  dijkstra_shortest_paths(g,s,predecessor_map(&p[0]).distance_map(&d[0]));
 // std::cout<<"timepass"<<s<<std::endl;
  std::cout<<"Distaces and Parents"<<std::endl;
  graph_traits<graph_t>::vertex_iterator vi,vend;
  for(tie(vi,vend)=vertices(g);vi!=vend;++vi)
  {
      std::cout<<"distance("<<name[*vi]<<")= "<<d[*vi]<<",";
      std::cout<<"parent("<<name[*vi]<<")= "<<name[p[*vi]]<<std::endl;
  }
  std::cout<<std::endl;

  graph_traits<graph_t>::vertex_iterator i,iend;
 // std::cout<<"testing iterators "<<i<<","<<iend<<std::cout;
  for(tie(i,iend)=vertices(g);i!=iend;++i)
  {
      if(s==*i) continue;
      else
    remove_edge(name[*i],name[p[*i]],g);
  }
  cout<<"After removal of working path"<<std::endl;
  vertex_descriptor s1= vertex(A,g);
  std::vector<vertex_descriptor> p1(num_vertices(g));
  std::vector<int> d1(num_vertices(g));

dijkstra_shortest_paths(g,s1,predecessor_map(&p1[0]).distance_map(&d1[0]));
  std::cout<<"Distaces and Parents"<<std::endl;
  graph_traits<graph_t>::vertex_iterator i1,end1;
  for(tie(i1,end1)=vertices(g);i1!=end1;++i1)
  {
      std::cout<<"distance("<<name[*i1]<<")= "<<d1[*i1]<<",";
      std::cout<<"parent("<<name[*i1]<<")= "<<name[p1[*i1]]<<std::endl;
  }
  std::cout<<std::endl;

}

Now I want to remove the edges that has been found by Dijkstra's algorithm
or alter the weights of those edges found by dijkstra's to some high value.
This is mainly to find different route to target. I know I am doing
something wrong with iterator's. But I am not able to figure it out due to
lack of knowledge in STL. I tried to find it online, but could not find
satisfactory explanation. If someone could give some explanation, it would
be really helpful for me. Please help.
-- 
Regards,
Giridhar