PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 37 of file GraphDefinition.cpp.

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

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

Here is the call graph for this function:

GraphDefinition::~GraphDefinition ( void  )

Definition at line 50 of file GraphDefinition.cpp.

50  {
51 }

Member Function Documentation

bool GraphDefinition::addEdge ( edge  edgeIn)
private

Definition at line 729 of file GraphDefinition.cpp.

References connectEdge(), edge::cost, edge::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::reverse_cost, edge::source, and edge::target.

Referenced by construct_graph(), and my_dijkstra().

729  {
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 }
float8 cost
Definition: trsp.h:35
GraphEdgeVector m_vecEdgeVector
VectorOfLongVector m_vecRestrictedEdge
long id
Definition: trsp.h:32
LongVector m_vecStartConnectedEdge
Long2LongMap m_mapEdgeId2Index
Long2LongVectorMap m_mapNodeId2Edge
double m_dReverseCost
bool connectEdge(GraphEdgeInfo &firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame)
LongVector m_vecEndConnedtedEdge
long target
Definition: trsp.h:34
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 696 of file GraphDefinition.cpp.

References GraphEdgeInfo::m_dCost, GraphEdgeInfo::m_dReverseCost, GraphEdgeInfo::m_lEdgeIndex, GraphEdgeInfo::m_lEndNode, GraphEdgeInfo::m_lStartNode, GraphEdgeInfo::m_vecEndConnedtedEdge, and GraphEdgeInfo::m_vecStartConnectedEdge.

Referenced by addEdge().

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

Here is the caller graph for this function:

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

Definition at line 678 of file GraphDefinition.cpp.

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

Referenced by multi_dijkstra(), and my_dijkstra().

679  {
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 }
float8 cost
Definition: trsp.h:35
bool addEdge(edge edgeIn)
float8 reverse_cost
Definition: trsp.h:36

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 77 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().

77  {
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 }
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 64 of file GraphDefinition.cpp.

References m_dCost, m_vecEdgeVector, and parent.

Referenced by multi_dijkstra(), and my_dijkstra().

64  {
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 }
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 151 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().

157  {
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 }
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 643 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().

644  {
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 }
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 115 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().

118  {
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 }
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 55 of file GraphDefinition.cpp.

References isEndVirtual, isStartVirtual, max_edge_id, and max_node_id.

Referenced by GraphDefinition(), and my_dijkstra().

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

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 208 of file GraphDefinition.cpp.

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

217  {
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 }
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 270 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 main(), multi_dijkstra(), my_dijkstra(), trsp_edge_wrapper(), and trsp_node_wrapper().

271  {
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 }
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 507 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.

509  {
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 }
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 452 of file GraphDefinition.cpp.

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

455  {
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 }
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 367 of file GraphDefinition.cpp.

References addEdge(), construct_graph(), edge::cost, edge::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::reverse_cost, edge::source, and edge::target.

370  {
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 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
GraphEdgeVector m_vecEdgeVector
bool addEdge(edge edgeIn)
long id
Definition: trsp.h:32
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)
long target
Definition: trsp.h:34
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33

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 addEdge(), get_single_cost(), and my_dijkstra().

Long2LongVectorMap GraphDefinition::m_mapNodeId2Edge
private

Definition at line 147 of file GraphDefinition.h.

Referenced by addEdge(), 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 addEdge(), init(), and my_dijkstra().

long GraphDefinition::max_node_id
private

Definition at line 148 of file GraphDefinition.h.

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

PARENT_PATH* GraphDefinition::parent
private

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