PGROUTING  2.6-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgRouting Namespace Reference

Functions

template<class G >
void pgr_dijkstraVia (G &graph, const std::vector< int64_t > via_vertices, std::deque< Path > &paths, bool strict, bool U_turn_on_edge, std::ostringstream &log)
 

Function Documentation

template<class G >
void pgRouting::pgr_dijkstraVia ( G &  graph,
const std::vector< int64_t >  via_vertices,
std::deque< Path > &  paths,
bool  strict,
bool  U_turn_on_edge,
std::ostringstream &  log 
)

Definition at line 45 of file pgr_dijkstraVia.hpp.

References Path::empty(), pgr_dijkstra(), and Path::size().

Referenced by do_pgr_dijkstraVia().

51  {
52  if (via_vertices.size() == 0) {
53  return;
54  }
55 
56  paths.clear();
57  int64_t prev_vertex = via_vertices[0];
58  Path path;
59 
60  int64_t i = 0;
61  for (const auto &vertex : via_vertices) {
62  if (i == 0) {
63  prev_vertex = vertex; ++i;
64  continue;
65  }
66 
67  // Delete U Turn edges only valid for paths that are not the first path
68  if (!U_turn_on_edge && i > 1) {
69  /*
70  * Can only delete if there was a path,
71  * that is at least one edge size
72  */
73  if (path.size() > 1) {
74  /*
75  * Delete from the graph the last edge if its outgoing also
76  * edge to be removed = second to last edge path[i].edge;
77  */
78  int64_t edge_to_be_removed = path[path.size() - 2].edge;
79  int64_t last_vertex_of_path = prev_vertex;
80 
81  // and the current vertex is not a dead end
82  if (graph.out_degree(last_vertex_of_path) > 1) {
83  log << "\ndeparting from " << last_vertex_of_path
84  << " deleting edge " << edge_to_be_removed << "\n";
85  graph.disconnect_out_going_edge(
86  last_vertex_of_path,
87  edge_to_be_removed);
88  }
89  }
90  }
91 
92  log << "\nfrom " << prev_vertex << " to " << vertex;
93  path = pgr_dijkstra(graph, prev_vertex, vertex);
94 
95  if (!U_turn_on_edge && i > 1) {
96  graph.restore_graph();
97  if (path.empty()) {
98  /*
99  * no path was found with the deleted edge
100  * try with the edge back in the graph
101  */
102  log << "\nEmpty so again from "
103  << prev_vertex << " to " << vertex;
104  path = pgr_dijkstra(graph, prev_vertex, vertex);
105  }
106  }
107 
108  if (strict && path.empty()) {
109  paths.clear();
110  return;
111  }
112  paths.push_back(path);
113 
114  /*
115  * got to the next
116  */
117  prev_vertex = vertex; ++i;
118  }
119 }
std::deque< Path > pgr_dijkstra(G &graph, std::vector< int64_t > sources, std::vector< int64_t > targets, bool only_cost, bool normal)
bool empty() const
size_t size() const

Here is the call graph for this function:

Here is the caller graph for this function: