31 #ifndef INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_ 32 #define INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_ 35 #include <boost/config.hpp> 36 #include <boost/graph/adjacency_list.hpp> 39 #if Boost_VERSION_MACRO >= 105500 40 #include <boost/graph/dijkstra_shortest_paths.hpp> 42 #include "boost/dijkstra_shortest_paths.hpp" 61 #include "./../../common/src/signalhandler.h" 74 std::vector< int64_t > start_vids,
77 std::ostringstream &log) {
95 bool only_cost =
false) {
97 return fn_dijkstra.
dijkstra(graph, source, target, only_cost);
116 int64_t start_vertex,
122 auto path =
Path(graph,
128 std::sort(path.begin(), path.end(),
130 {
return l.
node < r.node;});
131 std::stable_sort(path.begin(), path.end(),
138 Path p(start_vertex, start_vertex);
146 const std::vector< int64_t > &start_vertex,
149 std::ostringstream &the_log) {
155 the_log <<
log.str();
178 int64_t start_vertex,
180 bool only_cost =
false) {
186 graph.num_vertices(),
187 std::numeric_limits<double>::infinity());
190 if (!graph.has_vertex(start_vertex)
191 || !graph.has_vertex(end_vertex)) {
192 return Path(start_vertex, end_vertex);
196 auto v_source(graph.get_V(start_vertex));
197 auto v_target(graph.get_V(end_vertex));
218 int64_t start_vertex,
219 const std::vector< int64_t > &end_vertex,
221 size_t n_goals = (std::numeric_limits<size_t>::max)()) {
227 graph.num_vertices(),
228 std::numeric_limits<double>::infinity());
232 if (!graph.has_vertex(start_vertex))
233 return std::deque<Path>();
234 auto v_source(graph.get_V(start_vertex));
236 std::set< V > s_v_targets;
237 for (
const auto &vertex : end_vertex) {
238 if (graph.has_vertex(vertex)) {
239 s_v_targets.insert(graph.get_V(vertex));
243 std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
247 std::deque< Path > paths;
249 paths =
get_paths(graph, v_source, v_targets, only_cost);
251 std::stable_sort(paths.begin(), paths.end(),
252 [](
const Path &e1,
const Path &e2)->
bool {
253 return e1.
end_id() < e2.end_id();
262 const std::vector < int64_t > &start_vertex,
265 std::deque<Path> paths;
267 for (
const auto &start : start_vertex) {
269 dijkstra(graph, start, end_vertex, only_cost));
272 std::stable_sort(paths.begin(), paths.end(),
273 [](
const Path &e1,
const Path &e2)->
bool {
274 return e1.
start_id() < e2.start_id();
283 const std::vector< int64_t > &start_vertex,
284 const std::vector< int64_t > &end_vertex,
286 size_t n_goals = (std::numeric_limits<size_t>::max)()) {
288 std::deque<Path> paths;
290 for (
const auto &start : start_vertex) {
295 paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
298 std::sort(paths.begin(), paths.end(),
299 [](
const Path &e1,
const Path &e2)->
bool {
300 return e1.
end_id() < e2.end_id();
302 std::stable_sort(paths.begin(), paths.end(),
303 [](
const Path &e1,
const Path &e2)->
bool {
304 return e1.
start_id() < e2.start_id();
312 const std::vector< pgr_combination_t > &combinations,
314 size_t n_goals = (std::numeric_limits<size_t>::max)()) {
316 std::deque<Path> paths;
319 std::map<int64_t , std::vector<int64_t> > vertex_map;
321 std::map< int64_t , std::vector<int64_t> >::iterator it = vertex_map.find(comb.source);
322 if (it != vertex_map.end()) {
323 it->second.push_back(comb.target);
325 std::vector<int64_t > targets{comb.target};
326 vertex_map[comb.source] = targets;
330 for (
const auto &start_ends : vertex_map) {
333 start_ends.first, start_ends.second,
335 paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
338 std::sort(paths.begin(), paths.end(),
339 [](
const Path &e1,
const Path &e2)->
bool {
340 return e1.
end_id() < e2.end_id();
342 std::stable_sort(paths.begin(), paths.end(),
343 [](
const Path &e1,
const Path &e2)->
bool {
344 return e1.
start_id() < e2.start_id();
359 CHECK_FOR_INTERRUPTS();
361 boost::dijkstra_shortest_paths(graph.graph, source,
363 .weight_map(
get(&G::G_T_E::cost, graph.graph))
368 }
catch (boost::exception
const& ex) {
371 }
catch (std::exception &e) {
392 CHECK_FOR_INTERRUPTS();
394 boost::dijkstra_shortest_paths(graph.graph, source,
396 .weight_map(
get(&G::G_T_E::cost, graph.graph))
404 }
catch (boost::exception
const&) {
406 }
catch (std::exception&) {
426 std::vector<boost::default_color_type> color_map(graph.num_vertices());
428 CHECK_FOR_INTERRUPTS();
430 boost::dijkstra_shortest_paths_no_init(graph.graph, source,
431 make_iterator_property_map(
434 make_iterator_property_map(
437 get(&G::G_T_E::cost, graph.graph),
440 boost::closed_plus<double>(),
441 static_cast<double>(0),
449 boost::make_iterator_property_map(
455 }
catch (boost::exception
const& ex) {
458 }
catch (std::exception &e) {
494 int64_t start_vertex,
500 graph.num_vertices(),
501 std::numeric_limits<double>::infinity());
504 if (!graph.has_vertex(start_vertex)) {
510 graph.get_V(start_vertex),
568 const std::vector< int64_t > &start_vertex,
571 log <<
"Number of edges:" << boost::num_edges(graph.graph) <<
"\n";
575 graph.num_vertices(),
576 std::numeric_limits<double>::infinity());
585 std::deque< std::vector< V > >
pred(start_vertex.size());
589 for (
const auto &vertex : start_vertex) {
595 if (graph.has_vertex(vertex)) {
610 for (
const auto &vertex : start_vertex) {
611 for (
auto &p :
pred) {
612 if (!p.empty() && graph.has_vertex(vertex))
613 p[graph.get_V(vertex)] = graph.get_V(vertex);
634 const std::vector< int64_t > &start_vertex,
635 std::deque< std::vector< V > > &
pred,
646 std::deque<Path> paths;
647 for (
const auto vertex : start_vertex) {
648 paths.push_back(
Path(vertex, vertex));
649 paths.back().push_back({vertex, -1, 0, 0});
656 for (V d = 0; d <
distances.size(); ++d) {
660 if (!(
distances[d] <= distance))
continue;
662 for (
auto i = start_vertex.size(); i > 0; --i) {
666 if (
pred[i - 1].empty())
break;
673 if (
pred[i - 1][d] == d)
continue;
676 auto edge_id = graph.get_edge_id(pred[i - 1][d], d, cost);
678 paths[i - 1].push_back(
686 for (
auto &path : paths) {
687 path.sort_by_node_agg_cost();
696 const std::vector< int64_t > &start_vertex,
699 std::deque<Path> paths;
700 for (
const auto &vertex : start_vertex) {
708 path.sort_by_node_agg_cost();
709 paths.push_back(path);
711 Path p(vertex, vertex);
724 const std::vector< V > &targets,
725 size_t n_goals = (std::numeric_limits<size_t>::max)()) {
727 CHECK_FOR_INTERRUPTS();
729 boost::dijkstra_shortest_paths(graph.graph, source,
731 .weight_map(
get(&G::G_T_E::cost, graph.graph))
733 .distance_inf(std::numeric_limits<double>::infinity())
737 }
catch (boost::exception
const& ex) {
740 }
catch (std::exception &e) {
763 std::vector< V > &targets,
764 bool only_cost)
const {
765 std::deque<Path> paths;
766 for (
const auto target : targets) {
767 paths.push_back(
Path(
796 const std::vector< V > &goals,
798 m_goals(goals.begin(), goals.end()),
799 m_n_goals(n_goals) {}
802 auto s_it = m_goals.find(u);
803 if (s_it == m_goals.end())
return;
826 double distance_goal,
827 std::deque< V > &nodesInDistance,
828 std::vector< double > &distances) :
829 m_distance_goal(distance_goal),
830 m_nodes(nodesInDistance),
837 if (m_dist[u] > m_distance_goal) {
840 m_nodes.push_back(u);
851 :
public boost::default_dijkstra_visitor {
854 std::ostringstream &p_log,
856 double distance_goal,
857 std::vector< V > &predecessors,
858 std::vector< double > &distances,
859 std::vector<boost::default_color_type> &color_map) :
862 m_distance_goal(distance_goal),
864 m_predecessors(predecessors),
873 if ( 0 == m_num_examined++) first = u;
874 if (m_dist[u] > m_distance_goal) {
877 if (u != first && m_predecessors[u] == u) {
878 m_color[u] = boost::black_color;
884 if (source(e, g) != first
885 && m_predecessors[source(e, g)] == source(e, g)) {
886 m_color[target(e, g)] = boost::black_color;
899 if (source(e, g) != first
900 && m_predecessors[source(e, g)] == source(e, g)) {
901 m_color[target(e, g)] = boost::black_color;
913 if (u != first && m_predecessors[u] == u) {
914 m_color[u] = boost::black_color;
925 std::vector<boost::default_color_type> &
m_color;
932 #endif // INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_ std::deque< Path > drivingDistance_no_equicost(G &graph, const std::vector< int64_t > &start_vertex, double distance)
std::deque< Path > drivingDistance(G &graph, const std::vector< int64_t > &start_vertex, double distance, bool equicost, std::ostringstream &the_log)
bool execute_drivingDistance_no_init(G &graph, V start_vertex, double distance)
to use with driving distance
bool dijkstra_1_to_distance(G &graph, V source, double distance)
Call to Dijkstra 1 to distance.
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Path drivingDistance(G &graph, int64_t start_vertex, double distance)
1 to distance
dijkstra_distance_visitor_no_init(std::ostringstream &p_log, V source, double distance_goal, std::vector< V > &predecessors, std::vector< double > &distances, std::vector< boost::default_color_type > &color_map)
bool dijkstra_1_to_many(G &graph, V source, const std::vector< V > &targets, size_t n_goals=(std::numeric_limits< size_t >::max)())
Dijkstra 1 source to many targets.
std::vector< V > predecessors
void finish_vertex(V, B_G &)
void examine_vertex(V u, B_G &)
dijkstra_distance_visitor(double distance_goal, std::deque< V > &nodesInDistance, std::vector< double > &distances)
std::deque< Path > get_drivingDistance_with_equicost_paths(G &graph, const std::vector< int64_t > &start_vertex, std::deque< std::vector< V > > &pred, double distance)
gets results in form of a container of paths
boost::graph_traits< BG >::vertex_descriptor V
boost::graph_traits< BG >::edge_descriptor E
std::vector< boost::default_color_type > & m_color
static size_t pred(size_t i, size_t n)
void push_back(Path_t data)
std::vector< V > & m_predecessors
std::deque< Path > dijkstra(G &graph, int64_t start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost, size_t n_goals=(std::numeric_limits< size_t >::max)())
Dijkstra 1 to many.
Path pgr_dijkstra(G &graph, int64_t source, int64_t target, bool only_cost=false)
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
class for stopping when a distance/cost has being surpassed
std::deque< Path > dijkstra(G &graph, const std::vector< int64_t > &start_vertex, int64_t end_vertex, bool only_cost)
#define pgassert(expr)
Uses the standard assert syntax.
std::deque< Path > get_paths(const G &graph, V source, std::vector< V > &targets, bool only_cost) const
void edge_not_relaxed(E e, B_G &g)
class for stopping when a distance/cost has being surpassed
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
std::deque< Path > pgr_drivingDistance(G &graph, std::vector< int64_t > start_vids, double distance, bool equicost, std::ostringstream &log)
std::deque< Path > dijkstra(G &graph, const std::vector< pgr_combination_t > &combinations, bool only_cost, size_t n_goals=(std::numeric_limits< size_t >::max)())
void discover_vertex(V u, B_G &)
std::vector< double > & m_dist
void examine_vertex(V u, B_G &)
Book keeping class for swapping orders between vehicles.
void examine_vertex(V u, B_G &)
bool dijkstra_1_to_1(G &graph, V source, V target)
Call to Dijkstra 1 source to 1 target.
std::deque< Path > drivingDistance_with_equicost(G &graph, const std::vector< int64_t > &start_vertex, double distance)
void examine_edge(E e, B_G &g)
std::deque< V > nodesInDistance
std::vector< double > distances
class for stopping when all targets are found
std::deque< Path > dijkstra(G &graph, const std::vector< int64_t > &start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost, size_t n_goals=(std::numeric_limits< size_t >::max)())
dijkstra_many_goal_visitor(const std::vector< V > &goals, size_t n_goals)
bool execute_drivingDistance(G &graph, int64_t start_vertex, double distance)
to use with driving distance
bool dijkstra_1_to_distance_no_init(G &graph, V source, double distance)
Call to Dijkstra 1 to distance no init.
std::vector< double > & m_dist
std::deque< V > & m_nodes
exception for visitor termination
void edge_relaxed(E, B_G &)