PGROUTING  2.6-dev
pgrouting::trsp::Pgr_trspHandler Class Reference

#include "pgr_trspHandler.h"

Collaboration diagram for pgrouting::trsp::Pgr_trspHandler:

Classes

class  CostHolder
 
class  Predecessor
 

Public Member Functions

 Pgr_trspHandler (pgr_edge_t *edges, const size_t edge_count, const bool directed, const std::vector< Rule > &ruleList)
 
 Pgr_trspHandler (void)=delete
 
 ~Pgr_trspHandler (void)=default
 
void clear ()
 
Path process (const int64_t start_vertex, const int64_t end_vertex)
 process More...
 
std::deque< Pathprocess (const std::vector< int64_t > sources, const std::vector< int64_t > targets)
 process More...
 

Private Types

typedef std::pair< double, std::pair< int64_t, bool > > PDP
 Used in the priority queue. More...
 
enum  Position { ILLEGAL = -1, RC_EDGE = 0, C_EDGE = 1 }
 predecesor edge More...
 

Private Member Functions

void add_to_que (double cost, size_t e_idx, bool isStart)
 
bool addEdge (const pgr_edge_t edgeIn)
 
void connectEndEdge (size_t firstEdge_idx, size_t secondEdge_idx)
 
void connectStartEdge (size_t firstEdge_idx, size_t secondEdge_idx)
 
void construct_graph (pgr_edge_t *edges, const size_t edge_count, const bool directed)
 
double construct_path (int64_t ed_id, Position pos)
 
EdgeInfo dijkstra_exploration ()
 
void explore (int64_t cur_node, const EdgeInfo cur_edge, bool isStart)
 
double get_tot_cost (double cost, size_t edge_idx, bool isStart)
 
double getRestrictionCost (int64_t cur_node, const EdgeInfo &new_edge, bool isStart)
 
void initialize_que ()
 
int initialize_restrictions (const std::vector< Rule > &ruleList)
 
Path process_trsp (size_t edge_count)
 
int64_t renumber_edges (pgr_edge_t *edges, const size_t edge_count) const
 

Private Attributes

int64_t current_node
 
std::map< int64_t, std::vector< size_t > > m_adjacency
 m_adjacency[vertex] = {edges} More...
 
std::vector< CostHolderm_dCost
 
std::vector< EdgeInfom_edges
 
int64_t m_end_vertex
 
std::map< int64_t, int64_t > m_mapEdgeId2Index
 Used only to veryfy that there are no reppetitions inserted the way it orks, repeating edges id is not allowed. More...
 
int64_t m_min_id
 
std::vector< Predecessorm_parent
 
Path m_path
 
std::map< int64_t, std::vector< Rule > > m_ruleTable
 
int64_t m_start_vertex
 
std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > que
 

Detailed Description

Definition at line 52 of file pgr_trspHandler.h.

Member Typedef Documentation

typedef std::pair<double, std::pair<int64_t, bool> > pgrouting::trsp::Pgr_trspHandler::PDP
private

Used in the priority queue.

Definition at line 56 of file pgr_trspHandler.h.

Member Enumeration Documentation

predecesor edge

because each row represents 2 edges, this enumeration is needed for the predecessors

  • C_EDGE: If the predecessor comes from the "cost" edge
  • RC_EDGE: If the predecessor comes from the "reverse_cost" edge
  • ILLEGAL: Its not a predecessor of anything

The "legal" values are indices to vectors

Enumerator
ILLEGAL 
RC_EDGE 
C_EDGE 

Definition at line 68 of file pgr_trspHandler.h.

Constructor & Destructor Documentation

pgrouting::trsp::Pgr_trspHandler::Pgr_trspHandler ( pgr_edge_t edges,
const size_t  edge_count,
const bool  directed,
const std::vector< Rule > &  ruleList 
)

Definition at line 43 of file pgr_trspHandler.cpp.

References construct_graph(), initialize_restrictions(), m_min_id, and renumber_edges().

47  :
48  m_ruleTable() {
49 
50  initialize_restrictions(ruleList);
51 
52  m_min_id = renumber_edges(edges, edge_count);
53 
55  edges,
56  edge_count,
57  directed);
58 
59 }
void construct_graph(pgr_edge_t *edges, const size_t edge_count, const bool directed)
int initialize_restrictions(const std::vector< Rule > &ruleList)
int64_t renumber_edges(pgr_edge_t *edges, const size_t edge_count) const
std::map< int64_t, std::vector< Rule > > m_ruleTable

Here is the call graph for this function:

pgrouting::trsp::Pgr_trspHandler::Pgr_trspHandler ( void  )
delete
pgrouting::trsp::Pgr_trspHandler::~Pgr_trspHandler ( void  )
default

Member Function Documentation

void pgrouting::trsp::Pgr_trspHandler::add_to_que ( double  cost,
size_t  e_idx,
bool  isStart 
)
private

Definition at line 318 of file pgr_trspHandler.cpp.

References que.

Referenced by explore(), and initialize_que().

321  {
322  que.push(std::make_pair(cost,
323  std::make_pair(e_idx, isStart)));
324 }
std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > que

Here is the caller graph for this function:

bool pgrouting::trsp::Pgr_trspHandler::addEdge ( const pgr_edge_t  edgeIn)
private

Definition at line 510 of file pgr_trspHandler.cpp.

References connectEndEdge(), connectStartEdge(), pgr_edge_t::id, pgrouting::trsp::EdgeInfo::idx(), m_adjacency, m_edges, m_mapEdgeId2Index, pgr_edge_t::source, and pgr_edge_t::target.

Referenced by construct_graph().

510  {
511  /*
512  * The edge was already inserted
513  *
514  * If the user has rows with repeated edge id, the subsequent edges will be ignored
515  *
516  * When changing to boost graph, the additional edges are to be added
517  */
518  if (m_mapEdgeId2Index.find(edgeIn.id) != m_mapEdgeId2Index.end()) {
519  return false;
520  }
521 
522 
523  /*
524  * the index of this new edge in the edges container is
525  * m_edges.size()
526  */
527  EdgeInfo edge(edgeIn, m_edges.size());
528 
529  // Adding edge to the list
530  m_mapEdgeId2Index.insert(
531  std::make_pair(
532  edge.edgeID(),
533  m_edges.size()));
534 
535  m_edges.push_back(edge);
536 
537  EdgeInfo &newEdge = m_edges[m_edges.size()-1];
538 
539 
540 
541  /*
542  * Searching the start node for connectivity
543  */
544  auto itNodeMap = m_adjacency.find(edgeIn.source);
545 
546  if (itNodeMap != m_adjacency.end()) {
547  for (const auto e_idx : itNodeMap->second) {
548  connectStartEdge(edge.idx(), e_idx);
549  }
550  }
551 
552 
553  /*
554  * Searching the end node for connectivity
555  */
556  itNodeMap = m_adjacency.find(edgeIn.target);
557  if (itNodeMap != m_adjacency.end()) {
558  for (const auto e_idx : itNodeMap->second) {
559  connectEndEdge(edge.idx(), e_idx);
560  }
561  }
562 
563 
564  /*
565  * Add the edges to the adjacency list
566  */
567  m_adjacency[edgeIn.source].push_back(newEdge.idx());
568  m_adjacency[edgeIn.target].push_back(newEdge.idx());
569 
570 
571 
572  return true;
573 }
void connectStartEdge(size_t firstEdge_idx, size_t secondEdge_idx)
Definition: trsp.h:31
int64_t source
Definition: pgr_edge_t.h:60
int64_t target
Definition: pgr_edge_t.h:61
void connectEndEdge(size_t firstEdge_idx, size_t secondEdge_idx)
std::map< int64_t, int64_t > m_mapEdgeId2Index
Used only to veryfy that there are no reppetitions inserted the way it orks, repeating edges id is no...
int64_t id
Definition: pgr_edge_t.h:59
std::map< int64_t, std::vector< size_t > > m_adjacency
m_adjacency[vertex] = {edges}
std::vector< EdgeInfo > m_edges

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::trsp::Pgr_trspHandler::clear ( )

Definition at line 89 of file pgr_trspHandler.cpp.

References Path::clear(), m_dCost, m_parent, and m_path.

Referenced by process().

89  {
90  m_parent.clear();
91  m_dCost.clear();
92  m_path.clear();
93 }
std::vector< CostHolder > m_dCost
void clear()
std::vector< Predecessor > m_parent

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::trsp::Pgr_trspHandler::connectEndEdge ( size_t  firstEdge_idx,
size_t  secondEdge_idx 
)
private

Definition at line 487 of file pgr_trspHandler.cpp.

References pgrouting::trsp::EdgeInfo::connect_endEdge(), pgrouting::trsp::EdgeInfo::connect_startEdge(), pgrouting::trsp::EdgeInfo::cost(), pgrouting::trsp::EdgeInfo::endNode(), m_edges, pgrouting::trsp::EdgeInfo::r_cost(), and pgrouting::trsp::EdgeInfo::startNode().

Referenced by addEdge().

489  {
490  EdgeInfo &firstEdge = m_edges[firstEdge_idx];
491  EdgeInfo &secondEdge = m_edges[secondEdge_idx];
492 
493  if (firstEdge.cost() >= 0.0) {
494  firstEdge.connect_endEdge(secondEdge_idx);
495  }
496 
497  if (firstEdge.endNode() == secondEdge.startNode()
498  && secondEdge.r_cost() >= 0.0) {
499  secondEdge.connect_startEdge(firstEdge_idx);
500  }
501 
502  if (firstEdge.endNode() == secondEdge.endNode()
503  && secondEdge.cost() >= 0.0) {
504  secondEdge.connect_endEdge(firstEdge_idx);
505  }
506 }
std::vector< EdgeInfo > m_edges

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::trsp::Pgr_trspHandler::connectStartEdge ( size_t  firstEdge_idx,
size_t  secondEdge_idx 
)
private

Definition at line 464 of file pgr_trspHandler.cpp.

References pgrouting::trsp::EdgeInfo::connect_endEdge(), pgrouting::trsp::EdgeInfo::connect_startEdge(), pgrouting::trsp::EdgeInfo::cost(), pgrouting::trsp::EdgeInfo::endNode(), m_edges, pgrouting::trsp::EdgeInfo::r_cost(), and pgrouting::trsp::EdgeInfo::startNode().

Referenced by addEdge().

466  {
467  EdgeInfo &firstEdge = m_edges[firstEdge_idx];
468  EdgeInfo &secondEdge = m_edges[secondEdge_idx];
469 
470  if (firstEdge.r_cost() >= 0.0) {
471  firstEdge.connect_startEdge(secondEdge_idx);
472  }
473 
474  if (firstEdge.startNode() == secondEdge.startNode()
475  && secondEdge.r_cost() >= 0.0) {
476  secondEdge.connect_startEdge(firstEdge_idx);
477  }
478 
479  if (firstEdge.startNode() == secondEdge.endNode()
480  &&secondEdge.cost() >= 0.0) {
481  secondEdge.connect_endEdge(firstEdge_idx);
482  }
483 }
std::vector< EdgeInfo > m_edges

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::trsp::Pgr_trspHandler::construct_graph ( pgr_edge_t edges,
const size_t  edge_count,
const bool  directed 
)
private

Definition at line 436 of file pgr_trspHandler.cpp.

References addEdge(), and m_mapEdgeId2Index.

Referenced by Pgr_trspHandler().

439  {
440 
441  for (size_t i = 0; i < edge_count; i++) {
442  auto current_edge = &edges[i];
443 
444  /*
445  * making all costs > 0
446  */
447  if (current_edge->cost < 0 && current_edge->reverse_cost > 0) {
448  std::swap(current_edge->cost, current_edge->reverse_cost);
449  std::swap(current_edge->source, current_edge->target);
450  }
451 
452  if (!directed) {
453  if (current_edge->reverse_cost < 0) {
454  current_edge->reverse_cost = current_edge->cost;
455  }
456  }
457  addEdge(*current_edge);
458  }
459  m_mapEdgeId2Index.clear();
460 }
bool addEdge(const pgr_edge_t edgeIn)
std::map< int64_t, int64_t > m_mapEdgeId2Index
Used only to veryfy that there are no reppetitions inserted the way it orks, repeating edges id is no...

Here is the call graph for this function:

Here is the caller graph for this function:

double pgrouting::trsp::Pgr_trspHandler::construct_path ( int64_t  ed_id,
Position  pos 
)
private

Definition at line 97 of file pgr_trspHandler.cpp.

References Path_t::cost, Path_t::edge, ILLEGAL, m_dCost, m_edges, m_parent, m_path, m_start_vertex, Path_t::node, pgassert, Path::push_back(), RC_EDGE, and Path::start_id().

Referenced by process_trsp().

97  {
98  pgassert(pos != ILLEGAL);
99 
100  if (m_parent[ed_id].isIllegal(pos)) {
101  Path_t pelement;
102  auto cur_edge = &m_edges[ed_id];
103  if (pos == RC_EDGE) {
104  pelement.node = cur_edge->startNode();
105  pelement.cost = cur_edge->cost();
106  } else {
107  pelement.node = cur_edge->endNode();
108  pelement.cost = cur_edge->r_cost();
109  }
110  pelement.edge = cur_edge->edgeID();
111 
112  m_path.push_back(pelement);
114  return pelement.cost;
115  }
116 
117  double ret = construct_path(m_parent[ed_id].e_idx[pos],
118  m_parent[ed_id].v_pos[pos]);
119  Path_t pelement;
120  auto cur_edge = &m_edges[ed_id];
121  if (pos == RC_EDGE) {
122  pelement.node = cur_edge->startNode();
123  pelement.cost = m_dCost[ed_id].endCost - ret;
124  ret = m_dCost[ed_id].endCost;
125  } else {
126  pelement.node = cur_edge->endNode();
127  pelement.cost = m_dCost[ed_id].startCost - ret;
128  ret = m_dCost[ed_id].startCost;
129  }
130  pelement.edge = cur_edge->edgeID();
131 
132  m_path.push_back(pelement);
133 
134  return ret;
135 }
double cost
Definition: path_t.h:39
void push_back(Path_t data)
int64_t edge
Definition: path_t.h:38
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t node
Definition: path_t.h:37
std::vector< CostHolder > m_dCost
Definition: path_t.h:36
int64_t start_id() const
std::vector< EdgeInfo > m_edges
double construct_path(int64_t ed_id, Position pos)
std::vector< Predecessor > m_parent

Here is the call graph for this function:

Here is the caller graph for this function:

EdgeInfo pgrouting::trsp::Pgr_trspHandler::dijkstra_exploration ( )
private

Definition at line 354 of file pgr_trspHandler.cpp.

References pgrouting::trsp::EdgeInfo::cost(), current_node, pgrouting::trsp::EdgeInfo::endNode(), explore(), m_edges, m_end_vertex, m_start_vertex, pgassert, que, pgrouting::trsp::EdgeInfo::r_cost(), and pgrouting::trsp::EdgeInfo::startNode().

Referenced by process_trsp().

354  {
355  EdgeInfo cur_edge;
357 
358  while (!que.empty()) {
359  auto cur_pos = que.top();
360  que.pop();
361 
362  auto cure_idxex = cur_pos.second.first;
363  cur_edge = m_edges[cure_idxex];
364 
365  if (cur_pos.second.second) {
366  /*
367  * explore edges connected to end node
368  */
369  current_node = cur_edge.endNode();
370  if (cur_edge.cost() < 0.0) continue;
371  if (current_node == m_end_vertex) break;
372  explore(current_node, cur_edge, false);
373  } else {
374  /*
375  * explore edges connected to start node
376  */
377  current_node = cur_edge.startNode();
378  if (cur_edge.r_cost() < 0.0) continue;
379  if (current_node == m_end_vertex) break;
380  explore(current_node, cur_edge, true);
381  }
382  }
383  return cur_edge;
384 }
std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > que
void explore(int64_t cur_node, const EdgeInfo cur_edge, bool isStart)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::vector< EdgeInfo > m_edges

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::trsp::Pgr_trspHandler::explore ( int64_t  cur_node,
const EdgeInfo  cur_edge,
bool  isStart 
)
private

Definition at line 186 of file pgr_trspHandler.cpp.

References add_to_que(), C_EDGE, edge::cost, pgrouting::trsp::EdgeInfo::get_idx(), get_tot_cost(), getRestrictionCost(), pgrouting::trsp::EdgeInfo::idx(), m_dCost, m_edges, m_parent, and RC_EDGE.

Referenced by dijkstra_exploration().

189  {
190  double extra_cost = 0.0;
191  double totalCost;
192 
193  auto vecIndex = cur_edge.get_idx(isStart);
194 
195  for (const auto &index : vecIndex) {
196  auto edge = m_edges[index];
197 
198  extra_cost = getRestrictionCost(
199  cur_edge.idx(),
200  edge, isStart);
201 
202  if ((edge.startNode() == cur_node) && (edge.cost() >= 0.0)) {
203  totalCost = get_tot_cost(
204  edge.cost() + extra_cost,
205  cur_edge.idx(),
206  isStart);
207 
208  if (totalCost < m_dCost[index].endCost) {
209  m_dCost[index].endCost = totalCost;
210  m_parent[edge.idx()].v_pos[RC_EDGE] = (isStart? C_EDGE : RC_EDGE);
211  m_parent[edge.idx()].e_idx[RC_EDGE] =
212  cur_edge.idx();
213 
214  add_to_que(totalCost, edge.idx(), true);
215  }
216  }
217 
218  if ((edge.endNode() == cur_node) && (edge.r_cost() >= 0.0)) {
219  totalCost = get_tot_cost(
220  edge.r_cost() + extra_cost,
221  cur_edge.idx(),
222  isStart);
223 
224  if (totalCost < m_dCost[index].startCost) {
225  m_dCost[index].startCost = totalCost;
226  m_parent[edge.idx()].v_pos[C_EDGE] = (isStart? C_EDGE : RC_EDGE);
227  m_parent[edge.idx()].e_idx[C_EDGE] = cur_edge.idx();
228 
229  add_to_que(totalCost, edge.idx(), false);
230  }
231  }
232  } // for
233 }
float8 cost
Definition: trsp.h:35
double getRestrictionCost(int64_t cur_node, const EdgeInfo &new_edge, bool isStart)
Definition: trsp.h:31
double get_tot_cost(double cost, size_t edge_idx, bool isStart)
void add_to_que(double cost, size_t e_idx, bool isStart)
std::vector< CostHolder > m_dCost
std::vector< EdgeInfo > m_edges
std::vector< Predecessor > m_parent

Here is the call graph for this function:

Here is the caller graph for this function:

double pgrouting::trsp::Pgr_trspHandler::get_tot_cost ( double  cost,
size_t  edge_idx,
bool  isStart 
)
private

Definition at line 172 of file pgr_trspHandler.cpp.

References m_dCost.

Referenced by explore().

175  {
176  if (isStart) {
177  return m_dCost[edge_idx].startCost +
178  cost;
179  }
180  return m_dCost[edge_idx].endCost +
181  cost;
182 }
std::vector< CostHolder > m_dCost

Here is the caller graph for this function:

double pgrouting::trsp::Pgr_trspHandler::getRestrictionCost ( int64_t  cur_node,
const EdgeInfo new_edge,
bool  isStart 
)
private

Definition at line 139 of file pgr_trspHandler.cpp.

References C_EDGE, pgrouting::trsp::EdgeInfo::edgeID(), m_edges, m_parent, m_ruleTable, pgassert, and RC_EDGE.

Referenced by explore().

142  {
143  double cost = 0.0;
144  int64_t edge_id = edge.edgeID();
145  if (m_ruleTable.find(edge_id) == m_ruleTable.end()) {
146  return(0.0);
147  }
148  auto vecRules = m_ruleTable[edge_id];
149  int64_t st_edge_ind = edge_ind;
150  for (const auto &rule : vecRules) {
151  bool flag = true;
152  int64_t v_pos = (isStart? C_EDGE : RC_EDGE);
153  edge_ind = st_edge_ind;
154 
155  pgassert(!(edge_ind == -1));
156  for (auto const &precedence : rule.precedencelist()) {
157  if (precedence != m_edges[edge_ind].edgeID()) {
158  flag = false;
159  break;
160  }
161  auto m_parent_ind = m_parent[edge_ind].e_idx[v_pos];
162  v_pos = m_parent[edge_ind].v_pos[v_pos];
163  edge_ind = m_parent_ind;
164  }
165  if (flag)
166  cost += rule.cost();
167  }
168  return cost;
169 }
Definition: trsp.h:31
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::vector< EdgeInfo > m_edges
std::map< int64_t, std::vector< Rule > > m_ruleTable
std::vector< Predecessor > m_parent

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::trsp::Pgr_trspHandler::initialize_que ( )
private

Definition at line 330 of file pgr_trspHandler.cpp.

References add_to_que(), pgrouting::trsp::EdgeInfo::cost(), pgrouting::trsp::EdgeInfo::endNode(), pgrouting::trsp::EdgeInfo::idx(), ILLEGAL, m_adjacency, m_dCost, m_edges, m_parent, m_start_vertex, pgrouting::trsp::EdgeInfo::r_cost(), and pgrouting::trsp::EdgeInfo::startNode().

Referenced by process_trsp().

330  {
331  /*
332  * For each adjacent edge to the start_vertex
333  */
334  for (const auto source : m_adjacency[m_start_vertex]) {
335  EdgeInfo &cur_edge = m_edges[source];
336 
337  if (cur_edge.startNode() == m_start_vertex
338  && cur_edge.cost() >= 0.0) {
339  m_dCost[cur_edge.idx()].endCost = cur_edge.cost();
340  m_parent[cur_edge.idx()].v_pos[0] = ILLEGAL;
341  add_to_que(cur_edge.cost(), cur_edge.idx(), true);
342  }
343 
344  if (cur_edge.endNode() == m_start_vertex
345  && cur_edge.r_cost() >= 0.0) {
346  m_dCost[cur_edge.idx()].startCost =
347  cur_edge.r_cost();
348  m_parent[cur_edge.idx()].v_pos[1] = ILLEGAL;
349  add_to_que(cur_edge.r_cost(), cur_edge.idx(), false);
350  }
351  }
352 }
void add_to_que(double cost, size_t e_idx, bool isStart)
std::map< int64_t, std::vector< size_t > > m_adjacency
m_adjacency[vertex] = {edges}
std::vector< CostHolder > m_dCost
std::vector< EdgeInfo > m_edges
std::vector< Predecessor > m_parent

Here is the call graph for this function:

Here is the caller graph for this function:

int pgrouting::trsp::Pgr_trspHandler::initialize_restrictions ( const std::vector< Rule > &  ruleList)
private

Definition at line 238 of file pgr_trspHandler.cpp.

References m_ruleTable.

Referenced by Pgr_trspHandler().

239  {
240  for (const auto rule : ruleList) {
241  auto dest_edge_id = rule.dest_id();
242  if (m_ruleTable.find(dest_edge_id) != m_ruleTable.end()) {
243  m_ruleTable[dest_edge_id].push_back(rule);
244  } else {
245  std::vector<Rule> r;
246  r.push_back(rule);
247  m_ruleTable.insert(std::make_pair(dest_edge_id, r));
248  }
249  }
250 
251  return true;
252 }
std::map< int64_t, std::vector< Rule > > m_ruleTable

Here is the caller graph for this function:

Path pgrouting::trsp::Pgr_trspHandler::process ( const int64_t  start_vertex,
const int64_t  end_vertex 
)

process

does the processisng

Definition at line 260 of file pgr_trspHandler.cpp.

References clear(), m_adjacency, m_edges, m_end_vertex, m_min_id, m_path, m_start_vertex, and process_trsp().

Referenced by do_trsp(), and process().

262  {
263  clear();
264 
265  m_start_vertex = start_vertex - m_min_id;
266  m_end_vertex = end_vertex - m_min_id;
267 
269  m_path = tmp;
270 
271  if (m_adjacency.find(m_start_vertex) == m_adjacency.end()) {
272  return Path();
273  }
274 
275  if (m_adjacency.find(m_end_vertex) == m_adjacency.end()) {
276  return Path();
277  }
278 
279  return process_trsp(m_edges.size());
280 }
Path process_trsp(size_t edge_count)
std::map< int64_t, std::vector< size_t > > m_adjacency
m_adjacency[vertex] = {edges}
std::vector< EdgeInfo > m_edges

Here is the call graph for this function:

Here is the caller graph for this function:

std::deque< Path > pgrouting::trsp::Pgr_trspHandler::process ( const std::vector< int64_t >  sources,
const std::vector< int64_t >  targets 
)

process

does many to many processisng

Definition at line 293 of file pgr_trspHandler.cpp.

References Path::end_id(), process(), and Path::start_id().

295  {
296  std::deque<Path> paths;
297  for (const auto &s : sources) {
298  for (const auto &t : targets) {
299  paths.push_back(process(s, t));
300  }
301  }
302 
303  std::sort(paths.begin(), paths.end(),
304  [](const Path &e1, const Path &e2)->bool {
305  return e1.end_id() < e2.end_id();
306  });
307  std::stable_sort(paths.begin(), paths.end(),
308  [](const Path &e1, const Path &e2)->bool {
309  return e1.start_id() < e2.start_id();
310  });
311  return paths;
312 }
int64_t end_id() const
int64_t start_id() const
Path process(const int64_t start_vertex, const int64_t end_vertex)
process

Here is the call graph for this function:

Path pgrouting::trsp::Pgr_trspHandler::process_trsp ( size_t  edge_count)
private

Definition at line 390 of file pgr_trspHandler.cpp.

References C_EDGE, construct_path(), current_node, dijkstra_exploration(), Path::end_id(), initialize_que(), m_dCost, m_end_vertex, m_min_id, m_parent, m_path, m_start_vertex, Path_t::node, pgassert, Path::push_back(), RC_EDGE, Path::renumber_vertices(), and Path::start_id().

Referenced by process().

391  {
394  pgassert(m_parent.empty());
395 
396  m_parent.resize(edge_count + 1);
397  m_dCost.resize(edge_count + 1);
398 
399  initialize_que();
400 
402 
404 
405  auto cur_edge = dijkstra_exploration();
406 
408  if (current_node != m_end_vertex) {
410  return result.renumber_vertices(m_min_id);;
411  }
412 
414 
415  if (current_node == cur_edge.startNode()) {
416  construct_path(cur_edge.idx(), C_EDGE);
417  } else {
418  construct_path(cur_edge.idx(), RC_EDGE);
419  }
420 
421  Path_t pelement;
422  pelement.node = m_end_vertex;
423  pelement.edge = -1;
424  pelement.cost = 0.0;
425  m_path.push_back(pelement);
426 
427  m_path.Path::recalculate_agg_cost();
429 }
Path & renumber_vertices(int64_t value)
void push_back(Path_t data)
int64_t end_id() const
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t node
Definition: path_t.h:37
std::vector< CostHolder > m_dCost
Definition: path_t.h:36
int64_t start_id() const
double construct_path(int64_t ed_id, Position pos)
std::vector< Predecessor > m_parent

Here is the call graph for this function:

Here is the caller graph for this function:

int64_t pgrouting::trsp::Pgr_trspHandler::renumber_edges ( pgr_edge_t edges,
const size_t  edge_count 
) const
private

Definition at line 64 of file pgr_trspHandler.cpp.

References pgr_edge_t::source, and pgr_edge_t::target.

Referenced by Pgr_trspHandler().

66  {
67  int64_t v_min_id = UINT64_MAX;
68  size_t z;
69  for (z = 0; z < total_edges; z++) {
70  if (edges[z].source < v_min_id)
71  v_min_id = edges[z].source;
72 
73  if (edges[z].target < v_min_id)
74  v_min_id = edges[z].target;
75  }
76 
77  for (z = 0; z < total_edges; z++) {
78  edges[z].source -= v_min_id;
79  edges[z].target -= v_min_id;
80  }
81 
82  return v_min_id;
83 }
int64_t source
Definition: pgr_edge_t.h:60
int64_t target
Definition: pgr_edge_t.h:61

Here is the caller graph for this function:

Member Data Documentation

int64_t pgrouting::trsp::Pgr_trspHandler::current_node
private

Definition at line 198 of file pgr_trspHandler.h.

Referenced by dijkstra_exploration(), and process_trsp().

std::map<int64_t, std::vector<size_t> > pgrouting::trsp::Pgr_trspHandler::m_adjacency
private

m_adjacency[vertex] = {edges}

Definition at line 189 of file pgr_trspHandler.h.

Referenced by addEdge(), initialize_que(), and process().

std::vector<CostHolder> pgrouting::trsp::Pgr_trspHandler::m_dCost
private
std::vector<EdgeInfo> pgrouting::trsp::Pgr_trspHandler::m_edges
private
int64_t pgrouting::trsp::Pgr_trspHandler::m_end_vertex
private

Definition at line 193 of file pgr_trspHandler.h.

Referenced by dijkstra_exploration(), process(), and process_trsp().

std::map<int64_t, int64_t> pgrouting::trsp::Pgr_trspHandler::m_mapEdgeId2Index
private

Used only to veryfy that there are no reppetitions inserted the way it orks, repeating edges id is not allowed.

Definition at line 184 of file pgr_trspHandler.h.

Referenced by addEdge(), and construct_graph().

int64_t pgrouting::trsp::Pgr_trspHandler::m_min_id
private

Definition at line 200 of file pgr_trspHandler.h.

Referenced by Pgr_trspHandler(), process(), and process_trsp().

std::vector<Predecessor> pgrouting::trsp::Pgr_trspHandler::m_parent
private
Path pgrouting::trsp::Pgr_trspHandler::m_path
private

Definition at line 202 of file pgr_trspHandler.h.

Referenced by clear(), construct_path(), process(), and process_trsp().

std::map<int64_t, std::vector<Rule> > pgrouting::trsp::Pgr_trspHandler::m_ruleTable
private

Definition at line 207 of file pgr_trspHandler.h.

Referenced by getRestrictionCost(), and initialize_restrictions().

int64_t pgrouting::trsp::Pgr_trspHandler::m_start_vertex
private
std::priority_queue<PDP, std::vector<PDP>, std::greater<PDP> > pgrouting::trsp::Pgr_trspHandler::que
private

Definition at line 212 of file pgr_trspHandler.h.

Referenced by add_to_que(), and dijkstra_exploration().


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