PGROUTING  2.6-dev
pgr_bdDijkstra.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 File: pgr_bdDijkstra.hpp
4 
5 Copyright (c) 2016 Celia Virginia Vergara Castillo
6 vicky_vergara@hotmail.com
7 
8 ------
9 
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14 
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 
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 
24  ********************************************************************PGR-GNU*/
25 
26 #ifndef INCLUDE_BDDIJKSTRA_PGR_BDDIJKSTRA_HPP_
27 #define INCLUDE_BDDIJKSTRA_PGR_BDDIJKSTRA_HPP_
28 #pragma once
29 
30 
32 
33 #include <string>
34 #include <queue>
35 #include <utility>
36 #include <vector>
37 #include <limits>
38 #include <functional>
39 
40 
42 
43 
44 namespace pgrouting {
45 namespace bidirectional {
46 
47 
48 template < typename G >
49 class Pgr_bdDijkstra : public Pgr_bidirectional<G> {
50  typedef typename Pgr_bidirectional<G>::V V;
51  typedef typename Pgr_bidirectional<G>::E E;
53 
58 
64 
70 
71 
73 
74  public:
75  explicit Pgr_bdDijkstra(G &pgraph):
76  Pgr_bidirectional<G>(pgraph) {
77  m_log << "pgr_bdDijkstra constructor\n";
78  }
79 
80  ~Pgr_bdDijkstra() = default;
81 
82  Path pgr_bdDijkstra(V start_vertex, V end_vertex, bool only_cost) {
83  m_log << "pgr_bdDijkstra\n";
84  v_source = start_vertex;
85  v_target = end_vertex;
86 
87  if (v_source == v_target) {
88  return Path(v_source, v_target);
89  }
90  return bidirectional(only_cost);
91  }
92 
93 
96 
97 
98  private:
99  void explore_forward(const Cost_Vertex_pair &node) {
100  typename G::EO_i out, out_end;
101 
102  auto current_cost = node.first;
103  auto current_node = node.second;
104 
105  for (boost::tie(out, out_end) = out_edges(current_node, graph.graph);
106  out != out_end; ++out) {
107  auto edge_cost = graph[*out].cost;
108  auto next_node = graph.adjacent(current_node, *out);
109 
110  if (forward_finished[next_node]) continue;
111 
112  if (edge_cost + current_cost < forward_cost[next_node]) {
113  forward_cost[next_node] = edge_cost + current_cost;
114  forward_predecessor[next_node] = current_node;
115  forward_edge[next_node] = graph[*out].id;
116  forward_queue.push({forward_cost[next_node], next_node});
117  }
118  }
119  forward_finished[current_node] = true;
120  }
121 
122  void explore_backward(const Cost_Vertex_pair &node) {
123  typename G::EI_i in, in_end;
124 
125  auto current_cost = node.first;
126  auto current_node = node.second;
127 
128  for (boost::tie(in, in_end) = in_edges(current_node, graph.graph);
129  in != in_end; ++in) {
130  auto edge_cost = graph[*in].cost;
131  auto next_node = graph.adjacent(current_node, *in);
132 
133  if (backward_finished[next_node]) continue;
134 
135  if (edge_cost + current_cost < backward_cost[next_node]) {
136  backward_cost[next_node] = edge_cost + current_cost;
137  backward_predecessor[next_node] = current_node;
138  backward_edge[next_node] = graph[*in].id;
139  backward_queue.push({backward_cost[next_node], next_node});
140  }
141  }
142  backward_finished[current_node] = true;
143  }
144 };
145 
146 } // namespace bidirectional
147 } // namespace pgrouting
148 
149 #endif // INCLUDE_BDDIJKSTRA_PGR_BDDIJKSTRA_HPP_
Pgr_bidirectional< G >::Cost_Vertex_pair Cost_Vertex_pair
void explore_forward(const Cost_Vertex_pair &node)
void explore_backward(const Cost_Vertex_pair &node)
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
Path pgr_bdDijkstra(V start_vertex, V end_vertex, bool only_cost)