PGROUTING  3.1
bdAstar_driver.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: bdAstar_driver.cpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 Function's developer:
9 Copyright (c) 2016 Celia Virginia Vergara Castillo
10 Mail: vicky_vergara@hotmail.com
11 
12 ------
13 
14 This program is free software; you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation; either version 2 of the License, or
17 (at your option) any later version.
18 
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23 
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 
28  ********************************************************************PGR-GNU*/
29 
31 
32 #include <sstream>
33 #include <deque>
34 #include <vector>
35 #include <algorithm>
36 
37 #include "bdAstar/pgr_bdAstar.hpp"
38 
39 #include "cpp_common/pgr_alloc.hpp"
40 #include "cpp_common/pgr_assert.h"
41 
42 
43 
44 
45 
46 /************************************************************
47  edges_sql TEXT,
48  start_vid BIGINT,
49  end_vid BIGINT,
50  directed BOOLEAN DEFAULT true,
51  only_cost BOOLEAN DEFAULT false,
52  ***********************************************************/
53 
54 template < class G >
55 static
56 std::deque<Path>
58  G &graph,
59  std::vector < int64_t > sources,
60  std::vector < int64_t > targets,
61 
62  int heuristic,
63  double factor,
64  double epsilon,
65  std::ostream &log,
66  bool only_cost) {
67  log << "entering static function\n";
68  std::sort(sources.begin(), sources.end());
69  sources.erase(
70  std::unique(sources.begin(), sources.end()),
71  sources.end());
72 
73  std::sort(targets.begin(), targets.end());
74  targets.erase(
75  std::unique(targets.begin(), targets.end()),
76  targets.end());
77 
78 
80  std::deque<Path> paths;
81  for (const auto source : sources) {
82  for (const auto target : targets) {
83  if (source == target) {
84  paths.push_back(Path(source, target));
85  continue;
86  }
87 
88  if (!graph.has_vertex(source)
89  || !graph.has_vertex(target)) {
90  paths.push_back(Path(source, target));
91  continue;
92  }
93 
94  fn_bdAstar.clear();
95  paths.push_back(fn_bdAstar.pgr_bdAstar(
96  graph.get_V(source), graph.get_V(target),
97  heuristic, factor, epsilon, only_cost));
98  }
99  }
100  log << fn_bdAstar.log();
101 
102  return paths;
103 }
104 
105 
106 void
108  Pgr_edge_xy_t *edges,
109  size_t total_edges,
110  int64_t *start_vidsArr,
111  size_t size_start_vidsArr,
112  int64_t *end_vidsArr,
113  size_t size_end_vidsArr,
114 
115 
116  bool directed,
117  int heuristic,
118  double factor,
119  double epsilon,
120  bool only_cost,
121 
122  General_path_element_t **return_tuples,
123  size_t *return_count,
124 
125  char ** log_msg,
126  char ** notice_msg,
127  char ** err_msg) {
128  std::ostringstream log;
129  std::ostringstream err;
130  std::ostringstream notice;
131  try {
132  pgassert(!(*log_msg));
133  pgassert(!(*notice_msg));
134  pgassert(!(*err_msg));
135  pgassert(!(*return_tuples));
136  pgassert(*return_count == 0);
137  pgassert(total_edges != 0);
138 
139 
140  log << "Inserting vertices into a c++ vector structure";
141  std::vector<int64_t>
142  start_vertices(start_vidsArr, start_vidsArr + size_start_vidsArr);
143  std::vector< int64_t >
144  end_vertices(end_vidsArr, end_vidsArr + size_end_vidsArr);
145 
146  graphType gType = directed? DIRECTED: UNDIRECTED;
147 
148  std::deque<Path> paths;
149  log << "starting process\n";
150  if (directed) {
151  log << "Working with directed Graph\n";
153  pgrouting::extract_vertices(edges, total_edges),
154  gType);
155  digraph.insert_edges(edges, total_edges);
156 
157  paths = pgr_bdAstar(digraph,
158  start_vertices,
159  end_vertices,
160  heuristic,
161  factor,
162  epsilon,
163  log,
164  only_cost);
165  } else {
166  log << "Working with Undirected Graph\n";
168  pgrouting::extract_vertices(edges, total_edges),
169  gType);
170  undigraph.insert_edges(edges, total_edges);
171 
172  paths = pgr_bdAstar(
173  undigraph,
174  start_vertices,
175  end_vertices,
176  heuristic,
177  factor,
178  epsilon,
179  log,
180  only_cost);
181  }
182 
183  size_t count(0);
184  count = count_tuples(paths);
185 
186  if (count == 0) {
187  (*return_tuples) = NULL;
188  (*return_count) = 0;
189  notice <<
190  "No paths found";
191  *log_msg = pgr_msg(notice.str().c_str());
192  return;
193  }
194 
195  (*return_tuples) = pgr_alloc(count, (*return_tuples));
196  log << "\nConverting a set of paths into the tuples";
197  (*return_count) = (collapse_paths(return_tuples, paths));
198 
199 
200 #if 0
201  auto count = path.size();
202 
203  if (count == 0) {
204  (*return_tuples) = NULL;
205  (*return_count) = 0;
206  notice <<
207  "No paths found between start_vid and end_vid vertices";
208  } else {
209  (*return_tuples) = pgr_alloc(count, (*return_tuples));
210  size_t sequence = 0;
211  path.generate_postgres_data(return_tuples, sequence);
212  (*return_count) = sequence;
213  }
214 #endif
215 
216  pgassert(*err_msg == NULL);
217  *log_msg = log.str().empty()?
218  nullptr :
219  pgr_msg(log.str().c_str());
220  *notice_msg = notice.str().empty()?
221  nullptr :
222  pgr_msg(notice.str().c_str());
223  } catch (AssertFailedException &except) {
224  if (*return_tuples) free(*return_tuples);
225  (*return_count) = 0;
226  err << except.what();
227  *err_msg = pgr_msg(err.str().c_str());
228  *log_msg = pgr_msg(log.str().c_str());
229  } catch (std::exception& except) {
230  if (*return_tuples) free(*return_tuples);
231  (*return_count) = 0;
232  err << except.what();
233  *err_msg = pgr_msg(err.str().c_str());
234  *log_msg = pgr_msg(log.str().c_str());
235  } catch(...) {
236  if (*return_tuples) free(*return_tuples);
237  (*return_count) = 0;
238  err << "Caught unknown exception!";
239  *err_msg = pgr_msg(err.str().c_str());
240  *log_msg = pgr_msg(log.str().c_str());
241  }
242 }
Extends std::exception and is the exception that we throw if an assert fails.
Definition: pgr_assert.h:139
void do_pgr_bdAstar(Pgr_edge_xy_t *edges, size_t total_edges, int64_t *start_vidsArr, size_t size_start_vidsArr, int64_t *end_vidsArr, size_t size_end_vidsArr, bool directed, int heuristic, double factor, double epsilon, bool only_cost, General_path_element_t **return_tuples, size_t *return_count, char **log_msg, char **notice_msg, char **err_msg)
size_t collapse_paths(General_path_element_t **ret_path, const std::deque< Path > &paths)
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
static std::deque< Path > pgr_bdAstar(G &graph, std::vector< int64_t > sources, std::vector< int64_t > targets, int heuristic, double factor, double epsilon, std::ostream &log, bool only_cost)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
char * pgr_msg(const std::string &msg)
Definition: pgr_alloc.cpp:30
size_t count_tuples(const std::deque< Path > &paths)
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:66
Path pgr_bdAstar(V start_vertex, V end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
Definition: pgr_bdAstar.hpp:86
Assertions Handling.
virtual const char * what() const
Definition: pgr_assert.cpp:67
graphType
Definition: graph_enum.h:30
void insert_edges(const T *edges, size_t count)
Inserts count edges of type T into the graph.