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

#include "pgr_deadEndContraction.hpp"

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

Public Member Functions
void	add_if_dead_end (G &graph, V v)
void	calculateVertices (G &graph)
void	doContraction (G &graph)
bool	is_dead_end (G &graph, V v)
	true when v is a dead end More...
void	setForbiddenVertices (Identifiers< V > forbidden_vertices)

Private Types
typedef G::E	E
typedef G::V	V

Private Attributes
Identifiers< V >	deadendVertices
std::ostringstream	debug
Identifiers< V >	forbiddenVertices

Detailed Description

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

Definition at line 44 of file pgr_deadEndContraction.hpp.

Member Typedef Documentation

template<class G>

typedef G::E pgrouting::contraction::Pgr_deadend< G >::E

private

Definition at line 47 of file pgr_deadEndContraction.hpp.

template<class G>

typedef G::V pgrouting::contraction::Pgr_deadend< G >::V

private

Definition at line 46 of file pgr_deadEndContraction.hpp.

Member Function Documentation

template<class G >

void pgrouting::contraction::Pgr_deadend< G >::add_if_dead_end	(	G &	graph,
		V	v
	)

Definition at line 327 of file pgr_deadEndContraction.hpp.

                                             {
    if (is_dead_end(graph, v)) {
        deadendVertices += v;
    }
}

template<class G >

void pgrouting::contraction::Pgr_deadend< G >::calculateVertices

(

G &

graph

)

Definition at line 78 of file pgr_deadEndContraction.hpp.

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

                                               {
    debug << "Calculating vertices\n";

    for (auto vi = vertices(graph.graph).first;
            vi != vertices(graph.graph).second;
            ++vi) {
#ifndef NDEBUG
        debug << "Checking vertex " << graph[(*vi)].id << '\n';
#endif
        if (is_dead_end(graph, *vi)) {
#ifndef NDEBUG
            debug << "Adding " << graph[(*vi)].id << " to dead end" << '\n';
#endif
            deadendVertices += (*vi);
        }
    }
    deadendVertices -= forbiddenVertices;
}

Here is the caller graph for this function:

template<class G >

void pgrouting::contraction::Pgr_deadend< G >::doContraction

(

G &

graph

)

Definition at line 335 of file pgr_deadEndContraction.hpp.

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

                                      {
#ifndef NDEBUG
    debug << "Performing contraction\n";
#endif
    std::priority_queue<V, std::vector<V>, std::greater<V> > deadendPriority;

    for (V deadendVertex : deadendVertices) {
        deadendPriority.push(deadendVertex);
    }

    while (!deadendPriority.empty()) {
        V current_vertex = deadendPriority.top();
        deadendPriority.pop();

        if (!is_dead_end(graph, current_vertex)) {
            continue;
        }

        Identifiers<V> adjacent_vertices =
            graph.find_adjacent_vertices(current_vertex);

        for (auto adjacent_vertex : adjacent_vertices) {
#ifndef NDEBUG
            debug << "Contracting current vertex "
                << graph[current_vertex].id << std::endl;
#endif
            graph[adjacent_vertex].add_contracted_vertex(
                    graph[current_vertex], current_vertex);

#ifndef NDEBUG
            debug << "Adding contracted vertices of the edge\n";
#endif
            auto o_edges = out_edges(current_vertex, graph.graph);
            for (auto out = o_edges.first;
                    out != o_edges.second;
                    ++out) {
                debug << graph.graph[*out];
                graph.add_contracted_edge_vertices(
                        adjacent_vertex, graph[*out]);
            }
            auto i_edges = in_edges(current_vertex, graph.graph);
            for (auto in = i_edges.first;
                    in != i_edges.second; ++in) {
#ifndef NDEBUG
                debug << graph.graph[*in];
#endif
                graph.add_contracted_edge_vertices(adjacent_vertex, graph[*in]);
            }
#ifndef NDEBUG
            debug << "Current Vertex:\n";
            debug << graph[current_vertex];
            debug << "Adjacent Vertex:\n";
            debug << graph[adjacent_vertex];
#endif
            graph.disconnect_vertex(current_vertex);
            deadendVertices -= current_vertex;
#ifndef NDEBUG
            debug << "Adjacent vertex dead_end?: "
                << is_dead_end(graph, adjacent_vertex)
                << std::endl;
#endif
            if (is_dead_end(graph, adjacent_vertex)
                    && !forbiddenVertices.has(adjacent_vertex)) {
                deadendVertices += adjacent_vertex;
                deadendPriority.push(adjacent_vertex);
            }
        }
    }
}

Here is the caller graph for this function:

template<class G >

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

true when v is a dead end

• fobbiden_vertices
  • Not considered as dead end

undirected:

• There is only one adjacent vertex:
• All adjcent edges are from a single vertex

directed

case (1): (dead start)

• one outgoing edge,
• no incoming edge

case (2): (dead end)

• no outgoing edge,
• one incoming edge

case (3):

• one outgoing edge,
• one incoming edge
• one adjacent vertex

case (4):

• no outgoing edge,
• many incoming edges

case (5):

• many outgoing edge,
• many incoming edges
• All adjacent edges are from a single vertex

Definition at line 98 of file pgr_deadEndContraction.hpp.

References pgassert, and Identifiers< T >::size().

                                              {
#ifndef NDEBUG
    debug << "Is dead end: " << graph.graph[v].id << "?\n";
#endif

    if (forbiddenVertices.has(v)) {
        return false;
    }

    if (graph.is_undirected()) {
        Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(v);
        if (adjacent_vertices.size() == 1) {
            return true;
        }
        return false;
    }

    pgassert(graph.is_directed());
    /*
     * directed graph
     *
     * is dead end when:
     *  (2) one incoming edge, no outgoing edge (dead end)
     *  (3) one outgoing edge, one incoming edge
     *       and both are from/to the same vertex
     *  (4) many incoming edges
     *       and no outgoing edges
     *  (5) many outgoing edges TODO but all go to same vertex
     *       and no incoming edges
     *
     * NOT dead end when:
     *  (3) one outgoing edge, one incoming edge
     *       and both from/to different vertex
     *
     * note: when contracting case 4 & 5, the vertex has to be
     *       part of all the adjacent vertices
     */

    if (graph.in_degree(v) == 0 && graph.out_degree(v) == 1) {
        return true;
    }

    if (graph.in_degree(v) == 1 && graph.out_degree(v) == 0) {
        return true;
    }

    if (graph.out_degree(v) == 1 && graph.in_degree(v) == 1) {
        auto out_e = *(out_edges(v, graph.graph).first);
        auto in_e = *(in_edges(v, graph.graph).first);

        auto out_v = graph.is_source(v, out_e) ?
            graph.target(out_e) : graph.source(out_e);
        auto in_v = graph.is_source(v, in_e) ?
            graph.target(in_e) : graph.source(in_e);

        if (out_v == in_v) {
            return true;
        }
        return false;
    }

    if (graph.in_degree(v) > 0 && graph.out_degree(v) == 0) {
        return true;
    }

    if (graph.in_degree(v) > 0 && graph.out_degree(v) > 0) {
        auto adjacent_vertices = graph.find_adjacent_vertices(v);
        if (adjacent_vertices.size() == 1) {
            return true;
        }
    }
    debug << "Is Not Dead End\n";
    return false;
}

Here is the call graph for this function:

template<class G >

void pgrouting::contraction::Pgr_deadend< G >::setForbiddenVertices

(

Identifiers< V >

forbidden_vertices

)

Definition at line 68 of file pgr_deadEndContraction.hpp.

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

                                           {
#ifndef NDEBUG
    debug << "Setting forbidden vertices\n";
#endif
    forbiddenVertices = forbidden_vertices;
}

Here is the caller graph for this function:

Member Data Documentation

template<class G>

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

private

Definition at line 60 of file pgr_deadEndContraction.hpp.

template<class G>

std::ostringstream pgrouting::contraction::Pgr_deadend< G >::debug

private

Definition at line 62 of file pgr_deadEndContraction.hpp.

template<class G>

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

private

Definition at line 61 of file pgr_deadEndContraction.hpp.

---

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

• /home/vicky/pgrouting/pgrouting/pgrouting/include/contraction/pgr_deadEndContraction.hpp