pgrouting::functions::Pgr_breadthFirstSearch< G > Class Template Reference

#include "pgr_breadthFirstSearch.hpp"

Public Types
typedef G::B_G	B_G
typedef G::E	E
typedef G::V	V

Public Member Functions
std::vector< pgr_mst_rt >	breadthFirstSearch (G &graph, std::vector< int64_t > start_vertex, int64_t depth)

Private Member Functions
template<typename T >
std::vector< pgr_mst_rt >	get_results (T order, int64_t source, int64_t max_depth, const G &graph)

Detailed Description

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

Definition at line 42 of file pgr_breadthFirstSearch.hpp.

Member Typedef Documentation

B_G

template<class G >

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

Definition at line 46 of file pgr_breadthFirstSearch.hpp.

E

template<class G >

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

Definition at line 45 of file pgr_breadthFirstSearch.hpp.

V

template<class G >

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

Definition at line 44 of file pgr_breadthFirstSearch.hpp.

Member Function Documentation

breadthFirstSearch()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_breadthFirstSearch< G >::breadthFirstSearch ( G &  graph, std::vector< int64_t >  start_vertex, int64_t  depth  )

inline

Definition at line 49 of file pgr_breadthFirstSearch.hpp.

                       {
        std::vector<pgr_mst_rt> results;
        using bfs_visitor = visitors::Edges_order_bfs_visitor<E>;
 
        for (auto source : start_vertex) {
            std::vector<E> visited_order;
 
            if (graph.has_vertex(source)) {
                results.push_back({source, 0, source, -1, 0.0, 0.0});
                boost::breadth_first_search(graph.graph,
                                            graph.get_V(source),
                                            visitor(bfs_visitor(visited_order)));
 
                auto single_source_results = get_results(visited_order, source, depth, graph);
                results.insert(results.end(), single_source_results.begin(), single_source_results.end());
 
                /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
                CHECK_FOR_INTERRUPTS();
            }
        }
        return results;
        }

References pgrouting::functions::Pgr_breadthFirstSearch< G >::get_results().

Referenced by pgr_breadthFirstSearch().

get_results()

template<class G >

template<typename T >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_breadthFirstSearch< G >::get_results ( T  order, int64_t  source, int64_t  max_depth, const G &  graph  )

inlineprivate

Definition at line 77 of file pgr_breadthFirstSearch.hpp.

                             {
         std::vector<pgr_mst_rt> results;
 
         std::vector<double> agg_cost(graph.num_vertices(), 0);
         std::vector<int64_t> depth(graph.num_vertices(), 0);
 
         for (const auto edge : order) {
             auto u = graph.source(edge);
             auto v = graph.target(edge);
 
             agg_cost[v] = agg_cost[u] + graph[edge].cost;
             depth[v] = depth[u] + 1;
 
             if (max_depth >= depth[v]) {
                 results.push_back({
                     source,
                         depth[v],
                         graph[v].id,
                         graph[edge].id,
                         graph[edge].cost,
                         agg_cost[v]
                 });
             }
         }
         return results;
     }

Referenced by pgrouting::functions::Pgr_breadthFirstSearch< G >::breadthFirstSearch().

---

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

• pgr_breadthFirstSearch.hpp