#include "pgr_dijkstra.hpp"

Collaboration diagram for pgrouting::Pgr_dijkstra< G >:

[legend]

Classes
class	dijkstra_distance_visitor
	class for stopping when a distance/cost has being surpassed More...

class	dijkstra_distance_visitor_no_init
	class for stopping when a distance/cost has being surpassed More...

class	dijkstra_many_goal_visitor
	class for stopping when all targets are found More...

Public Types
typedef G::E	E

typedef G::V	V

Public Member Functions
drivingDistance
Path	drivingDistance (G &graph, int64_t start_vertex, double distance)
	1 to distance More...

std::deque< Path >	drivingDistance (G &graph, const std::vector< int64_t > &start_vertex, double distance, bool equicost, std::ostringstream &the_log)

Private Attributes
members
std::vector< V >	predecessors

std::vector< double >	distances

std::deque< V >	nodesInDistance

std::ostringstream	log

Dijkstra
Path	dijkstra (G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
	Dijkstra 1 to 1. More...

std::deque< Path >	dijkstra (G &graph, int64_t start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost, size_t n_goals)
	Dijkstra 1 to many. More...

std::deque< Path >	dijkstra (G &graph, const std::vector< int64_t > &start_vertex, int64_t end_vertex, bool only_cost)

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)())

std::deque< Path >	dijkstra (G &graph, const std::vector< pgr_combination_t > &combinations, bool only_cost, size_t n_goals)

bool	dijkstra_1_to_1 (G &graph, V source, V target)
	Call to Dijkstra 1 source to 1 target. More...

bool	dijkstra_1_to_distance (G &graph, V source, double distance)
	Call to Dijkstra 1 to distance. More...

bool	dijkstra_1_to_distance_no_init (G &graph, V source, double distance)
	Call to Dijkstra 1 to distance no init. More...

bool	execute_drivingDistance (G &graph, int64_t start_vertex, double distance)
	to use with driving distance More...

bool	execute_drivingDistance_no_init (G &graph, V start_vertex, double distance)
	to use with driving distance More...

std::deque< Path >	drivingDistance_with_equicost (G &graph, const std::vector< int64_t > &start_vertex, double distance)

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 More...

std::deque< Path >	drivingDistance_no_equicost (G &graph, const std::vector< int64_t > &start_vertex, double distance)

bool	dijkstra_1_to_many (G &graph, V source, const std::vector< V > &targets, size_t n_goals)
	Dijkstra 1 source to many targets. More...

void	clear ()

std::deque< Path >	get_paths (const G &graph, V source, std::vector< V > &targets, bool only_cost) const

Detailed Description

template<class G>
class pgrouting::Pgr_dijkstra< G >

Definition at line 62 of file pgr_dijkstra.hpp.

Member Typedef Documentation

◆ E

template<class G >

typedef G::E pgrouting::Pgr_dijkstra< G >::E

Definition at line 105 of file pgr_dijkstra.hpp.

◆ V

template<class G >

typedef G::V pgrouting::Pgr_dijkstra< G >::V

Definition at line 104 of file pgr_dijkstra.hpp.

Member Function Documentation

◆ clear()

template<class G >

void pgrouting::Pgr_dijkstra< G >::clear ( )

inlineprivate

Definition at line 710 of file pgr_dijkstra.hpp.

                   {
          predecessors.clear();
          distances.clear();
          nodesInDistance.clear();
      }

References pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::nodesInDistance, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra(), pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost(), and pgrouting::Pgr_dijkstra< G >::execute_drivingDistance().

◆ dijkstra() [1/5]

template<class G >

std::deque<Path> pgrouting::Pgr_dijkstra< G >::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)()`
	)

inline

Definition at line 270 of file pgr_dijkstra.hpp.

                                                                 {
          // a call to 1 to many is faster for each of the sources
          std::deque<Path> paths;
  
          for (const auto &start : start_vertex) {
              auto r_paths = dijkstra(
                      graph,
                      start, end_vertex,
                      only_cost, n_goals);
              paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
          }
  
          return paths;
      }

References pgrouting::Pgr_dijkstra< G >::dijkstra().

◆ dijkstra() [2/5]

template<class G >

std::deque<Path> pgrouting::Pgr_dijkstra< G >::dijkstra	(	G &	graph,
		const std::vector< int64_t > &	start_vertex,
		int64_t	end_vertex,
		bool	only_cost
	)

inline

Definition at line 249 of file pgr_dijkstra.hpp.

                              {
          std::deque<Path> paths;
  
          for (const auto &start : start_vertex) {
              paths.push_back(
                      dijkstra(graph, start, end_vertex, only_cost));
          }
  
          std::stable_sort(paths.begin(), paths.end(),
                  [](const Path &e1, const Path &e2)->bool {
                  return e1.start_id() < e2.start_id();
                  });
          return paths;
      }

References pgrouting::Pgr_dijkstra< G >::dijkstra().

◆ dijkstra() [3/5]

template<class G >

std::deque<Path> pgrouting::Pgr_dijkstra< G >::dijkstra	(	G &	graph,
		const std::vector< pgr_combination_t > &	combinations,
		bool	only_cost,
		size_t	n_goals
	)

inline

Definition at line 291 of file pgr_dijkstra.hpp.

                             {
         // a call to 1 to many is faster for each of the sources
         std::deque<Path> paths;
  
         // group targets per distinct source
         std::map<int64_t , std::vector<int64_t> > vertex_map;
         for (const pgr_combination_t &comb : combinations) {
             std::map< int64_t , std::vector<int64_t> >::iterator it = vertex_map.find(comb.source);
             if (it != vertex_map.end()) {
                 it->second.push_back(comb.target);
             } else {
                 std::vector<int64_t > targets{comb.target};
                 vertex_map[comb.source] = targets;
             }
         }
  
         for (const auto &start_ends : vertex_map) {
             auto r_paths = dijkstra(
                     graph,
                     start_ends.first, start_ends.second,
                     only_cost, n_goals);
             paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
         }
  
         return paths;
     }

References pgrouting::Pgr_dijkstra< G >::dijkstra().

◆ dijkstra() [4/5]

template<class G >

std::deque<Path> pgrouting::Pgr_dijkstra< G >::dijkstra	(	G &	graph,
		int64_t	start_vertex,
		const std::vector< int64_t > &	end_vertex,
		bool	only_cost,
		size_t	n_goals
	)

inline

Dijkstra 1 to many.

Definition at line 212 of file pgr_dijkstra.hpp.

                              {
          // adjust predecessors and distances vectors
          clear();
  
          predecessors.resize(graph.num_vertices());
          distances.resize(
                  graph.num_vertices(),
                  std::numeric_limits<double>::infinity());
  
  
          // get the graphs source and target
          if (!graph.has_vertex(start_vertex)) return std::deque<Path>();
  
          auto v_source(graph.get_V(start_vertex));
  
          std::set< V > s_v_targets;
          for (const auto &vertex : end_vertex) {
              if (graph.has_vertex(vertex)) s_v_targets.insert(graph.get_V(vertex));
          }
  
          std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
          // perform the algorithm
          dijkstra_1_to_many(graph, v_source, v_targets, n_goals);
  
          std::deque< Path > paths;
          // get the results // route id are the targets
          paths = get_paths(graph, v_source, v_targets, only_cost);
  
          return paths;
      }

References pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_many(), pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::get_paths(), and pgrouting::Pgr_dijkstra< G >::predecessors.

◆ dijkstra() [5/5]

template<class G >

Path pgrouting::Pgr_dijkstra< G >::dijkstra	(	G &	graph,
		int64_t	start_vertex,
		int64_t	end_vertex,
		bool	only_cost = `false`
	)

inline

Dijkstra 1 to 1.

Definition at line 172 of file pgr_dijkstra.hpp.

                                      {
          clear();
  
          // adjust predecessors and distances vectors
          predecessors.resize(graph.num_vertices());
          distances.resize(
                  graph.num_vertices(),
                  std::numeric_limits<double>::infinity());
  
  
          if (!graph.has_vertex(start_vertex)
                  || !graph.has_vertex(end_vertex)) {
              return Path(start_vertex, end_vertex);
          }
  
          // get the graphs source and target
          auto v_source(graph.get_V(start_vertex));
          auto v_target(graph.get_V(end_vertex));
  
          // perform the algorithm
          dijkstra_1_to_1(graph, v_source, v_target);
  
          // get the results
          return Path(
                  graph,
                  v_source, v_target,
                  predecessors, distances,
                  only_cost, true);
      }

References pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_1(), pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra(), pgrouting::yen::Pgr_ksp< G >::doNextCycle(), pgrouting::yen::Pgr_ksp< G >::getFirstSolution(), pgr_dijkstra(), pgrouting::pgr_dijkstra(), and detail::pgr_dijkstra().

◆ dijkstra_1_to_1()

template<class G >

bool pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_1	(	G &	graph,
		V	source,
		V	target
	)

inlineprivate

Call to Dijkstra 1 source to 1 target.

Definition at line 326 of file pgr_dijkstra.hpp.

                            {
          /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
          CHECK_FOR_INTERRUPTS();
          try {
              boost::dijkstra_shortest_paths(graph.graph, source,
                      boost::predecessor_map(&predecessors[0])
                      .weight_map(get(&G::G_T_E::cost, graph.graph))
                      .distance_map(&distances[0])
                      .visitor(visitors::dijkstra_one_goal_visitor<V>(target)));
          } catch(found_goals &) {
              return true;
          } catch (boost::exception const& ex) {
              (void)ex;
              throw;
          } catch (std::exception &e) {
              (void)e;
              throw;
          } catch (...) {
              throw;
          }
          return true;
      }

References pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra().

◆ dijkstra_1_to_distance()

template<class G >

bool pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance	(	G &	graph,
		V	source,
		double	distance
	)

inlineprivate

Call to Dijkstra 1 to distance.

Used on: 1 to distance many to distance On the first call of many to distance with equi_cost

Definition at line 359 of file pgr_dijkstra.hpp.

                               {
          /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
          CHECK_FOR_INTERRUPTS();
          try {
              boost::dijkstra_shortest_paths(graph.graph, source,
                      boost::predecessor_map(&predecessors[0])
                      .weight_map(get(&G::G_T_E::cost, graph.graph))
                      .distance_map(&distances[0])
                      .visitor(dijkstra_distance_visitor(
                              distance,
                              nodesInDistance,
                              distances)));
          } catch(found_goals &) {
              /*No op*/
          } catch (boost::exception const&) {
              throw;
          } catch (std::exception&) {
              throw;
          } catch (...) {
              throw;
          }
          return true;
      }

References pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::nodesInDistance, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::execute_drivingDistance().

◆ dijkstra_1_to_distance_no_init()

template<class G >

bool pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance_no_init	(	G &	graph,
		V	source,
		double	distance
	)

inlineprivate

Call to Dijkstra 1 to distance no init.

Used on: On the subsequent calls of many to distance with equi_cost

Definition at line 391 of file pgr_dijkstra.hpp.

                               {
          pgassert(predecessors.size() == graph.num_vertices());
          pgassert(distances.size() == graph.num_vertices());
          distances[source] = 0;
          std::vector<boost::default_color_type> color_map(graph.num_vertices());
          /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
          CHECK_FOR_INTERRUPTS();
          try {
              boost::dijkstra_shortest_paths_no_init(graph.graph, source,
                      make_iterator_property_map(
                          predecessors.begin(),
                          graph.vertIndex),
                      make_iterator_property_map(
                          distances.begin(),
                          graph.vertIndex),
                      get(&G::G_T_E::cost, graph.graph),
                      graph.vertIndex,
                      std::less<double>(),
                      boost::closed_plus<double>(),
                      static_cast<double>(0),
                      dijkstra_distance_visitor_no_init(
                          log,
                          source,
                          distance,
                          predecessors,
                          distances,
                          color_map),
                      boost::make_iterator_property_map(
                          color_map.begin(),
                          graph.vertIndex,
                          color_map[0]));
          } catch(found_goals &) {
              return true;
          } catch (boost::exception const& ex) {
              (void)ex;
              throw;
          } catch (std::exception &e) {
              (void)e;
              throw;
          } catch (...) {
              throw;
          }
  
          return true;
      }

References pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::log, pgassert, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::execute_drivingDistance_no_init().

◆ dijkstra_1_to_many()

template<class G >

bool pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_many	(	G &	graph,
		V	source,
		const std::vector< V > &	targets,
		size_t	n_goals
	)

inlineprivate

Dijkstra 1 source to many targets.

Definition at line 673 of file pgr_dijkstra.hpp.

                              {
          /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
          CHECK_FOR_INTERRUPTS();
          std::set<V> goals_found;
          std::set<V> goals(targets.begin(), targets.end());
          try {
              boost::dijkstra_shortest_paths(graph.graph, source,
                      boost::predecessor_map(&predecessors[0])
                      .weight_map(get(&G::G_T_E::cost, graph.graph))
                      .distance_map(&distances[0])
                      .distance_inf(std::numeric_limits<double>::infinity())
                      .visitor(dijkstra_many_goal_visitor(goals, n_goals, goals_found)));
          } catch(found_goals &) {
              for (const auto &g : goals) {
                  if (goals_found.find(g) == goals_found.end()) {
                      /* goal was not found */
                      predecessors[g] = g;
                  }
              }
              return true;
          } catch (boost::exception const& ex) {
              (void)ex;
              throw;
          } catch (std::exception &e) {
              (void)e;
              throw;
          } catch (...) {
              throw;
          }
          return true;
      }

References pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra().

◆ drivingDistance() [1/2]

template<class G >

std::deque< Path > pgrouting::Pgr_dijkstra< G >::drivingDistance	(	G &	graph,
		const std::vector< int64_t > &	start_vertex,
		double	distance,
		bool	equicost,
		std::ostringstream &	the_log
	)

inline

Definition at line 140 of file pgr_dijkstra.hpp.

                                         {
          if (equicost) {
              auto paths = drivingDistance_with_equicost(
                      graph,
                      start_vertex,
                      distance);
              the_log << log.str();
              return paths;
          } else {
              return drivingDistance_no_equicost(
                      graph,
                      start_vertex,
                      distance);
          }
      }

References pgrouting::Pgr_dijkstra< G >::drivingDistance_no_equicost(), pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost(), and pgrouting::Pgr_dijkstra< G >::log.

◆ drivingDistance() [2/2]

template<class G >

Path pgrouting::Pgr_dijkstra< G >::drivingDistance	(	G &	graph,
		int64_t	start_vertex,
		double	distance
	)

inline

1 to distance

Definition at line 110 of file pgr_dijkstra.hpp.

                               {
         if (execute_drivingDistance(
                 graph,
                 start_vertex,
                 distance)) {
             auto path = Path(graph,
                     start_vertex,
                     distance,
                     predecessors,
                     distances);
  
             std::sort(path.begin(), path.end(),
                     [](const Path_t &l, const  Path_t &r)
                     {return l.node < r.node;});
             std::stable_sort(path.begin(), path.end(),
                     [](const Path_t &l, const  Path_t &r)
                     {return l.agg_cost < r.agg_cost;});
             return path;
         }
  
         /* The result is empty */
         Path p(start_vertex, start_vertex);
         p.push_back({start_vertex, -1, 0, 0});
         return p;
      }

Referenced by pgrouting::pgr_drivingDistance().

◆ drivingDistance_no_equicost()

template<class G >

std::deque< Path > pgrouting::Pgr_dijkstra< G >::drivingDistance_no_equicost	(	G &	graph,
		const std::vector< int64_t > &	start_vertex,
		double	distance
	)

inlineprivate

Definition at line 646 of file pgr_dijkstra.hpp.

                               {
          // perform the algorithm
          std::deque<Path> paths;
          for (const auto &vertex : start_vertex) {
              if (execute_drivingDistance(graph, vertex, distance)) {
                  auto path = Path(
                          graph,
                          vertex,
                          distance,
                          predecessors,
                          distances);
                  path.sort_by_node_agg_cost();
                  paths.push_back(path);
              } else {
                  Path p(vertex, vertex);
                  p.push_back({vertex, -1, 0, 0});
                  paths.push_back(p);
              }
          }
          return paths;
      }

References pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::execute_drivingDistance(), pgrouting::Pgr_dijkstra< G >::predecessors, and Path::push_back().

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance().

◆ drivingDistance_with_equicost()

template<class G >

std::deque< Path > pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost	(	G &	graph,
		const std::vector< int64_t > &	start_vertex,
		double	distance
	)

inlineprivate

Definition at line 518 of file pgr_dijkstra.hpp.

                               {
          clear();
          log << "Number of edges:" << boost::num_edges(graph.graph) << "\n";
  
          predecessors.resize(graph.num_vertices());
          distances.resize(
                  graph.num_vertices(),
                  std::numeric_limits<double>::infinity());
  
          /*
           * Vector to store the different predessesors
           * each is of size = graph.num_vertices()
           *
           * TODO(vicky)
           * - figure out less storage if possible
           */
          std::deque< std::vector< V > > pred(start_vertex.size());
  
          // perform the algorithm
          size_t i = 0;
          for (const auto &vertex : start_vertex) {
              nodesInDistance.clear();
              /*
               * The vertex does not exist
               *   Nothing to do
               */
              if (graph.has_vertex(vertex)) {
                  if (execute_drivingDistance_no_init(
                              graph,
                              graph.get_V(vertex),
                              distance)) {
                      pred[i] = predecessors;
                  }
              }
              ++i;
          }
  
  
          /*
           * predecessors of vertices in the set are themselves
           */
          for (const auto &vertex : start_vertex) {
              for (auto &p : pred) {
                  if (!p.empty() && graph.has_vertex(vertex))
                      p[graph.get_V(vertex)] = graph.get_V(vertex);
              }
          }
  
  
         return get_drivingDistance_with_equicost_paths(
                 graph,
                 start_vertex,
                 pred,
                 distance);
      }

References pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::execute_drivingDistance_no_init(), pgrouting::Pgr_dijkstra< G >::get_drivingDistance_with_equicost_paths(), pgrouting::Pgr_dijkstra< G >::log, pgrouting::Pgr_dijkstra< G >::nodesInDistance, pred(), and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance().

◆ execute_drivingDistance()

template<class G >

bool pgrouting::Pgr_dijkstra< G >::execute_drivingDistance	(	G &	graph,
		int64_t	start_vertex,
		double	distance
	)

inlineprivate

to use with driving distance

Prepares the execution for a driving distance:

Parameters

graph
start_vertex
distance	Results are kept on predecessor & distances

Returns: bool True when results are found

Definition at line 453 of file pgr_dijkstra.hpp.

                               {
          clear();
  
          predecessors.resize(graph.num_vertices());
          distances.resize(
                  graph.num_vertices(),
                  std::numeric_limits<double>::infinity());
  
          // get source;
          if (!graph.has_vertex(start_vertex)) {
              return false;
          }
  
          return dijkstra_1_to_distance(
                  graph,
                  graph.get_V(start_vertex),
                  distance);
      }

References pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance(), pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance_no_equicost().

◆ execute_drivingDistance_no_init()

template<class G >

bool pgrouting::Pgr_dijkstra< G >::execute_drivingDistance_no_init	(	G &	graph,
		V	start_vertex,
		double	distance
	)

inlineprivate

to use with driving distance

Prepares the execution for a driving distance:

Parameters

graph
start_vertex
distance	Results are kept on predecessor & distances

Returns: bool True when results are found

Definition at line 488 of file pgr_dijkstra.hpp.

                               {
          pgassert(predecessors.size() == graph.num_vertices());
          pgassert(distances.size() == graph.num_vertices());
  
          std::iota(predecessors.begin(), predecessors.end(), 0);
  
          return dijkstra_1_to_distance_no_init(
                  graph,
                  start_vertex,
                  distance);
      }

References pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance_no_init(), pgrouting::Pgr_dijkstra< G >::distances, pgassert, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost().

◆ get_drivingDistance_with_equicost_paths()

template<class G >

std::deque< Path > pgrouting::Pgr_dijkstra< G >::get_drivingDistance_with_equicost_paths	(	G &	graph,
		const std::vector< int64_t > &	start_vertex,
		std::deque< std::vector< V > > &	pred,
		double	distance
	)

inlineprivate

gets results in form of a container of paths

Parameters

[in]	graph	The graph that is being worked
[in]	start_vertex	An array of vertices id
[in]	pred	an array of predecessors
[in]	distance	the max distance

Definition at line 584 of file pgr_dijkstra.hpp.

                               {
          /*
           * precondition
           */
          pgassert(start_vertex.size() == pred.size());
  
  
          /*
           * Creating all the result "paths"
           */
          std::deque<Path> paths;
          for (const auto vertex : start_vertex) {
              paths.push_back(Path(vertex, vertex));
              paths.back().push_back({vertex, -1, 0, 0});
          }
  
          /*
           *  Ciclying the distances:
           *  To which vertex do they belong to?
           */
          for (V d = 0; d < distances.size(); ++d) {
              /*
               * Sikiping distances greater than the one asked for
               */
              if (!(distances[d] <= distance)) continue;
  
              for (auto i = start_vertex.size(); i > 0; --i) {
                  /*
                   * The vertex does not exist on the graph
                   */
                  if (pred[i - 1].empty()) break;
  
  
                  /*
                   * The predecessor = current then
                   *  its unreachable to this vertex
                   */
                  if (pred[i - 1][d] == d) continue;
  
                  auto cost = distances[d] - distances[pred[i - 1][d]];
                  auto edge_id = graph.get_edge_id(pred[i - 1][d], d, cost);
                  pgassert(edge_id != -1);
                  paths[i - 1].push_back(
                          {graph[d].id,
                          edge_id, cost,
                          distances[d]});
                  break;
              }
          }
  
          for (auto &path : paths) {
              path.sort_by_node_agg_cost();
          }
          return paths;
      }

References pgrouting::Pgr_dijkstra< G >::distances, pgassert, and pred().

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost().

◆ get_paths()

template<class G >

std::deque<Path> pgrouting::Pgr_dijkstra< G >::get_paths	(	const G &	graph,
		V	source,
		std::vector< V > &	targets,
		bool	only_cost
	)		const

inlineprivate

Definition at line 720 of file pgr_dijkstra.hpp.

                                    {
          std::deque<Path> paths;
          for (const auto target : targets) {
              paths.push_back(Path(
                          graph,
                          source, target,
                          predecessors, distances,
                          only_cost, true));
          }
          return paths;
      }

References pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra().

Member Data Documentation

◆ distances

template<class G >

std::vector< double > pgrouting::Pgr_dijkstra< G >::distances

private

Definition at line 741 of file pgr_dijkstra.hpp.

◆ log

template<class G >

std::ostringstream pgrouting::Pgr_dijkstra< G >::log

private

Definition at line 743 of file pgr_dijkstra.hpp.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance_no_init(), pgrouting::Pgr_dijkstra< G >::drivingDistance(), and pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost().

◆ nodesInDistance

template<class G >

std::deque< V > pgrouting::Pgr_dijkstra< G >::nodesInDistance

private

Definition at line 742 of file pgr_dijkstra.hpp.

Referenced by pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance(), and pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost().

◆ predecessors

template<class G >

std::vector< V > pgrouting::Pgr_dijkstra< G >::predecessors

private

Definition at line 740 of file pgr_dijkstra.hpp.

The documentation for this class was generated from the following file:

pgr_dijkstra.hpp

Classes

Public Types

Public Member Functions

Private Attributes

Dijkstra

Detailed Description

template<class G> class pgrouting::Pgr_dijkstra< G >

Member Typedef Documentation

◆ E

◆ V

Member Function Documentation

◆ clear()

◆ dijkstra() [1/5]

◆ dijkstra() [2/5]

◆ dijkstra() [3/5]

◆ dijkstra() [4/5]

◆ dijkstra() [5/5]

◆ dijkstra_1_to_1()

◆ dijkstra_1_to_distance()

◆ dijkstra_1_to_distance_no_init()

◆ dijkstra_1_to_many()

◆ drivingDistance() [1/2]

◆ drivingDistance() [2/2]

◆ drivingDistance_no_equicost()

◆ drivingDistance_with_equicost()

◆ execute_drivingDistance()

◆ execute_drivingDistance_no_init()

◆ get_drivingDistance_with_equicost_paths()

◆ get_paths()

Member Data Documentation

◆ distances

◆ log

◆ nodesInDistance

◆ predecessors

template<class G>
class pgrouting::Pgr_dijkstra< G >