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