samedi 23 septembre 2017

Boost graph Library using Bundled properties

I am new to BGL and trying to setup a simple shortest path finding program using BGL where undirected graph is defined as a adjacency List with custom defined EdgeProperty and VertexProperty. I am getting compile time error which I attribute to my insufficient skills in templates and Boost. The code is as follows:

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

using namespace  std;
using namespace boost;
enum Node_type
{
  STAIR,
  LEVEL,
  LIFT,
  OTHER,
  UNKNOWN
};

class VertexProperty
{
public:
  VertexProperty(){ id=-1; type=Node_type::UNKNOWN, level_id=254, stair_id=254;}
  std::string toString()
  {
    std::string str;
    str = "id "+to_string(id)+" type "+to_string(type)+" level "+to_string(level_id)+" stair_id "+to_string(stair_id);
    return str;
  }

  int getVertexID() {return id;}
  int id;
  Node_type type;
  int level_id;
  int stair_id;
};

class EdgeProperty
{
public:
  EdgeProperty(){id=-1, weight=0;}
  EdgeProperty(int i, double wt){ id=i; weight=wt;  }
  double getWeigth(){ return weight;}
  int getID() {return id;}
  std::string toString()
  {
    std::string str;
    str = "id "+to_string(id)+" weight="+to_string(weight);
    return str;
  }

  int id;
  double weight;
};

typedef boost::property<boost::edge_weight_t, double> EdgeWeigthProperty;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,VertexProperty, EdgeProperty> UndirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator;
typedef boost::graph_traits<UndirectedGraph>::vertex_iterator vertex_iterator;
typedef boost::directed_graph <boost::no_property, EdgeWeigthProperty> DirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;

class A
{
public:
  A();
  void undirected_graph_creation();
  void directed_graph_creation();
  void showEdges();
  void showVertices();
  void run_dijkastra();
  UndirectedGraph g;
    DirectedGraph dg;
    map<int, vertex_descriptor> map_id_vertex_desc;
    map<int, edge_descriptor> map_id_edge_desc;
    map<int, Node_type> map_node_id_type;
};

A::A()

    {

    }

    void A::undirected_graph_creation()
    {

  UndirectedGraph::vertex_descriptor v0= boost::add_vertex(g);
  map_id_vertex_desc.emplace(0,v0);
  g[v0].id=0;
  g[v0].type=Node_type::LEVEL;
  UndirectedGraph::vertex_descriptor v1= boost::add_vertex(g);
  g[v1].id=1;
  g[v1].type=Node_type::STAIR;
  map_id_vertex_desc.emplace(1,v1);
  UndirectedGraph::vertex_descriptor v2= boost::add_vertex(g);
  map_id_vertex_desc.emplace(2,v2);
  g[v2].id=2;
  g[v2].type=Node_type::STAIR;
  UndirectedGraph::vertex_descriptor v3= boost::add_vertex(g);
  map_id_vertex_desc.emplace(3,v3);
  g[v3].id=3;
  g[v3].type=Node_type::STAIR;
  /*EdgeWeigthProperty w8(8);
  EdgeWeigthProperty w18(18);
  EdgeWeigthProperty w20(20);
  EdgeWeigthProperty w2(2);
  EdgeWeigthProperty w7(7);*/
  EdgeProperty w8(1,8);
  EdgeProperty w18(2,18);
  EdgeProperty w20(3,20);
  EdgeProperty w2(4,2);
  EdgeProperty w7(5,7);

  boost::add_edge(v0,v1,w8,g);
  boost::add_edge(v0,v3,w18,g);
  boost::add_edge(v1,v2,w20,g);
  boost::add_edge(v2,v3,w2,g);
  boost::add_edge(v1,v3,w7,g);
}

void A::showEdges()
{
  std::pair<edge_iterator,edge_iterator> ei=edges(g);
  std::cout<<" number of edges "<<num_edges(g)<<endl;
  std::cout<<" Edge list ";
  for(edge_iterator it= ei.first; it!=ei.second; ++it)
    cout<<*it<<" "<<g[*it].toString()<<endl;
}

void A::showVertices()
{
  std::pair<vertex_iterator, vertex_iterator> vi= boost::vertices(g);
  std::cout<<" Number of vertices are "<<endl;
  for( vertex_iterator i = vi.first; i!=vi.second; ++i)
  {
    cout<<*i<<" id="<<g[*i].toString()<<" type="<<g[*i].type<<endl;
  }

}
void A::run_dijkastra()
{
  std::vector<vertex_descriptor> predecessors(boost::num_vertices(g));
  std::vector<EdgeProperty> distances(boost::num_vertices(g));
  std::pair<vertex_iterator,vertex_iterator> vi=boost::vertices(g);
  vertex_descriptor first_vertex_descriptor = *(vi.first);
  vertex_descriptor start_vertex = boost::vertex(0,g);

 // boost::dijkstra_shortest_paths(g, first_vertex_descriptor,
  //                               boost::weight_map(get(&EdgeProperty::weight,g))
   //                              .distance_map(boost::make_iterator_property_map(distances.begin(), get(boost::vertex_index, g)))                               );

 dijkstra_shortest_paths(g, first_vertex_descriptor,
                         predecessor_map(make_iterator_property_map(predecessors.begin(), get(vertex_index,g))).distance_map(make_iterator_property_map(distances.begin(), get(boost::vertex_index,g))).weight_map(get(&EdgeProperty::weight,g));
/*
 std::cout << "distances and parents:" << std::endl;
 graph_traits < UndirectedGraph >::vertex_iterator vi1, vend1;
 for (boost::tie(vi1, vend1) = vertices(g); vi1 != vend1; ++vi1) {
   std::cout << "distance(" << g[*vi1].id << ") = " << distances[*vi1].toString() << ", ";
   std::cout << "parent(" << g[*vi1].id << ") = " << g[predecessors[*vi1]].id << std::
     endl;
 }*/
}

void A::directed_graph_creation()
{
//todo

}
int main()
{
  A a_graph;
  a_graph.undirected_graph_creation();
  a_graph.showEdges();
  a_graph.showVertices();;
  a_graph.run_dijkastra();
  return 0;
}

Error is unknown conversion from double to EdgeProperty. It appear that I have mistake in syntax of call to dijkstra_shortest_paths functions.

I will also like to replace data member of EdgeProperty with a function.

Other query I have is about maintaining an index to nodes via vertex descriptor. At present, I am using VertexProperty::id do maintain a dictionary to object of VertexProperty type. Do Boost maintains internally any dictionary which I can use of.

I am using gcc5.4 version compiler on Ubuntu 16.04 Thank you

Nitin

Aucun commentaire:

Enregistrer un commentaire