#include "pgr_binaryBreadthFirstSearch.hpp"

Public Types
typedef G::B_G	B_G

typedef G::E	E

typedef G::E_i	E_i

typedef G::EO_i	EO_i

typedef G::V	V

Public Member Functions
std::deque< Path >	binaryBreadthFirstSearch (G &graph, const std::vector< pgr_combination_t > &combinations)

std::deque< Path >	binaryBreadthFirstSearch (G &graph, std::vector< int64_t > start_vertex, std::vector< int64_t > end_vertex)

Private Member Functions
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)

std::deque< Path >	one_to_many_binaryBreadthFirstSearch (G &graph, int64_t start_vertex, std::vector< int64_t > end_vertex)

void	updateVertexCosts (G &graph, std::vector< double > &current_cost, std::vector< E > &from_edge, std::deque< V > &dq, V &head_vertex)

Private Attributes
E	DEFAULT_EDGE

Detailed Description

template<class G>
class pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >

Definition at line 44 of file pgr_binaryBreadthFirstSearch.hpp.

Member Typedef Documentation

◆ B_G

template<class G >

typedef G::B_G pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::B_G

Definition at line 48 of file pgr_binaryBreadthFirstSearch.hpp.

◆ E

template<class G >

typedef G::E pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::E

Definition at line 47 of file pgr_binaryBreadthFirstSearch.hpp.

◆ E_i

template<class G >

typedef G::E_i pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::E_i

Definition at line 50 of file pgr_binaryBreadthFirstSearch.hpp.

◆ EO_i

template<class G >

typedef G::EO_i pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::EO_i

Definition at line 49 of file pgr_binaryBreadthFirstSearch.hpp.

◆ V

template<class G >

typedef G::V pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::V

Definition at line 46 of file pgr_binaryBreadthFirstSearch.hpp.

Member Function Documentation

◆ binaryBreadthFirstSearch() [1/2]

template<class G >

std::deque<Path> pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::binaryBreadthFirstSearch	(	G &	graph,
		const std::vector< pgr_combination_t > &	combinations
	)

inline

Definition at line 82 of file pgr_binaryBreadthFirstSearch.hpp.

                                                           {
         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) {
             std::deque<Path> result_paths = one_to_many_binaryBreadthFirstSearch(
                 graph,
                 start_ends.first,
                 start_ends.second);
             paths.insert(
                 paths.begin(),
                 std::make_move_iterator(result_paths.begin()),
                 std::make_move_iterator(result_paths.end()));
         }
  
         std::sort(paths.begin(), paths.end(),
                   [](const Path &e1, const Path &e2) -> bool {
                       return e1.end_id() < e2.end_id();
                   });
         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::functions::Pgr_binaryBreadthFirstSearch< G >::one_to_many_binaryBreadthFirstSearch().

◆ binaryBreadthFirstSearch() [2/2]

template<class G >

std::deque<Path> pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::binaryBreadthFirstSearch	(	G &	graph,
		std::vector< int64_t >	start_vertex,
		std::vector< int64_t >	end_vertex
	)

inline

Definition at line 52 of file pgr_binaryBreadthFirstSearch.hpp.

                                        {
         std::deque<Path> paths;
  
         for (auto source : start_vertex) {
             std::deque<Path> result_paths = one_to_many_binaryBreadthFirstSearch(
                 graph,
                 source,
                 end_vertex);
             paths.insert(
                 paths.begin(),
                 std::make_move_iterator(result_paths.begin()),
                 std::make_move_iterator(result_paths.end()));
         }
  
         std::sort(paths.begin(), paths.end(),
                   [](const Path &e1, const Path &e2) -> bool {
                       return e1.end_id() < e2.end_id();
                   });
         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::functions::Pgr_binaryBreadthFirstSearch< G >::one_to_many_binaryBreadthFirstSearch().

Referenced by pgr_binaryBreadthFirstSearch().

◆ getPath()

template<class G >

Path pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::getPath	(	G &	graph,
		V	bgl_start_vertex,
		int64_t	target,
		V	bgl_target_vertex,
		std::vector< E > &	from_edge,
		std::vector< double > &	current_cost
	)

inlineprivate

Definition at line 171 of file pgr_binaryBreadthFirstSearch.hpp.

                                          {
         auto current_node = bgl_target_vertex;
  
         Path path = Path(graph[bgl_start_vertex].id, graph[current_node].id);
  
         path.push_back({target, -1, 0, current_cost[current_node]});
  
         do {
             E e = from_edge[current_node];
             auto from = graph.source(e);
  
             path.push_back({graph[from].id, graph[e].id, graph[e].cost, current_cost[from]});
  
             current_node = from;
         } while (from_edge[current_node] != DEFAULT_EDGE);
  
         std::reverse(path.begin(), path.end());
         return path;
     }

References Path::begin(), pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::DEFAULT_EDGE, Path::end(), and Path::push_back().

Referenced by pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::one_to_many_binaryBreadthFirstSearch().

◆ one_to_many_binaryBreadthFirstSearch()

template<class G >

std::deque<Path> pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::one_to_many_binaryBreadthFirstSearch	(	G &	graph,
		int64_t	start_vertex,
		std::vector< int64_t >	end_vertex
	)

inlineprivate

Definition at line 125 of file pgr_binaryBreadthFirstSearch.hpp.

                                            {
             std::deque<Path> paths;
  
             if (graph.has_vertex(start_vertex) == false) {
                 return paths;
             }
  
             std::vector<double> current_cost(graph.num_vertices(), std::numeric_limits<double>::infinity());
             std::vector<E> from_edge(graph.num_vertices());
             std::deque<V> dq;
             DEFAULT_EDGE = from_edge[0];
  
             auto bgl_start_vertex = graph.get_V(start_vertex);
  
             current_cost[bgl_start_vertex] = 0;
             dq.push_front(bgl_start_vertex);
  
             while (dq.empty() == false) {
                 auto head_vertex = dq.front();
  
                 dq.pop_front();
  
                 updateVertexCosts(graph, current_cost, from_edge, dq, head_vertex);
             }
  
             for (auto target_vertex : end_vertex) {
                 if (graph.has_vertex(target_vertex) == false) {
                     continue;
                 }
  
                 auto bgl_target_vertex = graph.get_V(target_vertex);
  
                 if (from_edge[bgl_target_vertex] == DEFAULT_EDGE) {
                     continue;
                 }
  
                 paths.push_front(
                     getPath(graph, bgl_start_vertex, target_vertex, bgl_target_vertex, from_edge, current_cost));
             }
  
             return paths;
     }

References pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::DEFAULT_EDGE, pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::getPath(), and pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::updateVertexCosts().

Referenced by pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::binaryBreadthFirstSearch().

◆ updateVertexCosts()

template<class G >

void pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::updateVertexCosts	(	G &	graph,
		std::vector< double > &	current_cost,
		std::vector< E > &	from_edge,
		std::deque< V > &	dq,
		V &	head_vertex
	)

inlineprivate

Definition at line 198 of file pgr_binaryBreadthFirstSearch.hpp.

                         {
         auto out_edges = boost::out_edges(head_vertex, graph.graph);
         E e;
         EO_i out_i;
         EO_i out_end;
         V v_source, v_target;
  
         for (boost::tie(out_i, out_end) = out_edges;
              out_i != out_end; ++out_i) {
             e = *out_i;
             v_target = graph.target(e);
             v_source = graph.source(e);
             double edge_cost = graph[e].cost;
  
             if (std::isinf(current_cost[v_target]) || current_cost[v_source] + edge_cost < current_cost[v_target]) {
                 current_cost[v_target] = current_cost[v_source] + edge_cost;
  
                 from_edge[v_target] = e;
  
                 if (edge_cost != 0) {
                     dq.push_back(v_target);
                 } else {
                     dq.push_front(v_target);
                 }
             }
         }
     }