PGROUTING  2.6
GraphDefinition Class Reference

#include "GraphDefinition.h"

Collaboration diagram for GraphDefinition:

Public Member Functions

 GraphDefinition (void)
 
 ~GraphDefinition (void)
 
bool construct_graph (edge_t *edges, size_t edge_count, bool has_reverse_cost, bool directed)
 
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)
 
int my_dijkstra (long start_vertex, long end_vertex, size_t edge_count, char **err_msg)
 
int my_dijkstra (edge_t *edges, size_t edge_count, long start_vertex, long end_vertex, bool directed, bool has_reverse_cost, path_element_tt **path, size_t *path_count, char **err_msg)
 
int my_dijkstra (edge_t *edges, size_t edge_count, long start_vertex, long end_vertex, bool directed, bool has_reverse_cost, path_element_tt **path, size_t *path_count, char **err_msg, std::vector< PDVI > &ruleList)
 
int my_dijkstra (edge_t *edges, size_t edge_count, long start_edge, double start_part, long end_edge, double end_part, bool directed, bool has_reverse_cost, path_element_tt **path, size_t *path_count, char **err_msg, std::vector< PDVI > &ruleList)
 

Private Member Functions

bool addEdge (edge edgeIn)
 
bool connectEdge (GraphEdgeInfo &firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame)
 
double construct_path (long ed_id, long v_pos)
 
void deleteall ()
 
void explore (long cur_node, GraphEdgeInfo &cur_edge, bool isStart, LongVector &vecIndex, std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > &que)
 
bool get_single_cost (double total_cost, path_element_tt **path, size_t *path_count)
 
double getRestrictionCost (long cur_node, GraphEdgeInfo &new_edge, bool isStart)
 
void init ()
 

Private Attributes

bool isEndVirtual
 
bool isStartVirtual
 
bool m_bIsGraphConstructed
 
bool m_bIsturnRestrictOn
 
CostHolderm_dCost
 
double m_dEndPart
 
double m_dStartpart
 
long m_lEndEdgeId
 
long m_lStartEdgeId
 
Long2LongMap m_mapEdgeId2Index
 
Long2LongVectorMap m_mapNodeId2Edge
 
RuleTable m_ruleTable
 
GraphEdgeVector m_vecEdgeVector
 
std::vector< path_element_ttm_vecPath
 
long max_edge_id
 
long max_node_id
 
PARENT_PATHparent
 

Detailed Description

Definition at line 89 of file GraphDefinition.h.

Constructor & Destructor Documentation

GraphDefinition::GraphDefinition ( void  )

Definition at line 36 of file GraphDefinition.cpp.

References init(), m_bIsGraphConstructed, m_bIsturnRestrictOn, m_dCost, m_dEndPart, m_dStartpart, m_lEndEdgeId, m_lStartEdgeId, and parent.

36  {
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 }
PARENT_PATH * parent
CostHolder * m_dCost

Here is the call graph for this function:

GraphDefinition::~GraphDefinition ( void  )

Definition at line 49 of file GraphDefinition.cpp.

49  {
50 }

Member Function Documentation

bool GraphDefinition::addEdge ( edge  edgeIn)
private

Referenced by connectEdge(), construct_graph(), and my_dijkstra().

Here is the caller graph for this function:

bool GraphDefinition::connectEdge ( GraphEdgeInfo firstEdge,
GraphEdgeInfo secondEdge,
bool  bIsStartNodeSame 
)
private

Definition at line 695 of file GraphDefinition.cpp.

References addEdge(), edge_t::cost, edge_t::id, GraphEdgeInfo::m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeID, GraphEdgeInfo::m_lEdgeIndex, GraphEdgeInfo::m_lEndNode, GraphEdgeInfo::m_lStartNode, m_mapEdgeId2Index, m_mapNodeId2Edge, m_vecEdgeVector, GraphEdgeInfo::m_vecEndConnedtedEdge, GraphEdgeInfo::m_vecRestrictedEdge, GraphEdgeInfo::m_vecStartConnectedEdge, max_edge_id, max_node_id, edge_t::reverse_cost, edge_t::source, and edge_t::target.

696  {
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 }
LongVector m_vecStartConnectedEdge
double m_dReverseCost
LongVector m_vecEndConnedtedEdge

Here is the call graph for this function:

bool GraphDefinition::construct_graph ( edge_t edges,
size_t  edge_count,
bool  has_reverse_cost,
bool  directed 
)

Definition at line 677 of file GraphDefinition.cpp.

References addEdge(), edge_t::cost, m_bIsGraphConstructed, and edge_t::reverse_cost.

Referenced by multi_dijkstra(), and my_dijkstra().

678  {
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 }
bool addEdge(edge edgeIn)
double cost
Definition: trsp_types.h:59
double reverse_cost
Definition: trsp_types.h:60

Here is the call graph for this function:

Here is the caller graph for this function:

double GraphDefinition::construct_path ( long  ed_id,
long  v_pos 
)
private

Definition at line 76 of file GraphDefinition.cpp.

References path_element::cost, path_element::edge_id, CostHolder::endCost, GraphEdgeInfo::m_dCost, m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeID, GraphEdgeInfo::m_lEndNode, GraphEdgeInfo::m_lStartNode, m_vecEdgeVector, m_vecPath, parent, CostHolder::startCost, and path_element::vertex_id.

Referenced by my_dijkstra().

76  {
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 }
double endCost
GraphEdgeVector m_vecEdgeVector
long edge_id
Definition: trsp.h:48
double m_dReverseCost
float8 cost
Definition: trsp.h:49
PARENT_PATH * parent
CostHolder * m_dCost
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

Here is the caller graph for this function:

void GraphDefinition::deleteall ( )
private

Definition at line 63 of file GraphDefinition.cpp.

References m_dCost, m_vecEdgeVector, and parent.

Referenced by multi_dijkstra(), and my_dijkstra().

63  {
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 }
GraphEdgeVector m_vecEdgeVector
PARENT_PATH * parent
CostHolder * m_dCost

Here is the caller graph for this function:

void GraphDefinition::explore ( long  cur_node,
GraphEdgeInfo cur_edge,
bool  isStart,
LongVector vecIndex,
std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > &  que 
)
private

Definition at line 150 of file GraphDefinition.cpp.

References PARENT_PATH::ed_ind, CostHolder::endCost, getRestrictionCost(), m_bIsturnRestrictOn, GraphEdgeInfo::m_dCost, m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeIndex, GraphEdgeInfo::m_lStartNode, m_vecEdgeVector, parent, CostHolder::startCost, and PARENT_PATH::v_pos.

Referenced by my_dijkstra().

156  {
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 }
double endCost
GraphEdgeVector m_vecEdgeVector
long ed_ind[2]
double m_dReverseCost
double getRestrictionCost(long cur_node, GraphEdgeInfo &new_edge, bool isStart)
PARENT_PATH * parent
CostHolder * m_dCost
double startCost

Here is the call graph for this function:

Here is the caller graph for this function:

bool GraphDefinition::get_single_cost ( double  total_cost,
path_element_tt **  path,
size_t *  path_count 
)
private

Definition at line 642 of file GraphDefinition.cpp.

References GraphEdgeInfo::m_dCost, m_dEndPart, GraphEdgeInfo::m_dReverseCost, m_dStartpart, m_lStartEdgeId, m_mapEdgeId2Index, m_vecEdgeVector, and path_element::vertex_id.

Referenced by my_dijkstra().

643  {
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 }
GraphEdgeVector m_vecEdgeVector
Long2LongMap m_mapEdgeId2Index
double m_dReverseCost
long vertex_id
Definition: trsp.h:47

Here is the caller graph for this function:

double GraphDefinition::getRestrictionCost ( long  cur_node,
GraphEdgeInfo new_edge,
bool  isStart 
)
private

Definition at line 114 of file GraphDefinition.cpp.

References PARENT_PATH::ed_ind, GraphEdgeInfo::m_lEdgeID, m_ruleTable, m_vecEdgeVector, parent, and PARENT_PATH::v_pos.

Referenced by explore().

117  {
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 }
GraphEdgeVector m_vecEdgeVector
long ed_ind[2]
RuleTable m_ruleTable
PARENT_PATH * parent

Here is the caller graph for this function:

void GraphDefinition::init ( )
private

Definition at line 54 of file GraphDefinition.cpp.

References isEndVirtual, isStartVirtual, max_edge_id, and max_node_id.

Referenced by GraphDefinition(), and my_dijkstra().

54  {
55  max_edge_id = 0;
56  max_node_id = 0;
57  isStartVirtual = false;
58  isEndVirtual = false;
59 }

Here is the caller graph for this function:

int GraphDefinition::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 
)

Definition at line 207 of file GraphDefinition.cpp.

References construct_graph(), deleteall(), m_bIsturnRestrictOn, m_dCost, m_ruleTable, m_vecPath, my_dijkstra(), parent, and path_element::vertex_id.

216  {
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 }
RuleTable m_ruleTable
struct Rule Rule
bool construct_graph(edge_t *edges, size_t edge_count, bool has_reverse_cost, bool directed)
int my_dijkstra(long start_vertex, long end_vertex, size_t edge_count, char **err_msg)
std::vector< long > LongVector
PARENT_PATH * parent
CostHolder * m_dCost
long vertex_id
Definition: trsp.h:47
std::vector< path_element_tt > m_vecPath

Here is the call graph for this function:

int GraphDefinition::my_dijkstra ( long  start_vertex,
long  end_vertex,
size_t  edge_count,
char **  err_msg 
)

Definition at line 269 of file GraphDefinition.cpp.

References construct_path(), path_element::cost, deleteall(), PARENT_PATH::ed_ind, path_element::edge_id, CostHolder::endCost, explore(), m_bIsGraphConstructed, GraphEdgeInfo::m_dCost, m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeIndex, GraphEdgeInfo::m_lEndNode, GraphEdgeInfo::m_lStartNode, m_mapNodeId2Edge, m_vecEdgeVector, GraphEdgeInfo::m_vecEndConnedtedEdge, m_vecPath, GraphEdgeInfo::m_vecStartConnectedEdge, parent, CostHolder::startCost, PARENT_PATH::v_pos, and path_element::vertex_id.

Referenced by multi_dijkstra(), my_dijkstra(), trsp_edge_wrapper(), and trsp_node_wrapper().

270  {
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 }
double endCost
GraphEdgeVector m_vecEdgeVector
long ed_ind[2]
long edge_id
Definition: trsp.h:48
LongVector m_vecStartConnectedEdge
Long2LongVectorMap m_mapNodeId2Edge
double m_dReverseCost
float8 cost
Definition: trsp.h:49
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)
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

Here is the call graph for this function:

Here is the caller graph for this function:

int GraphDefinition::my_dijkstra ( edge_t edges,
size_t  edge_count,
long  start_vertex,
long  end_vertex,
bool  directed,
bool  has_reverse_cost,
path_element_tt **  path,
size_t *  path_count,
char **  err_msg 
)

Definition at line 506 of file GraphDefinition.cpp.

References construct_graph(), construct_path(), path_element::cost, deleteall(), PARENT_PATH::ed_ind, path_element::edge_id, CostHolder::endCost, explore(), get_single_cost(), init(), isEndVirtual, isStartVirtual, m_bIsGraphConstructed, GraphEdgeInfo::m_dCost, m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeIndex, m_lEndEdgeId, GraphEdgeInfo::m_lEndNode, m_lStartEdgeId, GraphEdgeInfo::m_lStartNode, m_mapNodeId2Edge, m_vecEdgeVector, GraphEdgeInfo::m_vecEndConnedtedEdge, m_vecPath, GraphEdgeInfo::m_vecStartConnectedEdge, parent, CostHolder::startCost, PARENT_PATH::v_pos, and path_element::vertex_id.

508  {
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 }
double endCost
GraphEdgeVector m_vecEdgeVector
long ed_ind[2]
long edge_id
Definition: trsp.h:48
LongVector m_vecStartConnectedEdge
Long2LongVectorMap m_mapNodeId2Edge
double m_dReverseCost
bool construct_graph(edge_t *edges, size_t edge_count, bool has_reverse_cost, bool directed)
float8 cost
Definition: trsp.h:49
bool get_single_cost(double total_cost, path_element_tt **path, size_t *path_count)
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)
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

Here is the call graph for this function:

int GraphDefinition::my_dijkstra ( edge_t edges,
size_t  edge_count,
long  start_vertex,
long  end_vertex,
bool  directed,
bool  has_reverse_cost,
path_element_tt **  path,
size_t *  path_count,
char **  err_msg,
std::vector< PDVI > &  ruleList 
)

Definition at line 451 of file GraphDefinition.cpp.

References isEndVirtual, isStartVirtual, m_bIsturnRestrictOn, m_lEndEdgeId, m_lStartEdgeId, m_mapNodeId2Edge, m_ruleTable, m_vecEdgeVector, and my_dijkstra().

454  {
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 }
GraphEdgeVector m_vecEdgeVector
RuleTable m_ruleTable
Long2LongVectorMap m_mapNodeId2Edge
struct Rule Rule
int my_dijkstra(long start_vertex, long end_vertex, size_t edge_count, char **err_msg)
std::vector< long > LongVector

Here is the call graph for this function:

int GraphDefinition::my_dijkstra ( edge_t edges,
size_t  edge_count,
long  start_edge,
double  start_part,
long  end_edge,
double  end_part,
bool  directed,
bool  has_reverse_cost,
path_element_tt **  path,
size_t *  path_count,
char **  err_msg,
std::vector< PDVI > &  ruleList 
)

Definition at line 366 of file GraphDefinition.cpp.

References addEdge(), construct_graph(), edge_t::cost, edge_t::id, init(), isEndVirtual, isStartVirtual, m_bIsGraphConstructed, GraphEdgeInfo::m_dCost, m_dEndPart, GraphEdgeInfo::m_dReverseCost, m_dStartpart, m_lEndEdgeId, GraphEdgeInfo::m_lEndNode, m_lStartEdgeId, GraphEdgeInfo::m_lStartNode, m_mapEdgeId2Index, m_vecEdgeVector, max_edge_id, max_node_id, my_dijkstra(), edge_t::reverse_cost, edge_t::source, and edge_t::target.

369  {
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 }
int64_t source
Definition: trsp_types.h:57
GraphEdgeVector m_vecEdgeVector
bool addEdge(edge edgeIn)
double cost
Definition: trsp_types.h:59
Long2LongMap m_mapEdgeId2Index
double m_dReverseCost
bool construct_graph(edge_t *edges, size_t edge_count, bool has_reverse_cost, bool directed)
int my_dijkstra(long start_vertex, long end_vertex, size_t edge_count, char **err_msg)
int64_t target
Definition: trsp_types.h:58
double reverse_cost
Definition: trsp_types.h:60
int64_t id
Definition: trsp_types.h:56

Here is the call graph for this function:

Member Data Documentation

bool GraphDefinition::isEndVirtual
private

Definition at line 155 of file GraphDefinition.h.

Referenced by init(), and my_dijkstra().

bool GraphDefinition::isStartVirtual
private

Definition at line 154 of file GraphDefinition.h.

Referenced by init(), and my_dijkstra().

bool GraphDefinition::m_bIsGraphConstructed
private

Definition at line 162 of file GraphDefinition.h.

Referenced by construct_graph(), GraphDefinition(), and my_dijkstra().

bool GraphDefinition::m_bIsturnRestrictOn
private

Definition at line 161 of file GraphDefinition.h.

Referenced by explore(), GraphDefinition(), multi_dijkstra(), and my_dijkstra().

CostHolder* GraphDefinition::m_dCost
private
double GraphDefinition::m_dEndPart
private

Definition at line 153 of file GraphDefinition.h.

Referenced by get_single_cost(), GraphDefinition(), and my_dijkstra().

double GraphDefinition::m_dStartpart
private

Definition at line 152 of file GraphDefinition.h.

Referenced by get_single_cost(), GraphDefinition(), and my_dijkstra().

long GraphDefinition::m_lEndEdgeId
private

Definition at line 151 of file GraphDefinition.h.

Referenced by GraphDefinition(), and my_dijkstra().

long GraphDefinition::m_lStartEdgeId
private

Definition at line 150 of file GraphDefinition.h.

Referenced by get_single_cost(), GraphDefinition(), and my_dijkstra().

Long2LongMap GraphDefinition::m_mapEdgeId2Index
private

Definition at line 146 of file GraphDefinition.h.

Referenced by connectEdge(), get_single_cost(), and my_dijkstra().

Long2LongVectorMap GraphDefinition::m_mapNodeId2Edge
private

Definition at line 147 of file GraphDefinition.h.

Referenced by connectEdge(), and my_dijkstra().

RuleTable GraphDefinition::m_ruleTable
private

Definition at line 160 of file GraphDefinition.h.

Referenced by getRestrictionCost(), multi_dijkstra(), and my_dijkstra().

GraphEdgeVector GraphDefinition::m_vecEdgeVector
private
std::vector<path_element_tt> GraphDefinition::m_vecPath
private

Definition at line 157 of file GraphDefinition.h.

Referenced by construct_path(), multi_dijkstra(), and my_dijkstra().

long GraphDefinition::max_edge_id
private

Definition at line 149 of file GraphDefinition.h.

Referenced by connectEdge(), init(), and my_dijkstra().

long GraphDefinition::max_node_id
private

Definition at line 148 of file GraphDefinition.h.

Referenced by connectEdge(), init(), and my_dijkstra().

PARENT_PATH* GraphDefinition::parent
private

The documentation for this class was generated from the following files: