Boost Graph Problem

a guest
Jun 29th, 2011
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2.  *
3.  */
4.
5. #include <boost/config.hpp>
6.
7. #include <boost/graph/graph_traits.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.     {
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.             {
81.                 (graph, edges[j].id, edges[j].target,
82.                  edges[j].source, edges[j].rcost);
83.             }
84.           else
85.             {
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. }