PGROUTING  2.6-dev
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 44 of file pgr_dijkstraTRSP.hpp.

Member Typedef Documentation

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

Definition at line 63 of file pgr_dijkstraTRSP.hpp.

Member Function Documentation

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

Definition at line 80 of file pgr_dijkstraTRSP.hpp.

Referenced by Pgr_dijkstraTRSP< G >::executeDijkstraTRSP().

80  {
81 }

Here is the caller graph for this function:

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 85 of file pgr_dijkstraTRSP.hpp.

References Pgr_dijkstraTRSP< G >::curr_result_path, DIRECTED, Pgr_dijkstraTRSP< G >::executeDijkstraTRSP(), Pgr_dijkstraTRSP< G >::log, Pgr_dijkstraTRSP< G >::m_end, Pgr_dijkstraTRSP< G >::m_only_cost, Pgr_dijkstraTRSP< G >::m_restrictions, Pgr_dijkstraTRSP< G >::m_start, Pgr_dijkstraTRSP< G >::m_strict, Path::size(), UNDIRECTED, Pgr_dijkstraTRSP< G >::v_source, and Pgr_dijkstraTRSP< G >::v_target.

Referenced by pgr_dijkstraTRSP().

92  {
93  if (start_vertex == end_vertex)
94  return Path();
95  if (!graph.has_vertex(start_vertex) || !graph.has_vertex(end_vertex))
96  return Path();
97 
98  m_only_cost = only_cost;
99  v_source = graph.get_V(start_vertex);
100  v_target = graph.get_V(end_vertex);
101  m_start = start_vertex;
102  m_end = end_vertex;
103  m_restrictions = restrictions;
104  m_strict = strict;
105  executeDijkstraTRSP(graph);
106  if (curr_result_path.size() || graph.m_gType == UNDIRECTED)
107  return curr_result_path;
108 
109 #if 0
111  line.insert_vertices(edges);
112  auto line_graph_edges = line.transform(graph);
113  log << "\nGraph before removing restrictions\n" << line << "\n";
114  auto remaining_restrictions = line.remove_restricted_edges(m_restrictions);
115  log << "\n Graph after removing restrictions\n" << line << "\n";
116 
117  log << line.log.str().c_str() << "\n\n\n";
118 
119  line.create_virtual_vertices();
120  log << line << "\n";
121 #endif
122 
123  return curr_result_path;
124 }
std::vector< Restriction > m_restrictions
boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, Line_vertex, Basic_edge > LinearDirectedGraph
Data type to handle graph -> lineGaph transformation.
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 189 of file pgr_dijkstraTRSP.hpp.

References Pgr_dijkstraTRSP< G >::clear(), Pgr_dijkstraTRSP< G >::curr_result_path, Pgr_dijkstraTRSP< G >::getDijkstraSolution(), Pgr_dijkstraTRSP< G >::has_restriction(), Pgr_dijkstraTRSP< G >::log, and Pgr_dijkstraTRSP< G >::m_edges_in_path.

Referenced by Pgr_dijkstraTRSP< G >::dijkstraTRSP().

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

Definition at line 127 of file pgr_dijkstraTRSP.hpp.

References Pgr_dijkstraTRSP< G >::curr_result_path, Pgr_dijkstra< G >::dijkstra(), Path::empty(), Pgr_dijkstraTRSP< G >::m_end, and Pgr_dijkstraTRSP< G >::m_start.

Referenced by Pgr_dijkstraTRSP< G >::executeDijkstraTRSP().

127  {
128  Path path;
129 
130  Pgr_dijkstra< G > fn_dijkstra;
131  path = fn_dijkstra.dijkstra(graph, m_start, m_end);
132 
133  if (path.empty()) return;
134  curr_result_path = path;
135 }
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:

Here is the caller graph for this function:

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

Definition at line 138 of file pgr_dijkstraTRSP.hpp.

References Pgr_dijkstraTRSP< G >::log, Pgr_dijkstraTRSP< G >::m_edges_in_path, Pgr_dijkstraTRSP< G >::m_restrictions, and Restriction::restrict_edges().

Referenced by Pgr_dijkstraTRSP< G >::has_restriction().

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

Here is the caller graph for this function:

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

Definition at line 169 of file pgr_dijkstraTRSP.hpp.

References Pgr_dijkstraTRSP< G >::has_a_restriction(), Pgr_dijkstraTRSP< G >::log, Pgr_dijkstraTRSP< G >::m_edges_in_path, Pgr_dijkstraTRSP< G >::m_restrictions, and Restriction::restrict_edges().

Referenced by Pgr_dijkstraTRSP< G >::executeDijkstraTRSP().

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

Here is the caller graph for this function:

Member Data Documentation

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

Definition at line 70 of file pgr_dijkstraTRSP.hpp.

Referenced by Pgr_dijkstraTRSP< G >::dijkstraTRSP().

template<class G>
std::vector< Restriction > Pgr_dijkstraTRSP< G >::m_restrictions
private
template<class G>
int64_t Pgr_dijkstraTRSP< G >::m_start
private
template<class G>
bool Pgr_dijkstraTRSP< G >::m_strict
private

Definition at line 71 of file pgr_dijkstraTRSP.hpp.

Referenced by Pgr_dijkstraTRSP< G >::dijkstraTRSP().

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

Definition at line 64 of file pgr_dijkstraTRSP.hpp.

Referenced by Pgr_dijkstraTRSP< G >::dijkstraTRSP().

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

Definition at line 65 of file pgr_dijkstraTRSP.hpp.

Referenced by Pgr_dijkstraTRSP< G >::dijkstraTRSP().


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