PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Pgr_dijkstraTRSP< G > Class Template Reference

#include "pgr_dijkstraTRSP.hpp"

Collaboration diagram for Pgr_dijkstraTRSP< G >:

Public Member Functions

void clear ()
 
Path dijkstraTRSP (G &graph, const std::vector< Restriction > &restrictions, const std::vector< pgr_edge_t > &edges, int64_t source, int64_t target, bool only_cost, bool strict)
 

Public Attributes

std::ostringstream log
 

Private Types

typedef G::V V
 

Private Member Functions

void executeDijkstraTRSP (G &graph)
 
void getDijkstraSolution (G &graph)
 
bool has_a_restriction (int64_t edge, int64_t index)
 
bool has_restriction ()
 

Private Attributes

Path curr_result_path
 
std::vector< int64_t > m_edges_in_path
 
int64_t m_end
 
bool m_only_cost
 
std::vector< Restrictionm_restrictions
 
int64_t m_start
 
bool m_strict
 
V v_source
 
V v_target
 

Detailed Description

template<class G>
class Pgr_dijkstraTRSP< G >

Definition at line 45 of file pgr_dijkstraTRSP.hpp.

Member Typedef Documentation

template<class G>
typedef G::V Pgr_dijkstraTRSP< G >::V
private

Definition at line 62 of file pgr_dijkstraTRSP.hpp.

Member Function Documentation

template<class G >
void Pgr_dijkstraTRSP< G >::clear ( )

Definition at line 79 of file pgr_dijkstraTRSP.hpp.

79  {
80 }
template<class G >
Path Pgr_dijkstraTRSP< G >::dijkstraTRSP ( G &  graph,
const std::vector< Restriction > &  restrictions,
const std::vector< pgr_edge_t > &  edges,
int64_t  source,
int64_t  target,
bool  only_cost,
bool  strict 
)

Definition at line 84 of file pgr_dijkstraTRSP.hpp.

References DIRECTED, pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::insert_vertices(), pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::log, pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::transform(), and UNDIRECTED.

Referenced by pgr_dijkstraTRSP().

91  {
92  if (start_vertex == end_vertex)
93  return Path();
94  if (!graph.has_vertex(start_vertex) || !graph.has_vertex(end_vertex))
95  return Path();
96 
97  m_only_cost = only_cost;
98  v_source = graph.get_V(start_vertex);
99  v_target = graph.get_V(end_vertex);
100  m_start = start_vertex;
101  m_end = end_vertex;
102  m_restrictions = restrictions;
103  m_strict = strict;
104  executeDijkstraTRSP(graph);
105  if (curr_result_path.size() or graph.m_gType == UNDIRECTED)
106  return curr_result_path;
107 
108 #if 0
110  line.insert_vertices(edges);
111  auto line_graph_edges = line.transform(graph);
112  log << "\nGraph before removing restrictions\n" << line << "\n";
113  auto remaining_restrictions = line.remove_restricted_edges(m_restrictions);
114  log << "\n Graph after removing restrictions\n" << line << "\n";
115 
116  log << line.log.str().c_str() << "\n\n\n";
117 
118  line.create_virtual_vertices();
119  log << line << "\n";
120 #endif
121 
122  return curr_result_path;
123 }
std::vector< Restriction > m_restrictions
void executeDijkstraTRSP(G &graph)
size_t size() const
std::ostringstream log

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G >
void Pgr_dijkstraTRSP< G >::executeDijkstraTRSP ( G &  graph)
private

Definition at line 188 of file pgr_dijkstraTRSP.hpp.

188  {
189  clear();
190  getDijkstraSolution(graph);
192 
193  for (auto &path: curr_result_path) {
194  m_edges_in_path.push_back(path.edge);
195  }
196  while (m_edges_in_path.size() and m_edges_in_path.back() == -1) {
197  m_edges_in_path.pop_back();
198  }
199 
200  log << "Edges in m_edges_in_path:-------------------\n";
201  for(auto &it: m_edges_in_path) log << it << "\n";
202  log << "---------------------------------------------\n";
203  bool sol = has_restriction();
204  log << "Result of valid solution: " << sol << "\n";
205  if (sol) curr_result_path = Path();
206 }
void getDijkstraSolution(G &graph)
std::vector< int64_t > m_edges_in_path
std::ostringstream log
template<class G >
void Pgr_dijkstraTRSP< G >::getDijkstraSolution ( G &  graph)
private

Definition at line 126 of file pgr_dijkstraTRSP.hpp.

References Pgr_dijkstra< G >::dijkstra(), and Path::empty().

126  {
127  Path path;
128 
129  Pgr_dijkstra< G > fn_dijkstra;
130  path = fn_dijkstra.dijkstra(graph, m_start, m_end);
131 
132  if (path.empty()) return;
133  curr_result_path = path;
134 }
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
bool empty() const

Here is the call graph for this function:

template<class G >
bool Pgr_dijkstraTRSP< G >::has_a_restriction ( int64_t  edge,
int64_t  index 
)
private

Definition at line 137 of file pgr_dijkstraTRSP.hpp.

References Restriction::restrict_edges().

137  {
138  auto lower_bound_cmp = [](const Restriction& r, const int64_t& target) {
139  return r.restrict_edges()[0] < target;
140  };
141  auto edge_index = std::lower_bound(m_restrictions.begin(),
142  m_restrictions.end(), edge, lower_bound_cmp) - m_restrictions.begin();
143  log << "\nResult generated from lower_bound\n";
144  while (edge_index < (int64_t)m_restrictions.size()) {
145  auto r_edges = m_restrictions[edge_index].restrict_edges();
146  if (r_edges[0] != edge) break;
147  log << m_restrictions[edge_index] << "\n";
148  bool okay = true;
149  size_t temp_edge_index = index;
150 
151  for (auto &edge_id: r_edges) {
152  if (temp_edge_index >= m_edges_in_path.size() or
153  m_edges_in_path[temp_edge_index] != edge_id) {
154  okay = false;
155  break;
156  }
157  temp_edge_index++;
158  }
159  log << "\nokay value = " << okay <<"\n";
160  if (okay) return true;
161  edge_index++;
162  }
163  log << "Ends Here\n";
164  return false;
165 }
std::vector< Restriction > m_restrictions
Definition: trsp.h:31
std::vector< int64_t > m_edges_in_path
std::ostringstream log
std::vector< int64_t > restrict_edges() const
Definition: restriction.h:54

Here is the call graph for this function:

template<class G >
bool Pgr_dijkstraTRSP< G >::has_restriction ( )
private

Definition at line 168 of file pgr_dijkstraTRSP.hpp.

References Restriction::restrict_edges().

168  {
169  auto sort_cmp = [](const Restriction& left,
170  const Restriction& right) -> bool {
171  return left.restrict_edges()[0] <= right.restrict_edges()[0];
172  };
173  std::stable_sort(m_restrictions.begin(), m_restrictions.end(),
174  sort_cmp);
175  log << "\nRestriction array after sorting.\n";
176  for (auto &it: m_restrictions) log << it << "\n";
177  log << "\nEnd\n";
178  size_t index = 0;
179  for (auto &edge: m_edges_in_path) {
180  if (has_a_restriction(edge, index))
181  return true;
182  index++;
183  }
184  return false;
185 }
std::vector< Restriction > m_restrictions
Definition: trsp.h:31
std::vector< int64_t > m_edges_in_path
bool has_a_restriction(int64_t edge, int64_t index)
std::ostringstream log
std::vector< int64_t > restrict_edges() const
Definition: restriction.h:54

Here is the call graph for this function:

Member Data Documentation

template<class G>
Path Pgr_dijkstraTRSP< G >::curr_result_path
private

Definition at line 72 of file pgr_dijkstraTRSP.hpp.

template<class G>
std::ostringstream Pgr_dijkstraTRSP< G >::log

Definition at line 75 of file pgr_dijkstraTRSP.hpp.

Referenced by pgr_dijkstraTRSP().

template<class G>
std::vector< int64_t > Pgr_dijkstraTRSP< G >::m_edges_in_path
private

Definition at line 68 of file pgr_dijkstraTRSP.hpp.

template<class G>
int64_t Pgr_dijkstraTRSP< G >::m_end
private

Definition at line 66 of file pgr_dijkstraTRSP.hpp.

template<class G>
bool Pgr_dijkstraTRSP< G >::m_only_cost
private

Definition at line 69 of file pgr_dijkstraTRSP.hpp.

template<class G>
std::vector< Restriction > Pgr_dijkstraTRSP< G >::m_restrictions
private

Definition at line 67 of file pgr_dijkstraTRSP.hpp.

template<class G>
int64_t Pgr_dijkstraTRSP< G >::m_start
private

Definition at line 65 of file pgr_dijkstraTRSP.hpp.

template<class G>
bool Pgr_dijkstraTRSP< G >::m_strict
private

Definition at line 70 of file pgr_dijkstraTRSP.hpp.

template<class G>
V Pgr_dijkstraTRSP< G >::v_source
private

Definition at line 63 of file pgr_dijkstraTRSP.hpp.

template<class G>
V Pgr_dijkstraTRSP< G >::v_target
private

Definition at line 64 of file pgr_dijkstraTRSP.hpp.


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