PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GraphDefinition.cpp
Go to the documentation of this file.
1 
2 #ifdef __MINGW32__
3 #include <winsock2.h>
4 #include <windows.h>
5 #endif
6 
7 
8 #include <functional>
9 #include "GraphDefinition.h"
10 
11 // -------------------------------------------------------------------------
13 {
14  m_lStartEdgeId = -1;
15  m_lEndEdgeId = 0;
16  m_dStartpart = 0.0;
17  m_dEndPart = 0.0;
18  m_dCost = NULL;
19  m_bIsturnRestrictOn = false;
20  m_bIsGraphConstructed = false;
21  parent = NULL;
22  init();
23 }
24 
25 // -------------------------------------------------------------------------
27 {
28 }
29 
30 
31 // -------------------------------------------------------------------------
33 {
34  max_edge_id = 0;
35  max_node_id = 0;
36  isStartVirtual = false;
37  isEndVirtual = false;
38 }
39 
40 
41 // -------------------------------------------------------------------------
43 {
44  std::vector<GraphEdgeInfo*>::iterator it;
45  for(it = m_vecEdgeVector.begin(); it != m_vecEdgeVector.end(); it++){
46  delete *it;
47  }
48  m_vecEdgeVector.clear();
49 
50  delete [] parent;
51  delete [] m_dCost;
52 }
53 
54 
55 // -------------------------------------------------------------------------
56 double GraphDefinition::construct_path(long ed_id, int v_pos)
57 {
58  if(parent[ed_id].ed_ind[v_pos] == -1)
59  {
60  path_element_t pelement;
61  GraphEdgeInfo* cur_edge = m_vecEdgeVector[ed_id];
62  if(v_pos == 0)
63  {
64  pelement.vertex_id = cur_edge->m_lStartNode;
65  pelement.cost = cur_edge->m_dCost;
66  }
67  else
68  {
69  pelement.vertex_id = cur_edge->m_lEndNode;
70  pelement.cost = cur_edge->m_dReverseCost;
71  }
72  pelement.edge_id = cur_edge->m_lEdgeID;
73 
74  m_vecPath.push_back(pelement);
75  return pelement.cost;
76  }
77  double ret = construct_path(parent[ed_id].ed_ind[v_pos], parent[ed_id].v_pos[v_pos]);
78  path_element_t pelement;
79  GraphEdgeInfo* cur_edge = m_vecEdgeVector[ed_id];
80  if(v_pos == 0)
81  {
82  pelement.vertex_id = cur_edge->m_lStartNode;
83  pelement.cost = m_dCost[ed_id].endCost - ret;// cur_edge.m_dCost;
84  ret = m_dCost[ed_id].endCost;
85  }
86  else
87  {
88  pelement.vertex_id = cur_edge->m_lEndNode;
89  pelement.cost = m_dCost[ed_id].startCost - ret;
90  ret = m_dCost[ed_id].startCost;
91  }
92  pelement.edge_id = cur_edge->m_lEdgeID;
93 
94  m_vecPath.push_back(pelement);
95 
96  return ret;
97 }
98 
99 
100 // -------------------------------------------------------------------------
102  long edge_ind,
103  GraphEdgeInfo& new_edge,
104  bool isStart)
105 {
106  double cost = 0.0;
107  long edge_id = new_edge.m_lEdgeID;
108  if(m_ruleTable.find(edge_id) == m_ruleTable.end())
109  {
110  return(0.0);
111  }
112  std::vector<Rule> vecRules = m_ruleTable[edge_id];
113  long st_edge_ind = edge_ind;
114  for(const auto &rule : vecRules)
115  {
116  bool flag = true;
117  int v_pos = (isStart?0:1);
118  edge_ind = st_edge_ind;
119  for(auto const &precedence : rule.precedencelist)
120  {
121  if(edge_ind == -1)
122  {
123  flag = false;
124  break;
125  }
126  if(precedence != m_vecEdgeVector[edge_ind]->m_lEdgeID)
127  {
128  flag = false;
129  break;
130  }
131  auto parent_ind = parent[edge_ind].ed_ind[v_pos];
132  v_pos = parent[edge_ind].v_pos[v_pos];
133  edge_ind = parent_ind;
134  }
135  if(flag)
136  cost += rule.cost;
137  }
138  return cost;
139 }
140 
141 
142 // -------------------------------------------------------------------------
144  long cur_node,
145  GraphEdgeInfo& cur_edge,
146  bool isStart,
147  LongVector &vecIndex,
148  std::priority_queue<PDP, std::vector<PDP>,
149  std::greater<PDP> > &que)
150 {
151  double extCost = 0.0;
152  GraphEdgeInfo* new_edge;
153  double totalCost;
154  for(const auto &index : vecIndex)
155  {
156  new_edge = m_vecEdgeVector[index];
157  extCost = 0.0;
159  {
160  extCost = getRestrictionCost(cur_edge.m_lEdgeIndex, *new_edge, isStart);
161  }
162  if(new_edge->m_lStartNode == cur_node)
163  {
164  if(new_edge->m_dCost >= 0.0)
165  {
166  if(isStart)
167  totalCost = m_dCost[cur_edge.m_lEdgeIndex].endCost + new_edge->m_dCost + extCost;
168  else
169  totalCost = m_dCost[cur_edge.m_lEdgeIndex].startCost + new_edge->m_dCost + extCost;
170  if(totalCost < m_dCost[index].endCost)
171  {
172  m_dCost[index].endCost = totalCost;
173  parent[new_edge->m_lEdgeIndex].v_pos[0] = (isStart?0:1);
174  parent[new_edge->m_lEdgeIndex].ed_ind[0] = cur_edge.m_lEdgeIndex;
175  que.push(std::make_pair(totalCost, std::make_pair(new_edge->m_lEdgeIndex, true)));
176  }
177  }
178  }
179  else
180  {
181  if(new_edge->m_dReverseCost >= 0.0)
182  {
183  if(isStart)
184  totalCost = m_dCost[cur_edge.m_lEdgeIndex].endCost + new_edge->m_dReverseCost + extCost;
185  else
186  totalCost = m_dCost[cur_edge.m_lEdgeIndex].startCost + new_edge->m_dReverseCost + extCost;
187  if(totalCost < m_dCost[index].startCost)
188  {
189  m_dCost[index].startCost = totalCost;
190  parent[new_edge->m_lEdgeIndex].v_pos[1] = (isStart?0:1);
191  parent[new_edge->m_lEdgeIndex].ed_ind[1] = cur_edge.m_lEdgeIndex;
192  que.push(std::make_pair(totalCost, std::make_pair(new_edge->m_lEdgeIndex, false)));
193  }
194  }
195  }
196  }
197 }
198 
199 
200 // -------------------------------------------------------------------------
202  edge_t *edges,
203  unsigned int edge_count,
204  std::vector<int> vertices,
205  bool directed,
206  bool has_reverse_cost,
208  int *path_count,
209  char **err_msg,
210  std::vector<PDVI> &ruleList)
211 {
212  construct_graph(edges, edge_count, has_reverse_cost, directed);
213  if(ruleList.size() > 0)
214  {
215  m_ruleTable.clear();
216  LongVector vecsource;
217  for(const auto &rule : ruleList)
218  {
219  std::vector<long> temp_precedencelist;
220  temp_precedencelist.clear();
221  for(auto const &seq : rule.second)
222  {
223  temp_precedencelist.push_back(seq);
224  }
225  int dest_edge_id = rule.second[0];
226  if(m_ruleTable.find(dest_edge_id) != m_ruleTable.end())
227  {
228  m_ruleTable[dest_edge_id].push_back(Rule(rule.first, temp_precedencelist));
229  }
230  else
231  {
232  std::vector<Rule> temprules;
233  temprules.clear();
234  temprules.push_back(Rule(rule.first, temp_precedencelist));
235  m_ruleTable.insert(std::make_pair(dest_edge_id, temprules));
236  }
237  }
238  m_bIsturnRestrictOn = true;
239  }
240  parent = new PARENT_PATH[edge_count + 1];
241  m_dCost = new CostHolder[edge_count + 1];
242  m_vecPath.clear();
243  size_t i;
244  size_t total_vertices = vertices.size();
245  for(i = 0; i < total_vertices - 1; i++)
246  {
247  int ret = my_dijkstra(vertices[i], vertices[i + 1], edge_count, err_msg);
248  if(ret < 0)
249  {
250  deleteall();
251  return -1;
252  }
253  }
254 
255  *path = (path_element_t *) malloc(sizeof(path_element_t) * (m_vecPath.size() + 1));
256  *path_count = static_cast<int>(m_vecPath.size());
257 
258  for(int i = 0; i < *path_count; i++)
259  {
260  (*path)[i].vertex_id = m_vecPath[i].vertex_id;
261  (*path)[i].edge_id = m_vecPath[i].edge_id;
262  (*path)[i].cost = m_vecPath[i].cost;
263  }
264  deleteall();
265  return 0;
266 }
267 
268 
269 // -------------------------------------------------------------------------
270 int GraphDefinition::my_dijkstra(long start_vertex, long end_vertex, unsigned int edge_count, char **err_msg)
271 {
273  {
274  *err_msg = (char *)"Graph not Ready!";
275  return -1;
276  }
277  unsigned int i;
278  for(i = 0; i <= edge_count; i++)
279  {
280  m_dCost[i].startCost = 1e15;
281  m_dCost[i].endCost = 1e15;
282  }
283 
284  if(m_mapNodeId2Edge.find(start_vertex) == m_mapNodeId2Edge.end())
285  {
286  *err_msg = (char *)"Source Not Found";
287  deleteall();
288  return -1;
289  }
290 
291  if(m_mapNodeId2Edge.find(end_vertex) == m_mapNodeId2Edge.end())
292  {
293  *err_msg = (char *)"Destination Not Found";
294  deleteall();
295  return -1;
296  }
297 
298  std::priority_queue<PDP, std::vector<PDP>, std::greater<PDP> > que;
299  LongVector vecsource = m_mapNodeId2Edge[start_vertex];
300  GraphEdgeInfo* cur_edge = NULL;
301 
302  for(const auto &source : vecsource)
303  {
304  cur_edge = m_vecEdgeVector[source];
305  if(cur_edge->m_lStartNode == start_vertex)
306  {
307  if(cur_edge->m_dCost >= 0.0)
308  {
309  m_dCost[cur_edge->m_lEdgeIndex].endCost= cur_edge->m_dCost;
310  parent[cur_edge->m_lEdgeIndex].v_pos[0] = -1;
311  parent[cur_edge->m_lEdgeIndex].ed_ind[0] = -1;
312  que.push(std::make_pair(cur_edge->m_dCost, std::make_pair(cur_edge->m_lEdgeIndex, true)));
313  }
314  }
315  else
316  {
317  if(cur_edge->m_dReverseCost >= 0.0)
318  {
319  m_dCost[cur_edge->m_lEdgeIndex].startCost = cur_edge->m_dReverseCost;
320  parent[cur_edge->m_lEdgeIndex].v_pos[1] = -1;
321  parent[cur_edge->m_lEdgeIndex].ed_ind[1] = -1;
322  que.push(std::make_pair(cur_edge->m_dReverseCost, std::make_pair(cur_edge->m_lEdgeIndex, false)));
323  }
324  }
325  }
326 
327  long cur_node = -1;
328 
329  while(!que.empty())
330  {
331  PDP cur_pos = que.top();
332  que.pop();
333  int cured_index = cur_pos.second.first;
334  cur_edge = m_vecEdgeVector[cured_index];
335 
336  if(cur_pos.second.second) // explore edges connected to end node
337  {
338  cur_node = cur_edge->m_lEndNode;
339  if(cur_edge->m_dCost < 0.0)
340  continue;
341  if(cur_node == end_vertex)
342  break;
343  explore(cur_node, *cur_edge, true, cur_edge->m_vecEndConnedtedEdge, que);
344  }
345  else // explore edges connected to start node
346  {
347  cur_node = cur_edge->m_lStartNode;
348  if(cur_edge->m_dReverseCost < 0.0)
349  continue;
350  if(cur_node == end_vertex)
351  break;
352  explore(cur_node, *cur_edge, false, cur_edge->m_vecStartConnectedEdge, que);
353  }
354  }
355  if(cur_node != end_vertex)
356  {
357  *err_msg = (char *)"Path Not Found";
358  deleteall();
359  return -1;
360  }
361  else
362  {
363  if(cur_node == cur_edge->m_lStartNode)
364  {
365  construct_path(cur_edge->m_lEdgeIndex, 1);
366  }
367  else
368  {
369  construct_path(cur_edge->m_lEdgeIndex, 0);
370  }
371  path_element_t pelement;
372  pelement.vertex_id = end_vertex;
373  pelement.edge_id = -1;
374  pelement.cost = 0.0;
375  m_vecPath.push_back(pelement);
376  }
377  return 0;
378 }
379 
380 
381 // -------------------------------------------------------------------------
382 int GraphDefinition::my_dijkstra(edge_t *edges, unsigned int edge_count, int start_edge_id, double start_part, int end_edge_id, double end_part, bool directed, bool has_reverse_cost,
383  path_element_t **path, int *path_count, char **err_msg, std::vector<PDVI> &ruleList)
384 {
386  {
387  init();
388  construct_graph(edges, edge_count, has_reverse_cost, directed);
389  m_bIsGraphConstructed = true;
390  }
391  GraphEdgeInfo* start_edge_info = m_vecEdgeVector[m_mapEdgeId2Index[start_edge_id]];
392  edge_t start_edge;
393  long start_vertex, end_vertex;
394  m_dStartpart = start_part;
395  m_dEndPart = end_part;
396  m_lStartEdgeId = start_edge_id;
397  m_lEndEdgeId = end_edge_id;
398 
399  if(start_part == 0.0)
400  {
401  start_vertex = start_edge_info->m_lStartNode;
402  }
403  else if(start_part == 1.0)
404  {
405  start_vertex = start_edge_info->m_lEndNode;
406  }
407  else
408  {
409  isStartVirtual = true;
410  m_lStartEdgeId = start_edge_id;
411  start_vertex = max_node_id + 1;
412  max_node_id++;
413  start_edge.id = max_edge_id + 1;
414  max_edge_id++;
415  start_edge.source = start_vertex;
416  start_edge.reverse_cost = -1.0;
417  if(start_edge_info->m_dCost >= 0.0)
418  {
419  start_edge.target = start_edge_info->m_lEndNode;
420  start_edge.cost = (1.0 - start_part) * start_edge_info->m_dCost;
421  addEdge(start_edge);
422  edge_count++;
423  }
424  if(start_edge_info->m_dReverseCost >= 0.0)
425  {
426  start_edge.id = max_edge_id + 1;
427  max_edge_id++;
428  start_edge.target = start_edge_info->m_lStartNode;
429  start_edge.cost = start_part * start_edge_info->m_dReverseCost;
430  addEdge(start_edge);
431  edge_count++;
432  }
433  }
434 
435  GraphEdgeInfo* end_edge_info = m_vecEdgeVector[m_mapEdgeId2Index[end_edge_id]];
436  edge_t end_edge;
437 
438  if(end_part == 0.0)
439  {
440  end_vertex = end_edge_info->m_lStartNode;
441  }
442  else if(end_part == 1.0)
443  {
444  end_vertex = end_edge_info->m_lEndNode;
445  }
446  else
447  {
448  isEndVirtual = true;
449  m_lEndEdgeId = end_edge_id;
450  end_vertex = max_node_id + 1;
451  max_node_id++;
452  end_edge.id = max_edge_id + 1;
453  max_edge_id++;
454  end_edge.target = end_vertex;
455  end_edge.reverse_cost = -1.0;
456  if(end_edge_info->m_dCost >= 0.0)
457  {
458  end_edge.source = end_edge_info->m_lStartNode;
459  end_edge.cost = end_part * end_edge_info->m_dCost;
460  addEdge(end_edge);
461  edge_count++;
462  }
463  if(end_edge_info->m_dReverseCost >= 0.0)
464  {
465  end_edge.source = end_edge_info->m_lEndNode;
466  end_edge.id = max_edge_id + 1;
467  end_edge.cost = (1.0 - end_part) * end_edge_info->m_dReverseCost;
468  addEdge(end_edge);
469  edge_count++;
470  }
471  }
472 
473  return(my_dijkstra(edges, edge_count, start_vertex, end_vertex, directed, has_reverse_cost, path, path_count, err_msg, ruleList));
474 }
475 
476 
477 // -------------------------------------------------------------------------
478 int GraphDefinition:: my_dijkstra(edge_t *edges, unsigned int edge_count, long start_vertex, long end_vertex, bool directed, bool has_reverse_cost,
479  path_element_t **path, int *path_count, char **err_msg, std::vector<PDVI> &ruleList)
480 {
481  m_ruleTable.clear();
482  LongVector vecsource;
483  for (const auto &rule : ruleList)
484  {
485  size_t j;
486  size_t seq_cnt = rule.second.size();
487  std::vector<long> temp_precedencelist;
488  temp_precedencelist.clear();
489  for(j = 1; j < seq_cnt; j++)
490  {
491  temp_precedencelist.push_back(rule.second[j]);
492  }
493  int dest_edge_id = rule.second[0];
494  if(m_ruleTable.find(dest_edge_id) != m_ruleTable.end())
495  {
496  m_ruleTable[dest_edge_id].push_back(Rule(rule.first, temp_precedencelist));
497  }
498  else
499  {
500  std::vector<Rule> temprules;
501  temprules.clear();
502  temprules.push_back(Rule(rule.first, temp_precedencelist));
503  m_ruleTable.insert(std::make_pair(dest_edge_id, temprules));
504  }
505 
506  if(isStartVirtual)
507  {
508  if(seq_cnt == 2 && rule.second[1] == m_lStartEdgeId)
509  {
510  vecsource = m_mapNodeId2Edge[start_vertex];
511  for(const auto &source : vecsource)
512  {
513  temp_precedencelist.clear();
514  temp_precedencelist.push_back(m_vecEdgeVector[source]->m_lEdgeID);
515  m_ruleTable[dest_edge_id].push_back(Rule(rule.first, temp_precedencelist));
516  }
517  }
518  }
519  }
520  if(isEndVirtual)
521  {
522  if(m_ruleTable.find(m_lEndEdgeId) != m_ruleTable.end())
523  {
524  std::vector<Rule> tmpRules = m_ruleTable[m_lEndEdgeId];
525  vecsource = m_mapNodeId2Edge[end_vertex];
526  for(const auto &source : vecsource)
527  {
528  m_ruleTable.insert(std::make_pair(m_vecEdgeVector[source]->m_lEdgeID, tmpRules));
529  }
530  }
531  }
532  m_bIsturnRestrictOn = true;
533  return(my_dijkstra(edges, edge_count, start_vertex, end_vertex, directed, has_reverse_cost, path, path_count, err_msg));
534 }
535 
536 
537 // -------------------------------------------------------------------------
538 int GraphDefinition:: my_dijkstra(edge_t *edges, unsigned int edge_count, long start_vertex, long end_vertex, bool directed, bool has_reverse_cost,
539  path_element_t **path, int *path_count, char **err_msg)
540 {
542  {
543  init();
544  construct_graph(edges, edge_count, has_reverse_cost, directed);
545  m_bIsGraphConstructed = true;
546  }
547 
548  std::priority_queue<PDP, std::vector<PDP>, std::greater<PDP> > que;
549  parent = new PARENT_PATH[edge_count + 1];
550  m_dCost = new CostHolder[edge_count + 1];
551  m_vecPath.clear();
552 
553  unsigned int i;
554  for(i = 0; i <= edge_count; i++)
555  {
556  m_dCost[i].startCost = 1e15;
557  m_dCost[i].endCost = 1e15;
558  }
559 
560  if(m_mapNodeId2Edge.find(start_vertex) == m_mapNodeId2Edge.end())
561  {
562  *err_msg = (char *)"Source Not Found";
563  deleteall();
564  return -1;
565  }
566 
567  if(m_mapNodeId2Edge.find(end_vertex) == m_mapNodeId2Edge.end())
568  {
569  *err_msg = (char *)"Destination Not Found";
570  deleteall();
571  return -1;
572  }
573 
574  LongVector vecsource = m_mapNodeId2Edge[start_vertex];
575  GraphEdgeInfo* cur_edge = NULL;
576 
577  for(const auto &source: vecsource)
578  {
579  cur_edge = m_vecEdgeVector[source];
580  if(cur_edge->m_lStartNode == start_vertex)
581  {
582  if(cur_edge->m_dCost >= 0.0)
583  {
584  m_dCost[cur_edge->m_lEdgeIndex].endCost= cur_edge->m_dCost;
585  parent[cur_edge->m_lEdgeIndex].v_pos[0] = -1;
586  parent[cur_edge->m_lEdgeIndex].ed_ind[0] = -1;
587  que.push(std::make_pair(cur_edge->m_dCost, std::make_pair(cur_edge->m_lEdgeIndex, true)));
588  }
589  }
590  else
591  {
592  if(cur_edge->m_dReverseCost >= 0.0)
593  {
594  m_dCost[cur_edge->m_lEdgeIndex].startCost = cur_edge->m_dReverseCost;
595  parent[cur_edge->m_lEdgeIndex].v_pos[1] = -1;
596  parent[cur_edge->m_lEdgeIndex].ed_ind[1] = -1;
597  que.push(std::make_pair(cur_edge->m_dReverseCost, std::make_pair(cur_edge->m_lEdgeIndex, false)));
598  }
599  }
600  }
601  long cur_node = -1;
602 
603  while(!que.empty())
604  {
605  PDP cur_pos = que.top();
606  que.pop();
607  int cured_index = cur_pos.second.first;
608  cur_edge = m_vecEdgeVector[cured_index];
609 
610  if(cur_pos.second.second) // explore edges connected to end node
611  {
612  cur_node = cur_edge->m_lEndNode;
613  if(cur_edge->m_dCost < 0.0)
614  continue;
615  if(cur_node == end_vertex)
616  break;
617  explore(cur_node, *cur_edge, true, cur_edge->m_vecEndConnedtedEdge, que);
618  }
619  else // explore edges connected to start node
620  {
621  cur_node = cur_edge->m_lStartNode;
622  if(cur_edge->m_dReverseCost < 0.0)
623  continue;
624  if(cur_node == end_vertex)
625  break;
626  explore(cur_node, *cur_edge, false, cur_edge->m_vecStartConnectedEdge, que);
627  }
628  }
629  if(cur_node != end_vertex)
630  {
632  {
633  if(get_single_cost(1000.0, path, path_count))
634  {
635  return 0;
636  }
637  }
638  *err_msg = (char *)"Path Not Found";
639  deleteall();
640  return -1;
641  }
642  else
643  {
644  double total_cost;
645  if(cur_node == cur_edge->m_lStartNode)
646  {
647  total_cost = m_dCost[cur_edge->m_lEdgeIndex].startCost;
648  construct_path(cur_edge->m_lEdgeIndex, 1);
649  }
650  else
651  {
652  total_cost = m_dCost[cur_edge->m_lEdgeIndex].endCost;
653  construct_path(cur_edge->m_lEdgeIndex, 0);
654  }
655  path_element_t pelement;
656  pelement.vertex_id = end_vertex;
657  pelement.edge_id = -1;
658  pelement.cost = 0.0;
659  m_vecPath.push_back(pelement);
660 
662  {
663  if(get_single_cost(total_cost, path, path_count))
664  {
665  return 0;
666  }
667  }
668 
669  *path = (path_element_t *) malloc(sizeof(path_element_t) * (m_vecPath.size() + 1));
670  *path_count = static_cast<int>(m_vecPath.size());
671 
672  for(int i = 0; i < *path_count; i++)
673  {
674  (*path)[i].vertex_id = m_vecPath[i].vertex_id;
675  (*path)[i].edge_id = m_vecPath[i].edge_id;
676  (*path)[i].cost = m_vecPath[i].cost;
677  }
678  if(isStartVirtual)
679  {
680  (*path)[0].vertex_id = -1;
681  (*path)[0].edge_id = m_lStartEdgeId;
682  }
683  if(isEndVirtual)
684  {
685  *path_count = *path_count - 1;
686  (*path)[*path_count - 1].edge_id = m_lEndEdgeId;
687  }
688  }
689  deleteall();
690  return 0;
691 }
692 
693 
694 // -------------------------------------------------------------------------
696 {
698  if(m_dEndPart >= m_dStartpart)
699  {
700  if(start_edge_info->m_dCost >= 0.0 && start_edge_info->m_dCost * (m_dEndPart - m_dStartpart) <= total_cost)
701  {
702  *path = (path_element_t *) malloc(sizeof(path_element_t) * (1));
703  *path_count = 1;
704  (*path)[0].vertex_id = -1;
705  (*path)[0].edge_id = m_lStartEdgeId;
706  (*path)[0].cost = start_edge_info->m_dCost * (m_dEndPart - m_dStartpart);
707 
708  return true;
709  }
710  }
711  else
712  {
713  if(start_edge_info->m_dReverseCost >= 0.0 && start_edge_info->m_dReverseCost * (m_dStartpart - m_dEndPart) <= total_cost)
714  {
715  *path = (path_element_t *) malloc(sizeof(path_element_t) * (1));
716  *path_count = 1;
717  (*path)[0].vertex_id = -1;
718  (*path)[0].edge_id = m_lStartEdgeId;
719  (*path)[0].cost = start_edge_info->m_dReverseCost * (m_dStartpart - m_dEndPart);
720 
721  return true;
722  }
723  }
724  return false;
725 
726 }
727 
728 
729 // -------------------------------------------------------------------------
730 bool GraphDefinition::construct_graph(edge_t* edges, int edge_count, bool has_reverse_cost, bool directed)
731 {
732  int i;
733  for(i = 0; i < edge_count; i++)
734  {
735  if(!has_reverse_cost)
736  {
737  if(directed)
738  {
739  edges[i].reverse_cost = -1.0;
740  }
741  else
742  {
743  edges[i].reverse_cost = edges[i].cost;
744  }
745  }
746  addEdge(edges[i]);
747  }
748  m_bIsGraphConstructed = true;
749  return true;
750 }
751 
752 
753 // -------------------------------------------------------------------------
754 bool GraphDefinition::connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo& secondEdge, bool bIsStartNodeSame)
755 {
756  if(bIsStartNodeSame)
757  {
758  if(firstEdge.m_dReverseCost >= 0.0)
759  firstEdge.m_vecStartConnectedEdge.push_back(secondEdge.m_lEdgeIndex);
760  if(firstEdge.m_lStartNode == secondEdge.m_lStartNode)
761  {
762  if(secondEdge.m_dReverseCost >= 0.0)
763  secondEdge.m_vecStartConnectedEdge.push_back(firstEdge.m_lEdgeIndex);
764  }
765  else
766  {
767  if(secondEdge.m_dCost >= 0.0)
768  secondEdge.m_vecEndConnedtedEdge.push_back(firstEdge.m_lEdgeIndex);
769  }
770  }
771  else
772  {
773  if(firstEdge.m_dCost >= 0.0)
774  firstEdge.m_vecEndConnedtedEdge.push_back(secondEdge.m_lEdgeIndex);
775  if(firstEdge.m_lEndNode == secondEdge.m_lStartNode)
776  {
777  if(secondEdge.m_dReverseCost >= 0.0)
778  secondEdge.m_vecStartConnectedEdge.push_back(firstEdge.m_lEdgeIndex);
779  }
780  else
781  {
782  if(secondEdge.m_dCost >= 0.0)
783  secondEdge.m_vecEndConnedtedEdge.push_back(firstEdge.m_lEdgeIndex);
784  }
785  }
786 
787  return true;
788 }
789 
790 
791 // -------------------------------------------------------------------------
793 {
794  // long lTest;
795  Long2LongMap::iterator itMap = m_mapEdgeId2Index.find(edgeIn.id);
796  if(itMap != m_mapEdgeId2Index.end())
797  return false;
798 
799 
800  GraphEdgeInfo* newEdge = new GraphEdgeInfo();
801  newEdge->m_vecStartConnectedEdge.clear();
802  newEdge->m_vecEndConnedtedEdge.clear();
803  newEdge->m_vecRestrictedEdge.clear();
804  newEdge->m_lEdgeID = edgeIn.id;
805  newEdge->m_lEdgeIndex = m_vecEdgeVector.size();
806  newEdge->m_lStartNode = edgeIn.source;
807  newEdge->m_lEndNode = edgeIn.target;
808  newEdge->m_dCost = edgeIn.cost;
809  newEdge->m_dReverseCost = edgeIn.reverse_cost;
810 
811  if(edgeIn.id > max_edge_id)
812  {
813  max_edge_id = edgeIn.id;
814  }
815 
816  if(newEdge->m_lStartNode > max_node_id)
817  {
818  max_node_id = newEdge->m_lStartNode;
819  }
820  if(newEdge->m_lEndNode > max_node_id)
821  {
822  max_node_id = newEdge->m_lEndNode;
823  }
824 
825  //Searching the start node for connectivity
826  Long2LongVectorMap::iterator itNodeMap = m_mapNodeId2Edge.find(edgeIn.source);
827  if(itNodeMap != m_mapNodeId2Edge.end())
828  {
829  //Connect current edge with existing edge with start node
830  //connectEdge(
831  long lEdgeCount = itNodeMap->second.size();
832  long lEdgeIndex;
833  for(lEdgeIndex = 0; lEdgeIndex < lEdgeCount; lEdgeIndex++)
834  {
835  long lEdge = itNodeMap->second.at(lEdgeIndex);
836  connectEdge(*newEdge, *m_vecEdgeVector[lEdge], true);
837  }
838  }
839 
840 
841  //Searching the end node for connectivity
842  itNodeMap = m_mapNodeId2Edge.find(edgeIn.target);
843  if(itNodeMap != m_mapNodeId2Edge.end())
844  {
845  //Connect current edge with existing edge with end node
846  //connectEdge(
847  long lEdgeCount = itNodeMap->second.size();
848  long lEdgeIndex;
849  for(lEdgeIndex = 0; lEdgeIndex < lEdgeCount; lEdgeIndex++)
850  {
851  long lEdge = itNodeMap->second.at(lEdgeIndex);
852  connectEdge(*newEdge, *m_vecEdgeVector[lEdge], false);
853  }
854  }
855 
856 
857 
858  //Add this node and edge into the data structure
859  m_mapNodeId2Edge[edgeIn.source].push_back(newEdge->m_lEdgeIndex);
860  m_mapNodeId2Edge[edgeIn.target].push_back(newEdge->m_lEdgeIndex);
861 
862 
863  //Adding edge to the list
864  m_mapEdgeId2Index.insert(std::make_pair(newEdge->m_lEdgeID, m_vecEdgeVector.size()));
865  m_vecEdgeVector.push_back(newEdge);
866 
867  //
868 
869 
870  return true;
871 }
double endCost
bool get_single_cost(double total_cost, path_element_t **path, int *path_count)
int path_count
Definition: BDATester.cpp:51
GraphEdgeVector m_vecEdgeVector
double cost
long ed_ind[2]
bool addEdge(edge edgeIn)
std::vector< path_element_t > m_vecPath
double m_dReverseCost
RuleTable m_ruleTable
Long2LongMap m_mapEdgeId2Index
Long2LongVectorMap m_mapNodeId2Edge
int my_dijkstra(long start_vertex, long end_vertex, unsigned int edge_count, char **err_msg)
struct Rule Rule
double getRestrictionCost(long cur_node, GraphEdgeInfo &new_edge, bool isStart)
bool construct_graph(edge_t *edges, int edge_count, bool has_reverse_cost, bool directed)
bool connectEdge(GraphEdgeInfo &firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame)
int multi_dijkstra(edge_t *edges, unsigned int edge_count, std::vector< int > vertices, bool directed, bool has_reverse_cost, path_element_t **path, int *path_count, char **err_msg, std::vector< PDVI > &ruleList)
int edge_count
Definition: BDATester.cpp:47
double reverse_cost
edge_astar_t * edges
Definition: BDATester.cpp:46
double construct_path(long ed_id, int v_pos)
int64_t edge_id
Definition: pgr_types.h:89
LongVector m_vecEndConnedtedEdge
std::vector< size_t > LongVector
PARENT_PATH * parent
std::pair< double, PIB > PDP
path_element_t * path
Definition: BDATester.cpp:49
CostHolder * m_dCost
int64_t vertex_id
Definition: pgr_types.h:88
void explore(long cur_node, GraphEdgeInfo &cur_edge, bool isStart, LongVector &vecIndex, std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > &que)
char * err_msg
Definition: BDATester.cpp:50
double startCost
VectorOfLongVector m_vecRestrictedEdge
LongVector m_vecStartConnectedEdge
double cost
Definition: pgr_types.h:90