pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
boost_wrapper.cpp
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 ------
7 
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12 
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 
22 ********************************************************************PGR-GNU*/
23 /*
24  * Shortest path algorithm for PostgreSQL
25  *
26  * Copyright (c) 2005 Sylvain Pasche
27  *
28  * This program is free software; you can redistribute it and/or modify
29  * it under the terms of the GNU General Public License as published by
30  * the Free Software Foundation; either version 2 of the License, or
31  * (at your option) any later version.
32  *
33  * This program is distributed in the hope that it will be useful,
34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
36  * GNU General Public License for more details.
37  *
38  * You should have received a copy of the GNU General Public License
39  * along with this program; if not, write to the Free Software
40  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
41  *
42  */
43 
44 // Include C header first for windows build issue
45 #include "dijkstra.h"
46 #include <cfloat>
47 
48 #include <boost/config.hpp>
49 
50 #include <boost/graph/graph_traits.hpp>
51 #include <boost/graph/adjacency_list.hpp>
52 #include <boost/graph/dijkstra_shortest_paths.hpp>
53 
54 using namespace std;
55 using namespace boost;
56 
57 // Maximal number of nodes in the path (to avoid infinite loops)
58 #define MAX_NODES 100000000
59 
60 struct Vertex
61 {
62  int id;
63  float8 cost;
64 };
65 
66 
67 int
68 boost_dijkstra(edge_t *edges, unsigned int count, int start_vertex, int end_vertex,
69  bool directed, bool has_reverse_cost,
70  path_element_t **path, int *path_count, char **err_msg)
71 {
72 try {
73 
74  // FIXME: use a template for the directedS parameters
75  typedef adjacency_list < listS, vecS, directedS, no_property, Vertex> graph_t;
76 
77  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
78  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
79  typedef std::pair<int, int> Edge;
80 
81  // FIXME: compute this value
82  const unsigned int num_nodes = ((directed && has_reverse_cost ? 2 : 1) * count) + 100;
83 
84  graph_t graph(num_nodes);
85 
86  // commented out to fix APPLE build, is it needed?
87  //property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, graph);
88 
89  for (std::size_t j = 0; j < count; ++j)
90  {
91  double cost, rcost;
92  edge_descriptor e;
93  bool inserted;
94 
95  tie(e, inserted) = add_edge(edges[j].source, edges[j].target, graph);
96 
97  cost = (edges[j].cost < 0.0) ? DBL_MAX : edges[j].cost;
98  graph[e].cost = cost;
99  graph[e].id = edges[j].id;
100 
101  if (!directed || (directed && has_reverse_cost))
102  {
103  tie(e, inserted) = add_edge(edges[j].target, edges[j].source, graph);
104  graph[e].id = edges[j].id;
105 
106  if (has_reverse_cost)
107  {
108  rcost = (edges[j].reverse_cost < 0.0) ? DBL_MAX : edges[j].reverse_cost;
109  graph[e].cost = rcost;
110  }
111  else
112  {
113  graph[e].cost = cost;
114  }
115  }
116  }
117 
118  std::vector<vertex_descriptor> predecessors(num_vertices(graph));
119 
120  vertex_descriptor _source = vertex(start_vertex, graph);
121 
122  if (_source < 0 /*|| _source >= num_nodes*/)
123  {
124  *err_msg = (char *) "Starting vertex not found";
125  return -1;
126  }
127 
128  vertex_descriptor _target = vertex(end_vertex, graph);
129  if (_target < 0 /*|| _target >= num_nodes*/)
130  {
131  *err_msg = (char *) "Ending vertex not found";
132  return -1;
133  }
134 
135  std::vector<float8> distances(num_vertices(graph));
136  // calling Boost function
137  dijkstra_shortest_paths(graph, _source,
138  predecessor_map(&predecessors[0]).
139  weight_map(get(&Vertex::cost, graph))
140  .distance_map(&distances[0]));
141 
142  vector<int> path_vect;
143  int max = MAX_NODES;
144  path_vect.push_back(_target);
145 
146  while (_target != _source)
147  {
148  if (_target == predecessors[_target])
149  {
150  *err_msg = (char *) "No path found";
151  return 0;
152  }
153  _target = predecessors[_target];
154 
155  path_vect.push_back(_target);
156  if (!max--)
157  {
158  *err_msg = (char *) "Overflow";
159  return -1;
160  }
161  }
162 
163  *path = (path_element_t *) malloc(sizeof(path_element_t) * (path_vect.size() + 1));
164  *path_count = path_vect.size();
165 
166  for(int i = path_vect.size() - 1, j = 0; i >= 0; i--, j++)
167  {
168  graph_traits < graph_t >::vertex_descriptor v_src;
169  graph_traits < graph_t >::vertex_descriptor v_targ;
170  graph_traits < graph_t >::edge_descriptor e;
171  graph_traits < graph_t >::out_edge_iterator out_i, out_end;
172 
173  (*path)[j].vertex_id = path_vect.at(i);
174 
175  (*path)[j].edge_id = -1;
176  (*path)[j].cost = distances[_target];
177 
178  if (i == 0)
179  {
180  continue;
181  }
182 
183  v_src = path_vect.at(i);
184  v_targ = path_vect.at(i - 1);
185  double cost = 99999999.9;
186  int edge_id = 0;
187 
188  for (tie(out_i, out_end) = out_edges(v_src, graph);
189  out_i != out_end; ++out_i)
190  {
191  graph_traits < graph_t >::vertex_descriptor v, targ;
192  e = *out_i;
193  v = source(e, graph);
194  targ = target(e, graph);
195 
196  if (targ == v_targ)
197  {
198  // if there are multiple parallel edges get the lowest cost
199  if (graph[*out_i].cost < cost)
200  {
201  edge_id = graph[*out_i].id;
202  cost = graph[*out_i].cost;
203  }
204  }
205  }
206  (*path)[j].edge_id = edge_id;
207  (*path)[j].cost = cost;
208  }
209 
210  return EXIT_SUCCESS;
211  }
212  catch(...) {
213  *err_msg = (char *) "Unknown exception caught!";
214  return -1;
215  }
216 }
Definition: alpha.h:33