Advertisement
Guest User

Boost Graph Problem

a guest
Jun 29th, 2011
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.85 KB | None | 0 0
  1. /*
  2.  *
  3.  */
  4.  
  5. #include <boost/config.hpp>
  6.  
  7. #include <boost/graph/graph_traits.hpp>
  8. #include <boost/graph/adjacency_list.hpp>
  9. #include <boost/graph/dijkstra_shortest_paths.hpp>
  10.  
  11. #include "dijkstra.h"
  12.  
  13. using namespace std;
  14. using namespace boost;
  15.  
  16.  
  17. struct Edge
  18. {
  19.   int id;
  20.   float8 cost;
  21. };
  22.  
  23. struct Vertex
  24. {
  25.   int id;
  26.   int edge_id;
  27. };
  28.  
  29. template <class G, class E>
  30. static void
  31. graph_add_edge(G &graph, int id, int source, int target, float8 cost)
  32. {
  33.   E e;
  34.   bool inserted;
  35.  
  36.   if (cost < 0) // edges are not inserted in the graph if cost is negative
  37.     return;
  38.  
  39.   tie(e, inserted) = add_edge(source, target, graph);
  40.  
  41.   graph[e].cost = cost;
  42.   graph[e].id = id;
  43.  
  44.   typedef typename graph_traits<G>::vertex_descriptor Vertex;
  45.   Vertex s = vertex(source, graph);
  46.   Vertex t = vertex(target, graph);
  47.   graph[s].id = source;
  48.   graph[t].id = target;
  49.   graph[s].edge_id = id;
  50.   graph[t].edge_id = id;
  51.  
  52. }
  53.  
  54. int
  55. boost_dijkstra_nodes(edge_t *edges, unsigned int count, int source_vertex_id,
  56.                     double rdistance, bool directed, bool has_reverse_cost,
  57.                     path_element_t **path, int *path_count, char **err_msg)
  58. {
  59.   typedef adjacency_list < listS, vecS, directedS, Vertex, Edge > graph_t;
  60.   typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
  61.   typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
  62.  
  63.   const unsigned int num_nodes = 1;
  64.  
  65.   graph_t graph( num_nodes );
  66.  
  67.   property_map<graph_t, edge_weight_t>::type weightmap =
  68.     get(edge_weight, graph);
  69.  
  70.   for (std::size_t j = 0; j < count; ++j)
  71.     {
  72.       graph_add_edge<graph_t, edge_descriptor>
  73.         (graph, edges[j].id, edges[j].source,
  74.          edges[j].target, edges[j].cost);
  75.  
  76.       if (!directed || (directed && has_reverse_cost))
  77.         {
  78.           if (has_reverse_cost)
  79.             {
  80.               graph_add_edge<graph_t, edge_descriptor>
  81.                 (graph, edges[j].id, edges[j].target,
  82.                  edges[j].source, edges[j].rcost);
  83.             }
  84.           else
  85.             {
  86.               graph_add_edge<graph_t, edge_descriptor>
  87.                 (graph, edges[j].id, edges[j].target,
  88.                  edges[j].source, edges[j].cost);
  89.             }
  90.         }
  91.     }
  92.  
  93.   vertex_descriptor source_vertex = vertex( source_vertex_id, graph );
  94.  
  95.   std::vector<vertex_descriptor> predecessors(num_vertices(graph));
  96.   std::vector<float8> distances(num_vertices(graph));
  97.  
  98.   dijkstra_shortest_paths(graph, source_vertex,
  99.                           predecessor_map(&predecessors[0])
  100.                           .weight_map(get(&Edge::cost, graph))
  101.                           .distance_map(&distances[0]));
  102.  
  103.  
  104.   graph_traits < graph_t >::vertex_iterator vi, vend;
  105.   vector<path_element> path_vector;
  106.   int j=0;
  107.  
  108.   for(tie(vi, vend) = vertices(graph); vi != vend; vi++) {
  109.  
  110.     if( (double)distances[*vi] <= rdistance ) {
  111.  
  112.       path_element pe;
  113.  
  114.       graph_traits<graph_t>::vertex_descriptor s;
  115.       graph_traits<graph_t>::vertex_descriptor p;
  116.  
  117.       s = vertex(*vi, graph);
  118.       p = vertex(predecessors[*vi], graph);
  119.  
  120.       pe.vertex_id = graph[s].id;
  121.       pe.parent_id = graph[p].id;
  122.       pe.edge_id   = graph[s].edge_id;
  123.       pe.cost      = distances[*vi];
  124.  
  125.       path_vector.push_back( pe );
  126.     }
  127.   }
  128.  
  129.   if( path_vector.size() == 0 ) {
  130.     *err_msg = (char *)"No path found";
  131.     return 0;
  132.   }
  133.  
  134.   vector<path_element>::iterator itr;
  135.   *path = (path_element_t *) malloc( sizeof(path_element_t) *
  136.                                      (path_vector.size() + 1) );
  137.   *path_count = path_vector.size();
  138.  
  139.   for(j=0,itr=path_vector.begin();itr != path_vector.end();itr++,j++) {
  140.     path_element pe = *itr;
  141.     (*path)[j].vertex_id = pe.vertex_id;
  142.     (*path)[j].parent_id = pe.parent_id;
  143.     (*path)[j].edge_id   = pe.edge_id;
  144.     (*path)[j].cost      = pe.cost;
  145.   }
  146.  
  147.   return EXIT_SUCCESS;
  148. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement