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

#include "pgr_edwardMoore.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 >	edwardMoore (G &graph, const std::vector< pgr_combination_t > &combinations)
std::deque< Path >	edwardMoore (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_edwardMoore (G &graph, int64_t start_vertex, std::vector< int64_t > end_vertex)
void	updateVertexCosts (G &graph, std::vector< double > &current_cost, std::vector< bool > &isInQ, 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_edwardMoore< G >

Definition at line 41 of file pgr_edwardMoore.hpp.

Member Typedef Documentation

B_G

template<class G >

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

Definition at line 45 of file pgr_edwardMoore.hpp.

E

template<class G >

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

Definition at line 44 of file pgr_edwardMoore.hpp.

E_i

template<class G >

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

Definition at line 47 of file pgr_edwardMoore.hpp.

EO_i

template<class G >

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

Definition at line 46 of file pgr_edwardMoore.hpp.

V

template<class G >

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

Definition at line 43 of file pgr_edwardMoore.hpp.

Member Function Documentation

edwardMoore() [1/2]

template<class G >

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

inline

Definition at line 80 of file pgr_edwardMoore.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_edwardMoore(
                graph,
                start_ends.first,
                start_ends.second);
 
            paths.insert(
                paths.end(),
                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_edwardMoore< G >::one_to_many_edwardMoore().

edwardMoore() [2/2]

template<class G >

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

inline

Definition at line 49 of file pgr_edwardMoore.hpp.

                                       {
        std::deque<Path> paths;
 
        for (auto source : start_vertex) {
            std::deque<Path> result_paths = one_to_many_edwardMoore(
                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_edwardMoore< G >::one_to_many_edwardMoore().

Referenced by pgr_edwardMoore().

getPath()

template<class G >

Path pgrouting::functions::Pgr_edwardMoore< 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 173 of file pgr_edwardMoore.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_edwardMoore< G >::DEFAULT_EDGE, Path::end(), and Path::push_back().

Referenced by pgrouting::functions::Pgr_edwardMoore< G >::one_to_many_edwardMoore().

one_to_many_edwardMoore()

template<class G >

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

inlineprivate

Definition at line 124 of file pgr_edwardMoore.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<bool> isInQ(graph.num_vertices(), false);
        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;
        isInQ[bgl_start_vertex] = true;
        dq.push_front(bgl_start_vertex);
 
        while (dq.empty() == false) {
            auto head_vertex = dq.front();
 
            dq.pop_front();
            isInQ[head_vertex] = false;
 
            updateVertexCosts(graph, current_cost, isInQ, 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_edwardMoore< G >::DEFAULT_EDGE, pgrouting::functions::Pgr_edwardMoore< G >::getPath(), and pgrouting::functions::Pgr_edwardMoore< G >::updateVertexCosts().

Referenced by pgrouting::functions::Pgr_edwardMoore< G >::edwardMoore().

updateVertexCosts()

template<class G >

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

inlineprivate

Definition at line 199 of file pgr_edwardMoore.hpp.

                        {
        /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
        CHECK_FOR_INTERRUPTS();
 
        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 (isInQ[v_target] == false) {
                    dq.push_back(v_target);
                    isInQ[v_target] = true;
                }
            }
        }
    }

Referenced by pgrouting::functions::Pgr_edwardMoore< G >::one_to_many_edwardMoore().

Member Data Documentation

DEFAULT_EDGE

template<class G >

E pgrouting::functions::Pgr_edwardMoore< G >::DEFAULT_EDGE

private

Definition at line 122 of file pgr_edwardMoore.hpp.

Referenced by pgrouting::functions::Pgr_edwardMoore< G >::getPath(), and pgrouting::functions::Pgr_edwardMoore< G >::one_to_many_edwardMoore().

---

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

• pgr_edwardMoore.hpp