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