pgrouting::contraction::Pgr_deadend< G > Class Template Reference

#include "pgr_deadEndContraction.hpp"

Collaboration diagram for pgrouting::contraction::Pgr_deadend< G >:

Public Member Functions
	Pgr_deadend ()=default
void	calculateVertices (G &graph)
void	doContraction (G &graph)
bool	is_dead_end (G &graph, V v)
void	setForbiddenVertices (Identifiers< V > forbidden_vertices)

Private Types
using	E = typename G::E
using	V = typename G::V

Private Attributes
Identifiers< V >	deadendVertices
Identifiers< V >	forbiddenVertices

Detailed Description

template<class G>
class pgrouting::contraction::Pgr_deadend< G >

Definition at line 45 of file pgr_deadEndContraction.hpp.

Member Typedef Documentation

E

template<class G >

using pgrouting::contraction::Pgr_deadend< G >::E = typename G::E

private

Definition at line 48 of file pgr_deadEndContraction.hpp.

V

template<class G >

using pgrouting::contraction::Pgr_deadend< G >::V = typename G::V

private

Definition at line 47 of file pgr_deadEndContraction.hpp.

Constructor & Destructor Documentation

Pgr_deadend()

template<class G >

pgrouting::contraction::Pgr_deadend< G >::Pgr_deadend ( )

default

Member Function Documentation

calculateVertices()

template<class G >

void pgrouting::contraction::Pgr_deadend< G >::calculateVertices ( G &  graph )

inline

Definition at line 59 of file pgr_deadEndContraction.hpp.

                                     {
        for (const auto v : boost::make_iterator_range(vertices(graph.graph))) {
            if (is_dead_end(graph, v) && !forbiddenVertices.has(v)) {
                deadendVertices += v;
            }
        }
    }

References pgrouting::contraction::Pgr_deadend< G >::deadendVertices, pgrouting::contraction::Pgr_deadend< G >::forbiddenVertices, Identifiers< T >::has(), and pgrouting::contraction::Pgr_deadend< G >::is_dead_end().

Referenced by pgrouting::contraction::Pgr_deadend< G >::doContraction(), and pgrouting::contraction::Pgr_contract< G >::perform_deadEnd().

doContraction()

template<class G >

void pgrouting::contraction::Pgr_deadend< G >::doContraction ( G &  graph )

inline

Definition at line 78 of file pgr_deadEndContraction.hpp.

                                 {
        calculateVertices(graph);
 
        while (!deadendVertices.empty()) {
            V v = deadendVertices.front();
            deadendVertices -= v;
            pgassert(is_dead_end(graph, v));
 
            Identifiers<V> local;
            for (auto u : graph.find_adjacent_vertices(v)) {
                /*
                 * u{v1} --{v2}-> v{v3}
                 *
                 * u{v1 + v + v2 + v3}     v{}
                 */
                auto v2(graph.get_min_cost_edge(u, v));
                graph[u].contracted_vertices() += std::get<1>(v2);
                graph[u].contracted_vertices() += graph[v].id;
                graph[u].contracted_vertices() += graph[v].contracted_vertices();
 
                deadendVertices -= v;
                local += u;
            }
 
            graph[v].contracted_vertices().clear();
            boost::clear_vertex(v, graph.graph);
 
            /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
            CHECK_FOR_INTERRUPTS();
 
            for (const auto u : local) {
                if (is_dead_end(graph, u) && !forbiddenVertices.has(u)) {
                    deadendVertices += u;
                } else {
                    deadendVertices -= u;
                }
            }
        }
    }

References pgrouting::contraction::Pgr_deadend< G >::calculateVertices(), Identifiers< T >::clear(), pgrouting::contraction::Pgr_deadend< G >::deadendVertices, Identifiers< T >::empty(), pgrouting::contraction::Pgr_deadend< G >::forbiddenVertices, Identifiers< T >::front(), Identifiers< T >::has(), pgrouting::contraction::Pgr_deadend< G >::is_dead_end(), and pgassert.

Referenced by pgrouting::contraction::Pgr_contract< G >::perform_deadEnd().

is_dead_end()

template<class G >

bool pgrouting::contraction::Pgr_deadend< G >::is_dead_end ( G &  graph, V  v  )

inline

Definition at line 67 of file pgr_deadEndContraction.hpp.

                                    {
        if (graph.is_undirected()) {
            return graph.find_adjacent_vertices(v).size() == 1;
        }
 
        pgassert(graph.is_directed());
 
        return graph.find_adjacent_vertices(v).size() == 1
            || (graph.in_degree(v) > 0 && graph.out_degree(v) == 0);
    }

References pgassert.

Referenced by pgrouting::contraction::Pgr_deadend< G >::calculateVertices(), and pgrouting::contraction::Pgr_deadend< G >::doContraction().

setForbiddenVertices()

template<class G >

void pgrouting::contraction::Pgr_deadend< G >::setForbiddenVertices ( Identifiers< V >  forbidden_vertices )

inline

Definition at line 53 of file pgr_deadEndContraction.hpp.

                                               {
        forbiddenVertices = forbidden_vertices;
    }

References pgrouting::contraction::Pgr_deadend< G >::forbiddenVertices.

Referenced by pgrouting::contraction::Pgr_contract< G >::perform_deadEnd().

Member Data Documentation

deadendVertices

template<class G >

Identifiers<V> pgrouting::contraction::Pgr_deadend< G >::deadendVertices

private

Definition at line 119 of file pgr_deadEndContraction.hpp.

Referenced by pgrouting::contraction::Pgr_deadend< G >::calculateVertices(), and pgrouting::contraction::Pgr_deadend< G >::doContraction().

forbiddenVertices

template<class G >

Identifiers<V> pgrouting::contraction::Pgr_deadend< G >::forbiddenVertices

private

Definition at line 120 of file pgr_deadEndContraction.hpp.

Referenced by pgrouting::contraction::Pgr_deadend< G >::calculateVertices(), pgrouting::contraction::Pgr_deadend< G >::doContraction(), and pgrouting::contraction::Pgr_deadend< G >::setForbiddenVertices().

---

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

• pgr_deadEndContraction.hpp