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