PGROUTING  3.2
pgr_binaryBreadthFirstSearch.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_binaryBreadthFirstSearch.hpp
3 
4 Copyright (c) 2019 pgRouting developers
6 
7 Copyright (c) 2019 Gudesa Venkata Sai AKhil
9 
10 ------
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 ********************************************************************PGR-GNU*/
23 
24 #ifndef INCLUDE_BREADTHFIRSTSEARCH_PGR_BINARYBREADTHFIRSTSEARCH_HPP_
25 #define INCLUDE_BREADTHFIRSTSEARCH_PGR_BINARYBREADTHFIRSTSEARCH_HPP_
26 #pragma once
27 
28 #include <deque>
29 #include <algorithm>
30 #include <cmath>
31 #include <limits>
32 #include <vector>
33 #include <map>
34 
37 #include "cpp_common/pgr_assert.h"
38 //******************************************
39 
40 namespace pgrouting {
41 namespace functions {
42 
43 template <class G>
45  public:
46  typedef typename G::V V;
47  typedef typename G::E E;
48  typedef typename G::B_G B_G;
49  typedef typename G::EO_i EO_i;
50  typedef typename G::E_i E_i;
51 
52  std::deque<Path> binaryBreadthFirstSearch(
53  G &graph,
54  std::vector<int64_t> start_vertex,
55  std::vector<int64_t> end_vertex) {
56  std::deque<Path> paths;
57 
58  for (auto source : start_vertex) {
59  std::deque<Path> result_paths = one_to_many_binaryBreadthFirstSearch(
60  graph,
61  source,
62  end_vertex);
63  paths.insert(
64  paths.begin(),
65  std::make_move_iterator(result_paths.begin()),
66  std::make_move_iterator(result_paths.end()));
67  }
68 
69  std::sort(paths.begin(), paths.end(),
70  [](const Path &e1, const Path &e2) -> bool {
71  return e1.end_id() < e2.end_id();
72  });
73  std::stable_sort(paths.begin(), paths.end(),
74  [](const Path &e1, const Path &e2) -> bool {
75  return e1.start_id() < e2.start_id();
76  });
77 
78  return paths;
79  }
80 
81  // preparation for parallel arrays
82  std::deque<Path> binaryBreadthFirstSearch(
83  G &graph,
84  const std::vector<pgr_combination_t> &combinations) {
85  std::deque<Path> paths;
86 
87  // group targets per distinct source
88  std::map< int64_t, std::vector<int64_t> > vertex_map;
89  for (const pgr_combination_t &comb : combinations) {
90  std::map< int64_t, std::vector<int64_t> >::iterator it = vertex_map.find(comb.source);
91  if (it != vertex_map.end()) {
92  it->second.push_back(comb.target);
93  } else {
94  std::vector<int64_t > targets{comb.target};
95  vertex_map[comb.source] = targets;
96  }
97  }
98 
99  for (const auto &start_ends : vertex_map) {
100  std::deque<Path> result_paths = one_to_many_binaryBreadthFirstSearch(
101  graph,
102  start_ends.first,
103  start_ends.second);
104  paths.insert(
105  paths.begin(),
106  std::make_move_iterator(result_paths.begin()),
107  std::make_move_iterator(result_paths.end()));
108  }
109 
110  std::sort(paths.begin(), paths.end(),
111  [](const Path &e1, const Path &e2) -> bool {
112  return e1.end_id() < e2.end_id();
113  });
114  std::stable_sort(paths.begin(), paths.end(),
115  [](const Path &e1, const Path &e2) -> bool {
116  return e1.start_id() < e2.start_id();
117  });
118 
119  return paths;
120  }
121 
122  private:
124 
126  G &graph,
127  int64_t start_vertex,
128  std::vector<int64_t> end_vertex) {
129  std::deque<Path> paths;
130 
131  if (graph.has_vertex(start_vertex) == false) {
132  return paths;
133  }
134 
135  std::vector<double> current_cost(graph.num_vertices(), std::numeric_limits<double>::infinity());
136  std::vector<E> from_edge(graph.num_vertices());
137  std::deque<V> dq;
138  DEFAULT_EDGE = from_edge[0];
139 
140  auto bgl_start_vertex = graph.get_V(start_vertex);
141 
142  current_cost[bgl_start_vertex] = 0;
143  dq.push_front(bgl_start_vertex);
144 
145  while (dq.empty() == false) {
146  auto head_vertex = dq.front();
147 
148  dq.pop_front();
149 
150  updateVertexCosts(graph, current_cost, from_edge, dq, head_vertex);
151  }
152 
153  for (auto target_vertex : end_vertex) {
154  if (graph.has_vertex(target_vertex) == false) {
155  continue;
156  }
157 
158  auto bgl_target_vertex = graph.get_V(target_vertex);
159 
160  if (from_edge[bgl_target_vertex] == DEFAULT_EDGE) {
161  continue;
162  }
163 
164  paths.push_front(
165  getPath(graph, bgl_start_vertex, target_vertex, bgl_target_vertex, from_edge, current_cost));
166  }
167 
168  return paths;
169  }
170 
172  G &graph,
173  V bgl_start_vertex,
174  int64_t target,
175  V bgl_target_vertex,
176  std::vector<E> &from_edge,
177  std::vector<double> &current_cost) {
178  auto current_node = bgl_target_vertex;
179 
180  Path path = Path(graph[bgl_start_vertex].id, graph[current_node].id);
181 
182  path.push_back({target, -1, 0, current_cost[current_node]});
183 
184  do {
185  E e = from_edge[current_node];
186  auto from = graph.source(e);
187 
188  path.push_back({graph[from].id, graph[e].id, graph[e].cost, current_cost[from]});
189 
190  current_node = from;
191  } while (from_edge[current_node] != DEFAULT_EDGE);
192 
193  std::reverse(path.begin(), path.end());
194  return path;
195  }
196 
197 
199  G &graph,
200  std::vector<double> &current_cost,
201  std::vector<E> &from_edge,
202  std::deque<V> &dq,
203  V &head_vertex) {
204  auto out_edges = boost::out_edges(head_vertex, graph.graph);
205  E e;
206  EO_i out_i;
207  EO_i out_end;
208  V v_source, v_target;
209 
210  for (boost::tie(out_i, out_end) = out_edges;
211  out_i != out_end; ++out_i) {
212  e = *out_i;
213  v_target = graph.target(e);
214  v_source = graph.source(e);
215  double edge_cost = graph[e].cost;
216 
217  if (std::isinf(current_cost[v_target]) || current_cost[v_source] + edge_cost < current_cost[v_target]) {
218  current_cost[v_target] = current_cost[v_source] + edge_cost;
219 
220  from_edge[v_target] = e;
221 
222  if (edge_cost != 0) {
223  dq.push_back(v_target);
224  } else {
225  dq.push_front(v_target);
226  }
227  }
228  }
229  }
230 };
231 } // namespace functions
232 } // namespace pgrouting
233 
234 #endif // INCLUDE_BREADTHFIRSTSEARCH_PGR_BINARYBREADTHFIRSTSEARCH_HPP_
Path
Definition: basePath_SSEC.hpp:47
Path::push_back
void push_back(Path_t data)
Definition: basePath_SSEC.cpp:52
pgrouting::functions::Pgr_binaryBreadthFirstSearch::EO_i
G::EO_i EO_i
Definition: pgr_binaryBreadthFirstSearch.hpp:49
pgr_base_graph.hpp
pgrouting::functions::Pgr_binaryBreadthFirstSearch::one_to_many_binaryBreadthFirstSearch
std::deque< Path > one_to_many_binaryBreadthFirstSearch(G &graph, int64_t start_vertex, std::vector< int64_t > end_vertex)
Definition: pgr_binaryBreadthFirstSearch.hpp:125
pgrouting::functions::Pgr_binaryBreadthFirstSearch::V
G::V V
Definition: pgr_binaryBreadthFirstSearch.hpp:46
Path::end
pthIt end()
Definition: basePath_SSEC.hpp:82
pgrouting::functions::Pgr_binaryBreadthFirstSearch
Definition: pgr_binaryBreadthFirstSearch.hpp:44
pgrouting::functions::Pgr_binaryBreadthFirstSearch::binaryBreadthFirstSearch
std::deque< Path > binaryBreadthFirstSearch(G &graph, std::vector< int64_t > start_vertex, std::vector< int64_t > end_vertex)
Definition: pgr_binaryBreadthFirstSearch.hpp:52
pgrouting::functions::Pgr_binaryBreadthFirstSearch::B_G
G::B_G B_G
Definition: pgr_binaryBreadthFirstSearch.hpp:48
pgrouting::alphashape::E
boost::graph_traits< BG >::edge_descriptor E
Definition: pgr_alphaShape.h:57
pgr_combination_t
Definition: pgr_combination_t.h:43
pgr_assert.h
An assert functionality that uses C++ throw().
pgrouting::functions::Pgr_binaryBreadthFirstSearch::binaryBreadthFirstSearch
std::deque< Path > binaryBreadthFirstSearch(G &graph, const std::vector< pgr_combination_t > &combinations)
Definition: pgr_binaryBreadthFirstSearch.hpp:82
pgrouting::functions::Pgr_binaryBreadthFirstSearch::getPath
Path getPath(G &graph, V bgl_start_vertex, int64_t target, V bgl_target_vertex, std::vector< E > &from_edge, std::vector< double > &current_cost)
Definition: pgr_binaryBreadthFirstSearch.hpp:171
pgrouting::alphashape::G
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
Definition: pgr_alphaShape.h:56
pgrouting::functions::Pgr_binaryBreadthFirstSearch::E_i
G::E_i E_i
Definition: pgr_binaryBreadthFirstSearch.hpp:50
pgrouting::functions::Pgr_binaryBreadthFirstSearch::DEFAULT_EDGE
E DEFAULT_EDGE
Definition: pgr_binaryBreadthFirstSearch.hpp:123
pgrouting::functions::Pgr_binaryBreadthFirstSearch::E
G::E E
Definition: pgr_binaryBreadthFirstSearch.hpp:47
pgrouting::functions::Pgr_binaryBreadthFirstSearch::updateVertexCosts
void updateVertexCosts(G &graph, std::vector< double > &current_cost, std::vector< E > &from_edge, std::deque< V > &dq, V &head_vertex)
Definition: pgr_binaryBreadthFirstSearch.hpp:198
pgrouting::alphashape::V
boost::graph_traits< BG >::vertex_descriptor V
Definition: pgr_alphaShape.h:58
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56
Path::begin
pthIt begin()
Definition: basePath_SSEC.hpp:81
basePath_SSEC.hpp