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