PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_withPoints.hpp File Reference
#include <vector>
#include "c_types/point_on_edge_t.h"
#include "cpp_common/basePath_SSEC.hpp"
Include dependency graph for pgr_withPoints.hpp:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

void adjust_pids (const std::vector< Point_on_edge_t > &points, Path &path)
 
int check_points (std::vector< Point_on_edge_t > &points, std::ostringstream &log)
 
bool create_new_edges (std::vector< Point_on_edge_t > &points, const std::vector< pgr_edge_t > &edges, char driving_side, std::vector< pgr_edge_t > &new_edges)
 
bool create_new_edges (std::vector< Point_on_edge_t > &points, const std::vector< pgr_edge_t > &edges, char driving_side, std::vector< pgr_edge_t > &new_edges, std::ostringstream &log)
 
void eliminate_details (Path &path, const std::vector< pgr_edge_t > &point_edges)
 
void eliminate_details_dd (Path &path)
 

Function Documentation

void adjust_pids ( const std::vector< Point_on_edge_t > &  points,
Path path 
)

Definition at line 192 of file pgr_withPoints.cpp.

References adjust_pids(), Path::empty(), Path::end_id(), and Path::start_id().

194  {
195  /*
196  * There is no path nothing to do
197  */
198  if (path.empty()) return;
199  /* from, to:
200  * * are constant along the path
201  * */
202  int64_t start_vid = path.start_id();
203  int64_t end_vid = path.end_id();
204 
205  int64_t start_pid = 0;
206  int64_t end_pid = 0;
207 
208  for (auto &p : points) {
209  if (p.vertex_id == start_vid) {
210  start_pid = -p.pid;
211  }
212  if (p.vertex_id == end_vid) {
213  end_pid = -p.pid;
214  }
215  }
216  adjust_pids(points, start_pid, end_pid, path);
217 }
static void adjust_pids(const std::vector< Point_on_edge_t > &points, const int64_t &start_pid, const int64_t &end_pid, Path &path)
int64_t end_id() const
int64_t start_id() const
bool empty() const

Here is the call graph for this function:

int check_points ( std::vector< Point_on_edge_t > &  points,
std::ostringstream &  log 
)

Definition at line 63 of file pgr_withPoints.cpp.

References Point_on_edge_t::edge_id, Point_on_edge_t::fraction, PGR_LOG_POINTS(), Point_on_edge_t::pid, and Point_on_edge_t::side.

Referenced by do_pgr_many_withPointsDD(), do_pgr_withPoints(), and do_pgr_withPointsKsp().

64  {
65  PGR_LOG_POINTS(log, points, "original points");
66  /*
67  * deleting duplicate points
68  */
69  std::sort(points.begin(), points.end(),
70  [](const Point_on_edge_t &a, const Point_on_edge_t &b)
71  -> bool {
72  if (a.pid != b.pid) return a.pid < b.pid;
73  if (a.edge_id != b.edge_id) return a.edge_id < b.edge_id;
74  if (a.fraction != b.fraction) return a.fraction < b.fraction;
75  return a.side < b.side;
76  });
77  PGR_LOG_POINTS(log, points, "after sorting");
78  auto last = std::unique(points.begin(), points.end(),
79  [](const Point_on_edge_t &a, const Point_on_edge_t &b) {
80  return a.pid == b.pid &&
81  a.edge_id == b.edge_id &&
82  a.fraction == b.fraction &&
83  a.side == b.side;
84  });
85  points.erase(last, points.end());
86  size_t total_points = points.size();
87 
88  PGR_LOG_POINTS(log, points, "after deleting repetitions");
89  log << "We have " << total_points << " different points";
90 
91  last = std::unique(points.begin(), points.end(),
92  [](const Point_on_edge_t &a, const Point_on_edge_t &b) {
93  return a.pid == b.pid;
94  });
95  points.erase(last, points.end());
96  PGR_LOG_POINTS(log, points, "after deleting points with same id");
97 
98  if (points.size() != total_points) {
99  return 1;
100  }
101  return 0;
102 }
static void PGR_LOG_POINTS(std::ostringstream &log, const std::vector< Point_on_edge_t > &points, const std::string &title)

Here is the call graph for this function:

Here is the caller graph for this function:

bool create_new_edges ( std::vector< Point_on_edge_t > &  points,
const std::vector< pgr_edge_t > &  edges,
char  driving_side,
std::vector< pgr_edge_t > &  new_edges 
)

Definition at line 228 of file pgr_withPoints.cpp.

References create_new_edges().

Referenced by create_new_edges(), do_pgr_many_withPointsDD(), do_pgr_withPoints(), and do_pgr_withPointsKsp().

232  {
233  std::ostringstream log;
234  return create_new_edges( points, edges, driving_side, new_edges, log);
235 }
bool create_new_edges(std::vector< Point_on_edge_t > &points, const std::vector< pgr_edge_t > &edges, char driving_side, std::vector< pgr_edge_t > &new_edges)

Here is the call graph for this function:

Here is the caller graph for this function:

bool create_new_edges ( std::vector< Point_on_edge_t > &  points,
const std::vector< pgr_edge_t > &  edges,
char  driving_side,
std::vector< pgr_edge_t > &  new_edges,
std::ostringstream &  log 
)

Definition at line 240 of file pgr_withPoints.cpp.

References edge::cost, pgr_edge_t::cost, edge::id, pgr_edge_t::id, pgassert, edge::reverse_cost, pgr_edge_t::reverse_cost, edge::source, pgr_edge_t::source, edge::target, and pgr_edge_t::target.

245  {
246  for (const auto &point : points) {
247  log << "point: "
248  << point.pid << "\t"
249  << point.edge_id << "\t"
250  << point.fraction << "\t"
251  << point.side << "\t"
252  << point.vertex_id << "\n";
253  }
254 
255  int64_t vertex_id = 1;
256  std::vector< Point_on_edge_t > new_points;
257  for (const auto edge : edges) {
258  std::set< Point_on_edge_t, pointCompare> points_on_edge;
259  for (const auto point : points) {
260  if (edge.id == point.edge_id) {
261  points_on_edge.insert(point);
262  log << "working points: "
263  << point.pid << "\t"
264  << point.edge_id << "\t"
265  << point.fraction << "\t"
266  << point.side << "\t"
267  << point.vertex_id << "\n";
268  }
269  }
270  if (points_on_edge.empty()) {
271  log << "For some reason didn't find a point belonging to the edge"
272  << ", must be an error\n";
273  return false;
274  }
275 #if 0
276  log << "breaking: \n"
277  << edge.id << "\t"
278  << edge.source << "\t"
279  << edge.target << "\t"
280  << edge.cost << "\t"
281  << edge.reverse_cost << "\n";
282 #endif
283  int64_t prev_target = edge.source;
284  int64_t prev_rtarget = edge.source;
285  double prev_fraction = 0;
286  double prev_rfraction = 0;
287  double agg_cost = 0;
288  double agg_rcost = 0;
289  double last_cost = 0;
290  double last_rcost = 0;
291  std::vector<Point_on_edge_t> the_points(
292  points_on_edge.begin(), points_on_edge.end());
293 
294  for (auto &point : the_points) {
295  /* the point either has
296  * vertex_id = source
297  * vertex_id = target
298  * vertex_id = -newnumber
299  */
300  log << "\npid"
301  << point.pid
302  << "\teid" << point.edge_id
303  << "/t" << point.fraction
304  << "\t" << point.side << "\n";
305  if (point.fraction <= 0 || point.fraction >= 1) {
306  log << "For some reason an invalid fraction was accepted,"
307  << " must be an error\n";
308  return false;
309  }
310  if (point.fraction == 0) {
311  log << "Point's vertex_id = source" << edge.source << "\n";
312  point.vertex_id = edge.source;
313  }
314  if (point.fraction == 1) {
315  log << "point's vertex_id = target" << edge.target << "\n";
316  point.vertex_id = edge.target;
317  }
318  if (point.fraction > 0 && point.fraction < 1) {
319  log << "vertex_id of the point is " << -point.pid << "\n";
320  point.vertex_id = -point.pid;
321  ++vertex_id;
322  }
323  new_points.push_back(point);
324 
325  double deltaFraction = point.fraction - prev_fraction;
326  double deltarFraction = point.fraction - prev_rfraction;
327  if ((edge.cost < 0 || edge.reverse_cost < 0)
328  || driving_side == 'b'
329  || point.side == 'b') {
330  log << "Edge is one way "
331  << " or driving side is both or point side is both\n";
332  log << "Edge is one way: "
333  << (edge.cost < 0 || edge.reverse_cost < 0)
334  << "\n";
335  log << "driving side: " << driving_side << "\n";
336  log << "point side: " << point.side << "\n";
337  if (point.fraction > 0 && point.fraction < 1) {
338  if (edge.cost >= 0) {
339  last_cost = deltaFraction * edge.cost;
340  pgr_edge_t new_edge = {
341  edge.id,
342  prev_target,
343  point.vertex_id,
344  last_cost,
345  -1};
346  new_edges.push_back(new_edge);
347  log << "new_edge("
348  << "id, source, target, cost, reverse_cost) = ("
349  << new_edge.id << "\t"
350  << new_edge.source << "\t"
351  << new_edge.target << "\t"
352  << new_edge.cost << "\t"
353  << new_edge.reverse_cost << ")\n";
354  }
355  if (edge.reverse_cost >= 0) {
356  last_rcost = deltarFraction * edge.reverse_cost;
357  pgr_edge_t new_edge = {
358  edge.id,
359  prev_target,
360  point.vertex_id,
361  -1,
362  last_rcost};
363  new_edges.push_back(new_edge);
364  log << "new_edge("
365  << "id, source, target, cost, reverse_cost) = ("
366  << new_edge.id << "\t"
367  << new_edge.source << "\t"
368  << new_edge.target << "\t"
369  << new_edge.cost << "\t"
370  << new_edge.reverse_cost << ")\n";
371  }
372  }
373  prev_target = point.vertex_id;
374  prev_fraction = point.fraction;
375  agg_cost += last_cost;
376 
377  prev_rtarget = point.vertex_id;
378  prev_rfraction = point.fraction;
379  agg_rcost += last_rcost;
380  continue;
381  }
382 
383  pgassert(edge.cost > 0 && edge.reverse_cost > 0);
384  pgassert(point.side != 'b');
385 
386  if (driving_side == point.side) {
387  log << "two way and driving side == the side of the point\n";
388  log << "Breaking (source, target) when its not the extreme\n";
389  if (point.fraction > 0 && point.fraction < 1) {
390  last_cost = deltaFraction * edge.cost;
391  pgr_edge_t new_edge = {
392  edge.id, prev_target, point.vertex_id, last_cost, -1};
393  new_edges.push_back(new_edge);
394  log << "new_edge("
395  << "id, source, target, cost, reverse_cost) = ("
396  << new_edge.id << "\t"
397  << new_edge.source << "\t"
398  << new_edge.target << "\t"
399  << new_edge.cost << "\t"
400  << new_edge.reverse_cost << ")\n";
401  }
402  prev_target = point.vertex_id;
403  prev_fraction = point.fraction;
404  agg_cost += last_cost;
405  continue;
406  }
407 
408  log << "\ntwo way and driving side != the side of the point";
409  if (point.fraction > 0 && point.fraction < 1) {
410  last_rcost = deltarFraction * edge.reverse_cost;
411  pgr_edge_t new_edge = {
412  edge.id,
413  prev_rtarget,
414  point.vertex_id,
415  -1,
416  last_rcost};
417  new_edges.push_back(new_edge);
418  log << "\nnew_edge(id, source, target, cost, reverse_cost) = ("
419  << new_edge.id << "\t"
420  << new_edge.source << "\t"
421  << new_edge.target << "\t"
422  << new_edge.cost << "\t"
423  << new_edge.reverse_cost << ")\n";
424  }
425  prev_rtarget = point.vertex_id;
426  prev_rfraction = point.fraction;
427  agg_rcost += last_rcost;
428  }
429 
430  { // the last segments
431  pgr_edge_t new_edge = {
432  edge.id,
433  prev_target,
434  edge.target,
435  (edge.cost - agg_cost),
436  -1};
437  new_edges.push_back(new_edge);
438  log << "last edge: (id, source, target, cost, reverse_cost) = ("
439  << new_edge.id << "\t"
440  << new_edge.source << "\t"
441  << new_edge.target << "\t"
442  << new_edge.cost << "\t"
443  << new_edge.reverse_cost << ")\n";
444 
445  new_edge = {edge.id , prev_rtarget, edge.target,
446  -1, (edge.reverse_cost - agg_rcost)};
447  new_edges.push_back(new_edge);
448  log << "last edge: (id, source, target, cost, reverse_cost) = ("
449  << new_edge.id << "\t"
450  << new_edge.source << "\t"
451  << new_edge.target << "\t"
452  << new_edge.cost << "\t"
453  << new_edge.reverse_cost << ")\n";
454  }
455  }
456 
457  points = new_points;
458  for (const auto &point : points) {
459  log << "point: "
460  << point.pid << "\t"
461  << point.edge_id << "\t"
462  << point.fraction << "\t"
463  << point.side << "\t"
464  << point.vertex_id << "\n";
465  }
466  return true;
467 }
float8 cost
Definition: trsp.h:35
double reverse_cost
Definition: pgr_edge_t.h:63
Definition: trsp.h:31
int64_t source
Definition: pgr_edge_t.h:60
int64_t target
Definition: pgr_edge_t.h:61
long id
Definition: trsp.h:32
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t id
Definition: pgr_edge_t.h:59
double cost
Definition: pgr_edge_t.h:62
long target
Definition: trsp.h:34
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33
void eliminate_details ( Path path,
const std::vector< pgr_edge_t > &  point_edges 
)

Definition at line 127 of file pgr_withPoints.cpp.

References Path::empty(), Path::end_id(), edge::id, Path::push_back(), and Path::start_id().

Referenced by do_pgr_withPoints(), and do_pgr_withPointsKsp().

129  {
130  /*
131  * There is no path nothing to do
132  */
133  if (path.empty()) return;
134 
135  Path newPath(path.start_id(), path.end_id());
136  double cost = 0.0;
137  for (const auto &pathstop : path) {
138  if ((pathstop.node == path.start_id())
139  || (pathstop.node == path.end_id())
140  || (pathstop.node > 0)) {
141  newPath.push_back(pathstop);
142  if (pathstop.node != path.end_id()) cost = 0.0;
143  continue;
144  }
145  cost += pathstop.cost;
146  }
147 
148  newPath[0].cost = newPath[1].agg_cost;
149  for (unsigned int i = 1; i < newPath.size() - 2; ++i) {
150  /* newPath[i] has: node, edge, cost, agg_cost
151  * pgr_type_t has: id, source, target, cost, reverse_cost
152  *
153  * find the edge where the pathstop.edge == edge.id */
154 
155  int64_t edge_to_find = newPath[i].edge;
156  auto edge_ptr = std::find_if(point_edges.begin(), point_edges.end(),
157  [&edge_to_find](const pgr_edge_t &edge)
158  {return edge_to_find == edge.id;});
159  if (edge_ptr != point_edges.end()) {
160  newPath[i].cost = edge_ptr->target == newPath[i+1].node ?
161  edge_ptr->cost : edge_ptr->reverse_cost;
162  }
163  }
164  newPath[newPath.size()-2].cost += cost;
165 
166 
167  path = newPath;
168 }
Definition: trsp.h:31
long id
Definition: trsp.h:32
void push_back(Path_t data)
int64_t end_id() const
int64_t start_id() const
bool empty() const

Here is the call graph for this function:

Here is the caller graph for this function:

void eliminate_details_dd ( Path path)

Definition at line 106 of file pgr_withPoints.cpp.

References Path::empty(), Path::end_id(), Path::push_back(), and Path::start_id().

Referenced by do_pgr_many_withPointsDD().

107  {
108  /*
109  * There is no path nothing to do
110  */
111  if (path.empty()) return;
112 
113  Path newPath(path.start_id(), path.end_id());
114  for (const auto &pathstop : path) {
115  if ((pathstop.node == path.start_id())
116  || (pathstop.node == path.end_id())
117  || (pathstop.node > 0)) {
118  newPath.push_back(pathstop);
119  }
120  }
121 
122  path = newPath;
123 }
void push_back(Path_t data)
int64_t end_id() const
int64_t start_id() const
bool empty() const

Here is the call graph for this function:

Here is the caller graph for this function: