pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GraphDefinition.cpp
Go to the documentation of this file.
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 #if defined(__MINGW32__) || defined(_MSC_VER)
25 #include <winsock2.h>
26 #include <windows.h>
27 #undef min
28 #undef max
29 #endif
30 
31 
32 #include <sstream>
33 #include "GraphDefinition.h"
34 
35 // -------------------------------------------------------------------------
37  edge_t *edges,
38  unsigned int edge_count,
39  bool directed,
40  bool has_rcost) :
41  m_lStartEdgeId(-1),
42  m_lEndEdgeId(0),
43  m_dStartpart(0.0),
44  m_dEndPart(0.0),
45  m_edge_count(edge_count),
46  m_bIsturnRestrictOn(false),
47  m_bIsGraphConstructed(false) {
48  m_dCost.clear();
49  parent.clear();
50  init();
51  construct_graph(edges, has_rcost, directed);
52  m_bIsGraphConstructed = true;
53  }
54 
55 // -------------------------------------------------------------------------
57 
58 
59 // -------------------------------------------------------------------------
61  max_edge_id = 0;
62  max_node_id = 0;
63  isStartVirtual = false;
64  isEndVirtual = false;
65 }
66 
67 
68 // -------------------------------------------------------------------------
69 
71  m_vecEdgeVector.clear();
72 
73  parent.clear();
74  m_dCost.clear();
75 }
76 
77 
78 
79 
80 // -------------------------------------------------------------------------
81 double GraphDefinition::construct_path(int64_t ed_id, int64_t v_pos) {
82  if(parent[ed_id].ed_ind[v_pos] == -1) {
83  path_element_t pelement;
84  GraphEdgeInfo* cur_edge = &m_vecEdgeVector[ed_id];
85  if(v_pos == 0) {
86  pelement.vertex_id = cur_edge->m_lStartNode;
87  pelement.cost = cur_edge->m_dCost;
88  } else {
89  pelement.vertex_id = cur_edge->m_lEndNode;
90  pelement.cost = cur_edge->m_dReverseCost;
91  }
92  pelement.edge_id = cur_edge->m_lEdgeID;
93 
94  m_vecPath.push_back(pelement);
95  return pelement.cost;
96  }
97  double ret = construct_path(parent[ed_id].ed_ind[v_pos], parent[ed_id].v_pos[v_pos]);
98  path_element_t pelement;
99  GraphEdgeInfo* cur_edge = &m_vecEdgeVector[ed_id];
100  if(v_pos == 0) {
101  pelement.vertex_id = cur_edge->m_lStartNode;
102  pelement.cost = m_dCost[ed_id].endCost - ret;// cur_edge.m_dCost;
103  ret = m_dCost[ed_id].endCost;
104  } else {
105  pelement.vertex_id = cur_edge->m_lEndNode;
106  pelement.cost = m_dCost[ed_id].startCost - ret;
107  ret = m_dCost[ed_id].startCost;
108  }
109  pelement.edge_id = cur_edge->m_lEdgeID;
110 
111  m_vecPath.push_back(pelement);
112 
113  return ret;
114 }
115 
116 
117 // -------------------------------------------------------------------------
119  int64_t edge_ind,
120  GraphEdgeInfo& new_edge,
121  bool isStart) {
122  double cost = 0.0;
123  auto edge_id = new_edge.m_lEdgeID;
124  if(m_ruleTable.find(edge_id) == m_ruleTable.end()) {
125  return(0.0);
126  }
127  std::vector<Rule> vecRules = m_ruleTable[edge_id];
128  auto totalRule = vecRules.size();
129  auto st_edge_ind = edge_ind;
130  for(size_t ruleIndex = 0; ruleIndex < totalRule; ruleIndex++) {
131  bool flag = true;
132  auto total_edge = vecRules[ruleIndex].precedencelist.size();
133  int64_t v_pos = (isStart?0:1);
134  edge_ind = st_edge_ind;
135  for(size_t i = 0; i < total_edge; i++) {
136  if(edge_ind == -1) {
137  flag = false;
138  break;
139  }
140  if(vecRules[ruleIndex].precedencelist[i] != m_vecEdgeVector[edge_ind].m_lEdgeID) {
141  flag = false;
142  break;
143  }
144  auto parent_ind = parent[edge_ind].ed_ind[v_pos];
145  v_pos = parent[edge_ind].v_pos[v_pos];
146  edge_ind = parent_ind;
147  }
148  if(flag)
149  cost += vecRules[ruleIndex].cost;
150  }
151  return cost;
152 }
153 
154 
155 // -------------------------------------------------------------------------
157  int64_t cur_node,
158  GraphEdgeInfo &cur_edge,
159  bool isStart,
160  LongVector &vecIndex,
161  std::priority_queue<PDP, std::vector<PDP>,
162  std::greater<PDP> > &que) {
163  unsigned int i;
164  double extCost = 0.0;
165  GraphEdgeInfo new_edge;
166  // int new_node;
167  double totalCost;
168  for(i = 0; i < vecIndex.size(); i++) {
169  new_edge = m_vecEdgeVector[vecIndex[i]];
170  extCost = 0.0;
171  if(m_bIsturnRestrictOn) {
172  extCost = getRestrictionCost(cur_edge.m_lEdgeIndex, new_edge, isStart);
173  }
174  if(new_edge.m_lStartNode == cur_node) {
175  if(new_edge.m_dCost >= 0.0) {
176  //new_node = new_edge->m_lEndNode;
177 
178  if(isStart)
179  totalCost = m_dCost[cur_edge.m_lEdgeIndex].endCost + new_edge.m_dCost + extCost;
180  else
181  totalCost = m_dCost[cur_edge.m_lEdgeIndex].startCost + new_edge.m_dCost + extCost;
182  if(totalCost < m_dCost[vecIndex[i]].endCost) {
183  m_dCost[vecIndex[i]].endCost = totalCost;
184  parent[new_edge.m_lEdgeIndex].v_pos[0] = (isStart?0:1);
185  parent[new_edge.m_lEdgeIndex].ed_ind[0] = cur_edge.m_lEdgeIndex;
186  que.push(std::make_pair(totalCost, std::make_pair(new_edge.m_lEdgeIndex, true)));
187  }
188  }
189  } else {
190  if(new_edge.m_dReverseCost >= 0.0)
191  {
192  // new_node = new_edge->m_lStartNode;
193  if(isStart)
194  totalCost = m_dCost[cur_edge.m_lEdgeIndex].endCost + new_edge.m_dReverseCost + extCost;
195  else
196  totalCost = m_dCost[cur_edge.m_lEdgeIndex].startCost + new_edge.m_dReverseCost + extCost;
197  if(totalCost < m_dCost[vecIndex[i]].startCost)
198  {
199  m_dCost[vecIndex[i]].startCost = totalCost;
200  parent[new_edge.m_lEdgeIndex].v_pos[1] = (isStart?0:1);
201  parent[new_edge.m_lEdgeIndex].ed_ind[1] = cur_edge.m_lEdgeIndex;
202  que.push(std::make_pair(totalCost, std::make_pair(new_edge.m_lEdgeIndex, false)));
203  }
204  }
205  }
206  }
207 }
208 
209 
210 
211 // -------------------------------------------------------------------------
212  void
213 GraphDefinition::add_virtual_vertices(int start_edge_id, double start_part, int end_edge_id, double end_part,
214  int64_t &start_vertex, int64_t &end_vertex)
215 {
216  GraphEdgeInfo *start_edge_info = &m_vecEdgeVector[m_mapEdgeId2Index[start_edge_id]];
217  edge_t start_edge;
218  //int start_vertex, end_vertex;
219  m_dStartpart = start_part;
220  m_dEndPart = end_part;
221  m_lStartEdgeId = start_edge_id;
222  m_lEndEdgeId = end_edge_id;
223 
224  if(start_part == 0.0)
225  {
226  start_vertex = start_edge_info->m_lStartNode;
227  }
228  else if(start_part == 1.0)
229  {
230  start_vertex = start_edge_info->m_lEndNode;
231  }
232  else
233  {
234  isStartVirtual = true;
235  m_lStartEdgeId = start_edge_id;
236  start_vertex = max_node_id + 1;
237  max_node_id++;
238  start_edge.id = max_edge_id + 1;
239  max_edge_id++;
240  start_edge.source = start_vertex;
241  start_edge.reverse_cost = -1.0;
242  if(start_edge_info->m_dCost >= 0.0)
243  {
244  start_edge.target = start_edge_info->m_lEndNode;
245  start_edge.cost = (1.0 - start_part) * start_edge_info->m_dCost;
246  addEdge(start_edge);
247  m_edge_count++;
248  }
249  if(start_edge_info->m_dReverseCost >= 0.0)
250  {
251  start_edge.id = max_edge_id + 1;
252  max_edge_id++;
253  start_edge.target = start_edge_info->m_lStartNode;
254  start_edge.cost = start_part * start_edge_info->m_dReverseCost;
255  addEdge(start_edge);
256  m_edge_count++;
257  }
258  }
259 
260  GraphEdgeInfo *end_edge_info = &m_vecEdgeVector[m_mapEdgeId2Index[end_edge_id]];
261  edge_t end_edge;
262 
263  if(end_part == 0.0)
264  {
265  end_vertex = end_edge_info->m_lStartNode;
266  }
267  else if(end_part == 1.0)
268  {
269  end_vertex = end_edge_info->m_lEndNode;
270  }
271  else
272  {
273  isEndVirtual = true;
274  m_lEndEdgeId = end_edge_id;
275  end_vertex = max_node_id + 1;
276  max_node_id++;
277  end_edge.id = max_edge_id + 1;
278  max_edge_id++;
279  end_edge.target = end_vertex;
280  end_edge.reverse_cost = -1.0;
281  if(end_edge_info->m_dCost >= 0.0)
282  {
283  end_edge.source = end_edge_info->m_lStartNode;
284  end_edge.cost = end_part * end_edge_info->m_dCost;
285  addEdge(end_edge);
286  m_edge_count++;
287  }
288  if(end_edge_info->m_dReverseCost >= 0.0)
289  {
290  end_edge.source = end_edge_info->m_lEndNode;
291  end_edge.id = max_edge_id + 1;
292  end_edge.cost = (1.0 - end_part) * end_edge_info->m_dReverseCost;
293  addEdge(end_edge);
294  m_edge_count++;
295  }
296  }
297  //edge_count = m_edge_count;
298 }
299 
300 
301 // -------------------------------------------------------------------------
302  void
304  int64_t start_vertex,
305  int64_t end_vertex,
306  std::vector<PDVI> &ruleList) {
307  m_ruleTable.clear();
308  auto total_rule = ruleList.size();
309  LongVector vecsource;
310  unsigned int kk;
311  for(size_t i = 0; i < total_rule; i++)
312  {
313  Rule rule;
314  rule.cost = ruleList[i].first;
315  auto seq_cnt = ruleList[i].second.size();
316  for(size_t j = 1; j < seq_cnt; j++) {
317  rule.precedencelist.push_back(ruleList[i].second[j]);
318  }
319  auto dest_edge_id = ruleList[i].second[0];
320  if(m_ruleTable.find(dest_edge_id) != m_ruleTable.end()) {
321  m_ruleTable[dest_edge_id].push_back(rule);
322  } else {
323  std::vector<Rule> temprules;
324  temprules.clear();
325  temprules.push_back(rule);
326  m_ruleTable.insert(std::make_pair(dest_edge_id, temprules));
327  }
328 
329  if(isStartVirtual) {
330  if(seq_cnt == 2 && ruleList[i].second[1] == m_lStartEdgeId) {
331  vecsource = m_mapNodeId2Edge[start_vertex];
332  for(kk = 0; kk < vecsource.size(); kk++) {
333  rule.precedencelist.clear();
334  rule.precedencelist.push_back(m_vecEdgeVector[vecsource[kk]].m_lEdgeID);
335  m_ruleTable[dest_edge_id].push_back(rule);
336  }
337  }
338  }
339  }
340  if(isEndVirtual) {
341  if(m_ruleTable.find(m_lEndEdgeId) != m_ruleTable.end()) {
342  std::vector<Rule> tmpRules = m_ruleTable[m_lEndEdgeId];
343  vecsource = m_mapNodeId2Edge[end_vertex];
344  for(kk = 0; kk < vecsource.size(); kk++) {
345  m_ruleTable.insert(std::make_pair(m_vecEdgeVector[vecsource[kk]].m_lEdgeID, tmpRules));
346  }
347  }
348  }
349  m_bIsturnRestrictOn = true;
350 }
351 
352 // THIS ONE IS THE DIJKSTRA
353 // -------------------------------------------------------------------------
354 int GraphDefinition:: my_dijkstra(int64_t start_vertex, int64_t end_vertex,
355  path_element_t **path, size_t *path_count,
356  std::ostringstream &log) {
357 
358  std::priority_queue<PDP, std::vector<PDP>, std::greater<PDP> > que;
359  parent.resize(m_edge_count + 1);
360  m_dCost.resize(m_edge_count + 1);
361  m_vecPath.clear();
362 
363  for (auto &dcost : m_dCost) {
364  dcost.startCost = 1e15;
365  dcost.endCost = 1e15;
366  }
367 
368  if(m_mapNodeId2Edge.find(start_vertex) == m_mapNodeId2Edge.end())
369  {
370  log << "Source Not Found";
371  return -1;
372  }
373 
374  if(m_mapNodeId2Edge.find(end_vertex) == m_mapNodeId2Edge.end())
375  {
376  log << "Destination Not Found";
377  return -1;
378  }
379 
380  LongVector vecsource = m_mapNodeId2Edge[start_vertex];
381  GraphEdgeInfo *cur_edge = NULL;
382 
383  for (auto &s : vecsource)
384  {
385  GraphEdgeInfo *cur_edge = &m_vecEdgeVector[s];
386  if(cur_edge->m_lStartNode == start_vertex)
387  {
388  if(cur_edge->m_dCost >= 0.0)
389  {
390  m_dCost[cur_edge->m_lEdgeIndex].endCost= cur_edge->m_dCost;
391  parent[cur_edge->m_lEdgeIndex].v_pos[0] = -1;
392  parent[cur_edge->m_lEdgeIndex].ed_ind[0] = -1;
393  que.push(std::make_pair(cur_edge->m_dCost, std::make_pair(cur_edge->m_lEdgeIndex, true)));
394  }
395  } else {
396  if(cur_edge->m_dReverseCost >= 0.0)
397  {
398  m_dCost[cur_edge->m_lEdgeIndex].startCost = cur_edge->m_dReverseCost;
399  parent[cur_edge->m_lEdgeIndex].v_pos[1] = -1;
400  parent[cur_edge->m_lEdgeIndex].ed_ind[1] = -1;
401  que.push(std::make_pair(cur_edge->m_dReverseCost, std::make_pair(cur_edge->m_lEdgeIndex, false)));
402  }
403  }
404  }
405 
406  int64_t cur_node = -1;
407 
408  while(!que.empty()) {
409  PDP cur_pos = que.top();
410  que.pop();
411  int cured_index = cur_pos.second.first;
412  cur_edge = &m_vecEdgeVector[cured_index];
413 
414  if(cur_pos.second.second) {
415  // explore edges connected to end node
416  cur_node = cur_edge->m_lEndNode;
417  if(cur_edge->m_dCost < 0.0)
418  continue;
419  if(cur_node == end_vertex)
420  break;
421  explore(cur_node, *cur_edge, true, cur_edge->m_vecEndConnedtedEdge, que);
422  } else {
423  // explore edges connected to start node
424  cur_node = cur_edge->m_lStartNode;
425  if(cur_edge->m_dReverseCost < 0.0)
426  continue;
427  if(cur_node == end_vertex)
428  break;
429  explore(cur_node, *cur_edge, false, cur_edge->m_vecStartConnectedEdge, que);
430  }
431  }
432  if(cur_node != end_vertex) {
434  if(get_single_cost(1000.0, path, path_count)) {
435  return 0;
436  }
437  }
438  log << "Path Not Found";
439  *path=NULL;
440  path_count=0;
441  return 0;
442  } else {
443  double total_cost;
444  if(cur_node == cur_edge->m_lStartNode) {
445  total_cost = m_dCost[cur_edge->m_lEdgeIndex].startCost;
446  construct_path(cur_edge->m_lEdgeIndex, 1);
447  } else {
448  total_cost = m_dCost[cur_edge->m_lEdgeIndex].endCost;
449  construct_path(cur_edge->m_lEdgeIndex, 0);
450  }
451  path_element_t pelement;
452  pelement.vertex_id = end_vertex;
453  pelement.edge_id = -1;
454  pelement.cost = 0.0;
455  m_vecPath.push_back(pelement);
456 
458  {
459  if(get_single_cost(total_cost, path, path_count))
460  {
461  return 0;
462  }
463  }
464 
465  *path = (path_element_t *) malloc(sizeof(path_element_t) * (m_vecPath.size() + 1));
466  *path_count = m_vecPath.size();
467 
468  for(size_t i = 0; i < *path_count; i++)
469  {
470  (*path)[i].vertex_id = m_vecPath[i].vertex_id;
471  (*path)[i].edge_id = m_vecPath[i].edge_id;
472  (*path)[i].cost = m_vecPath[i].cost;
473  }
474  if(isStartVirtual)
475  {
476  (*path)[0].vertex_id = -1;
477  (*path)[0].edge_id = m_lStartEdgeId;
478  }
479  if(isEndVirtual)
480  {
481  *path_count = *path_count - 1;
482  (*path)[*path_count - 1].edge_id = m_lEndEdgeId;
483  }
484  }
485  return 0;
486 }
487 
488 
489 // -------------------------------------------------------------------------
491 {
493  if(m_dEndPart >= m_dStartpart)
494  {
495  if(start_edge_info->m_dCost >= 0.0 && start_edge_info->m_dCost * (m_dEndPart - m_dStartpart) <= total_cost)
496  {
497  *path = (path_element_t *) malloc(sizeof(path_element_t) * (1));
498  *path_count = 1;
499  (*path)[0].vertex_id = -1;
500  (*path)[0].edge_id = m_lStartEdgeId;
501  (*path)[0].cost = start_edge_info->m_dCost * (m_dEndPart - m_dStartpart);
502 
503  return true;
504  }
505  }
506  else
507  {
508  if(start_edge_info->m_dReverseCost >= 0.0 && start_edge_info->m_dReverseCost * (m_dStartpart - m_dEndPart) <= total_cost)
509  {
510  *path = (path_element_t *) malloc(sizeof(path_element_t) * (1));
511  *path_count = 1;
512  (*path)[0].vertex_id = -1;
513  (*path)[0].edge_id = m_lStartEdgeId;
514  (*path)[0].cost = start_edge_info->m_dReverseCost * (m_dStartpart - m_dEndPart);
515 
516  return true;
517  }
518  }
519  return false;
520 
521 }
522 
523 
524 // -------------------------------------------------------------------------
525 bool GraphDefinition::construct_graph(edge_t* edges, bool has_reverse_cost, bool directed) {
526  unsigned int i;
527  for(i = 0; i < m_edge_count; i++) {
528 
529  /*
530  * has_reverse_cost but cost is negative
531  * - flip the record
532  * - After this: cost is positive unless reverse_cost was also negative
533  */
534  if (has_reverse_cost) {
535  if (edges[i].cost < 0) {
536  auto tmp_v = edges[i].source;
537  edges[i].source = edges[i].target;
538  edges[i].target = tmp_v;
539  edges[i].cost = edges[i].reverse_cost;
540  edges[i].reverse_cost = -1.0;
541  }
542  }
543 
544  /*
545  * all data in the reverse_cost column must be ignored
546  */
547  if (!has_reverse_cost) {
548  edges[i].reverse_cost = -1.0;
549  }
550 
551  /*
552  * when the graph is undirected:
553  * both colummns must have the same smallest positive value
554  */
555  if (!directed && !has_reverse_cost) {
556  edges[i].reverse_cost = edges[i].cost;
557  } else if (!directed && has_reverse_cost) {
558  if (edges[i].reverse_cost < 0) {
559  edges[i].reverse_cost = edges[i].cost;
560  } else {
561  edges[i].reverse_cost = std::min(edges[i].reverse_cost, edges[i].cost);
562  }
563  }
564 
565  addEdge(edges[i]);
566  }
567  m_bIsGraphConstructed = true;
568  return true;
569 }
570 
571 
572 // -------------------------------------------------------------------------
573 bool GraphDefinition::connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo& secondEdge, bool bIsStartNodeSame)
574 {
575  if(bIsStartNodeSame)
576  {
577  if(firstEdge.m_dReverseCost >= 0.0)
578  firstEdge.m_vecStartConnectedEdge.push_back(secondEdge.m_lEdgeIndex);
579  if(firstEdge.m_lStartNode == secondEdge.m_lStartNode)
580  {
581  if(secondEdge.m_dReverseCost >= 0.0)
582  secondEdge.m_vecStartConnectedEdge.push_back(firstEdge.m_lEdgeIndex);
583  }
584  else
585  {
586  if(secondEdge.m_dCost >= 0.0)
587  secondEdge.m_vecEndConnedtedEdge.push_back(firstEdge.m_lEdgeIndex);
588  }
589  }
590  else
591  {
592  if(firstEdge.m_dCost >= 0.0)
593  firstEdge.m_vecEndConnedtedEdge.push_back(secondEdge.m_lEdgeIndex);
594  if(firstEdge.m_lEndNode == secondEdge.m_lStartNode)
595  {
596  if(secondEdge.m_dReverseCost >= 0.0)
597  secondEdge.m_vecStartConnectedEdge.push_back(firstEdge.m_lEdgeIndex);
598  }
599  else
600  {
601  if(secondEdge.m_dCost >= 0.0)
602  secondEdge.m_vecEndConnedtedEdge.push_back(firstEdge.m_lEdgeIndex);
603  }
604  }
605 
606  return true;
607 }
608 
609 
610 // -------------------------------------------------------------------------
612 {
613  // long lTest;
614  Long2LongMap::iterator itMap = m_mapEdgeId2Index.find(edgeIn.id);
615  if(itMap != m_mapEdgeId2Index.end())
616  return false;
617 
618 
619  GraphEdgeInfo newEdge(edgeIn.id, m_vecEdgeVector.size(),
620  edgeIn.source, edgeIn.target,edgeIn.cost, edgeIn.reverse_cost);
621  newEdge.m_vecStartConnectedEdge.clear();
622  newEdge.m_vecEndConnedtedEdge.clear();
623  newEdge.m_vecRestrictedEdge.clear();
624  newEdge.m_lEdgeID = edgeIn.id;
625  newEdge.m_lEdgeIndex = m_vecEdgeVector.size();
626  newEdge.m_lStartNode = edgeIn.source;
627  newEdge.m_lEndNode = edgeIn.target;
628  newEdge.m_dCost = edgeIn.cost;
629  newEdge.m_dReverseCost = edgeIn.reverse_cost;
630  if(edgeIn.id > max_edge_id) {
631  max_edge_id = edgeIn.id;
632  }
633 
634  if(newEdge.m_lStartNode > max_node_id) { max_node_id = newEdge.m_lStartNode;
635  }
636 
637  if(newEdge.m_lEndNode > max_node_id) { max_node_id = newEdge.m_lEndNode;
638  }
639 
640  //Searching the start node for connectivity
641  Long2LongVectorMap::iterator itNodeMap = m_mapNodeId2Edge.find(edgeIn.source);
642  if(itNodeMap != m_mapNodeId2Edge.end())
643  {
644  //Connect current edge with existing edge with start node
645  //connectEdge(
646  int64_t lEdgeCount = itNodeMap->second.size();
647  int64_t lEdgeIndex;
648  for(lEdgeIndex = 0; lEdgeIndex < lEdgeCount; lEdgeIndex++)
649  {
650  int64_t lEdge = itNodeMap->second.at(lEdgeIndex);
651  connectEdge(newEdge, m_vecEdgeVector[lEdge], true);
652  }
653  }
654 
655 
656  //Searching the end node for connectivity
657  itNodeMap = m_mapNodeId2Edge.find(edgeIn.target);
658  if(itNodeMap != m_mapNodeId2Edge.end())
659  {
660  //Connect current edge with existing edge with end node
661  //connectEdge(
662  int64_t lEdgeCount = itNodeMap->second.size();
663  int64_t lEdgeIndex;
664  for(lEdgeIndex = 0; lEdgeIndex < lEdgeCount; lEdgeIndex++)
665  {
666  int64_t lEdge = itNodeMap->second.at(lEdgeIndex);
667  connectEdge(newEdge, m_vecEdgeVector[lEdge], false);
668  }
669  }
670 
671 
672 
673  //Add this node and edge into the data structure
674  m_mapNodeId2Edge[edgeIn.source].push_back(newEdge.m_lEdgeIndex);
675  m_mapNodeId2Edge[edgeIn.target].push_back(newEdge.m_lEdgeIndex);
676 
677 
678  //Adding edge to the list
679  m_mapEdgeId2Index.insert(std::make_pair(newEdge.m_lEdgeID, m_vecEdgeVector.size()));
680  m_vecEdgeVector.push_back(newEdge);
681 
682  //
683 
684 
685  return true;
686 }
bool addEdge(edge_t edgeIn)
bool construct_graph(edge_t *edges, bool has_rcost, bool directed)
double reverse_cost
Definition: pgr_types.h:132
int path_count
Definition: BDATester.cpp:51
std::vector< PARENT_PATH > parent
double construct_path(int64_t ed_id, int64_t v_pos)
void set_restrictions(int64_t start_vertex, int64_t end_vertex, std::vector< PDVI > &ruleList)
int64_t source
Definition: pgr_types.h:129
int64_t target
Definition: pgr_types.h:130
GraphEdgeVector m_vecEdgeVector
int my_dijkstra(int64_t start_vertex, int64_t end_vertex, path_element_t **path, size_t *path_count, std::ostringstream &log)
void explore(int64_t cur_node, GraphEdgeInfo &cur_edge, bool isStart, LongVector &vecIndex, std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > &que)
std::vector< path_element_t > m_vecPath
RuleTable m_ruleTable
Long2LongMap m_mapEdgeId2Index
Long2LongVectorMap m_mapNodeId2Edge
bool get_single_cost(double total_cost, path_element_t **path, size_t *path_count)
std::vector< int64_t > precedencelist
void add_virtual_vertices(int start_edge, double start_part, int end_edge, double end_part, int64_t &start_vertex, int64_t &end_vertex)
bool connectEdge(GraphEdgeInfo &firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame)
int64_t id
Definition: pgr_types.h:128
double cost
Definition: pgr_types.h:131
int edge_count
Definition: BDATester.cpp:47
edge_astar_t * edges
Definition: BDATester.cpp:46
GraphDefinition(edge_t *edges, unsigned int edge_count, bool directed, bool has_rcost)
int64_t edge_id
Definition: pgr_types.h:75
path_element_t * path
Definition: BDATester.cpp:49
int64_t vertex_id
Definition: pgr_types.h:74
double getRestrictionCost(int64_t cur_node, GraphEdgeInfo &new_edge, bool isStart)
std::vector< CostHolder > m_dCost
std::vector< int64_t > LongVector
unsigned int m_edge_count
std::pair< double, PIB > PDP
double cost
Definition: pgr_types.h:76