PGROUTING  3.2
pgr_breadthFirstSearch.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_breadthFirstSearch.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_BREADTHFIRSTSEARCH_HPP_
25 #define INCLUDE_BREADTHFIRSTSEARCH_PGR_BREADTHFIRSTSEARCH_HPP_
26 #pragma once
27 
28 
30 #include <boost/graph/breadth_first_search.hpp>
31 
32 #include <vector>
33 
36 //******************************************
37 
38 namespace pgrouting {
39 namespace functions {
40 
41 template <class G>
43  public:
44  typedef typename G::V V;
45  typedef typename G::E E;
46  typedef typename G::B_G B_G;
47 
48 
49  std::vector<pgr_mst_rt> breadthFirstSearch(
50  G &graph,
51  std::vector<int64_t> start_vertex,
52  int64_t depth) {
53  std::vector<pgr_mst_rt> results;
54  using bfs_visitor = visitors::Edges_order_bfs_visitor<E>;
55 
56  for (auto source : start_vertex) {
57  std::vector<E> visited_order;
58 
59  if (graph.has_vertex(source)) {
60  results.push_back({source, 0, source, -1, 0.0, 0.0});
61  boost::breadth_first_search(graph.graph,
62  graph.get_V(source),
63  visitor(bfs_visitor(visited_order)));
64 
65  auto single_source_results = get_results(visited_order, source, depth, graph);
66  results.insert(results.end(), single_source_results.begin(), single_source_results.end());
67 
68  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
69  CHECK_FOR_INTERRUPTS();
70  }
71  }
72  return results;
73  }
74 
75  private:
76  template <typename T>
77  std::vector<pgr_mst_rt> get_results(
78  T order,
79  int64_t source,
80  int64_t max_depth,
81  const G &graph) {
82  std::vector<pgr_mst_rt> results;
83 
84  std::vector<double> agg_cost(graph.num_vertices(), 0);
85  std::vector<int64_t> depth(graph.num_vertices(), 0);
86 
87  for (const auto edge : order) {
88  auto u = graph.source(edge);
89  auto v = graph.target(edge);
90 
91  agg_cost[v] = agg_cost[u] + graph[edge].cost;
92  depth[v] = depth[u] + 1;
93 
94  if (max_depth >= depth[v]) {
95  results.push_back({
96  source,
97  depth[v],
98  graph[v].id,
99  graph[edge].id,
100  graph[edge].cost,
101  agg_cost[v]
102  });
103  }
104  }
105  return results;
106  }
107 };
108 } // namespace functions
109 } // namespace pgrouting
110 
111 #endif // INCLUDE_BREADTHFIRSTSEARCH_PGR_BREADTHFIRSTSEARCH_HPP_
interruption.h
pgr_base_graph.hpp
edge
Definition: trsp.h:41
pgrouting::functions::Pgr_breadthFirstSearch
Definition: pgr_breadthFirstSearch.hpp:42
pgrouting::functions::Pgr_breadthFirstSearch::breadthFirstSearch
std::vector< pgr_mst_rt > breadthFirstSearch(G &graph, std::vector< int64_t > start_vertex, int64_t depth)
Definition: pgr_breadthFirstSearch.hpp:49
pgrouting::alphashape::E
boost::graph_traits< BG >::edge_descriptor E
Definition: pgr_alphaShape.h:57
pgrouting::functions::Pgr_breadthFirstSearch::V
G::V V
Definition: pgr_breadthFirstSearch.hpp:44
pgrouting::functions::Pgr_breadthFirstSearch::get_results
std::vector< pgr_mst_rt > get_results(T order, int64_t source, int64_t max_depth, const G &graph)
Definition: pgr_breadthFirstSearch.hpp:77
pgrouting::alphashape::G
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
Definition: pgr_alphaShape.h:56
pgrouting::functions::Pgr_breadthFirstSearch::E
G::E E
Definition: pgr_breadthFirstSearch.hpp:45
pgrouting::visitors::Edges_order_bfs_visitor
Definition: edges_order_bfs_visitor.hpp:41
pgrouting::alphashape::V
boost::graph_traits< BG >::vertex_descriptor V
Definition: pgr_alphaShape.h:58
edges_order_bfs_visitor.hpp
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56
pgrouting::functions::Pgr_breadthFirstSearch::B_G
G::B_G B_G
Definition: pgr_breadthFirstSearch.hpp:46