PGROUTING  2.6
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< VdeadendVertices
 
std::ostringstream debug
 
Identifiers< VforbiddenVertices
 

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.

References pgrouting::contraction::Pgr_deadend< G >::deadendVertices, and pgrouting::contraction::Pgr_deadend< G >::is_dead_end().

327  {
328  if (is_dead_end(graph, v)) {
329  deadendVertices += v;
330  }
331 }
bool is_dead_end(G &graph, V v)
true when v is a dead end

Here is the call graph for this function:

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

Definition at line 78 of file pgr_deadEndContraction.hpp.

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

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

78  {
79  debug << "Calculating vertices\n";
80 
81  for (auto vi = vertices(graph.graph).first;
82  vi != vertices(graph.graph).second;
83  ++vi) {
84 #ifndef NDEBUG
85  debug << "Checking vertex " << graph[(*vi)].id << '\n';
86 #endif
87  if (is_dead_end(graph, *vi)) {
88 #ifndef NDEBUG
89  debug << "Adding " << graph[(*vi)].id << " to dead end" << '\n';
90 #endif
91  deadendVertices += (*vi);
92  }
93  }
95 }
bool is_dead_end(G &graph, V v)
true when v is a dead end

Here is the call graph for this function:

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.

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

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

335  {
336 #ifndef NDEBUG
337  debug << "Performing contraction\n";
338 #endif
339  std::priority_queue<V, std::vector<V>, std::greater<V> > deadendPriority;
340 
341  for (V deadendVertex : deadendVertices) {
342  deadendPriority.push(deadendVertex);
343  }
344 
345  while (!deadendPriority.empty()) {
346  V current_vertex = deadendPriority.top();
347  deadendPriority.pop();
348 
349  if (!is_dead_end(graph, current_vertex)) {
350  continue;
351  }
352 
353  Identifiers<V> adjacent_vertices =
354  graph.find_adjacent_vertices(current_vertex);
355 
356  for (auto adjacent_vertex : adjacent_vertices) {
357 #ifndef NDEBUG
358  debug << "Contracting current vertex "
359  << graph[current_vertex].id << std::endl;
360 #endif
361  graph[adjacent_vertex].add_contracted_vertex(
362  graph[current_vertex], current_vertex);
363 
364 #ifndef NDEBUG
365  debug << "Adding contracted vertices of the edge\n";
366 #endif
367  auto o_edges = out_edges(current_vertex, graph.graph);
368  for (auto out = o_edges.first;
369  out != o_edges.second;
370  ++out) {
371  debug << graph.graph[*out];
372  graph.add_contracted_edge_vertices(
373  adjacent_vertex, graph[*out]);
374  }
375  auto i_edges = in_edges(current_vertex, graph.graph);
376  for (auto in = i_edges.first;
377  in != i_edges.second; ++in) {
378 #ifndef NDEBUG
379  debug << graph.graph[*in];
380 #endif
381  graph.add_contracted_edge_vertices(adjacent_vertex, graph[*in]);
382  }
383 #ifndef NDEBUG
384  debug << "Current Vertex:\n";
385  debug << graph[current_vertex];
386  debug << "Adjacent Vertex:\n";
387  debug << graph[adjacent_vertex];
388 #endif
389  graph.disconnect_vertex(current_vertex);
390  deadendVertices -= current_vertex;
391 #ifndef NDEBUG
392  debug << "Adjacent vertex dead_end?: "
393  << is_dead_end(graph, adjacent_vertex)
394  << std::endl;
395 #endif
396  if (is_dead_end(graph, adjacent_vertex)
397  && !forbiddenVertices.has(adjacent_vertex)) {
398  deadendVertices += adjacent_vertex;
399  deadendPriority.push(adjacent_vertex);
400  }
401  }
402  }
403 }
bool has(const T other) const
true ids() has element
Definition: identifiers.hpp:97
bool is_dead_end(G &graph, V v)
true when v is a dead end

Here is the call graph for this function:

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
dot_inline_dotgraph_2.png

directed

case (1): (dead start)

  • one outgoing edge,
  • no incoming edge
dot_inline_dotgraph_3.png

case (2): (dead end)

  • no outgoing edge,
  • one incoming edge
dot_inline_dotgraph_4.png

case (3):

  • one outgoing edge,
  • one incoming edge
  • one adjacent vertex
dot_inline_dotgraph_5.png

case (4):

  • no outgoing edge,
  • many incoming edges
dot_inline_dotgraph_6.png

case (5):

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

Definition at line 98 of file pgr_deadEndContraction.hpp.

References pgrouting::contraction::Pgr_deadend< G >::debug, pgrouting::contraction::Pgr_deadend< G >::forbiddenVertices, Identifiers< T >::has(), pgassert, and Identifiers< T >::size().

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

98  {
99 #ifndef NDEBUG
100  debug << "Is dead end: " << graph.graph[v].id << "?\n";
101 #endif
102 
103  if (forbiddenVertices.has(v)) {
109  return false;
110  }
111 
112  if (graph.is_undirected()) {
137  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(v);
138  if (adjacent_vertices.size() == 1) {
139  return true;
140  }
141  return false;
142  }
143 
144  pgassert(graph.is_directed());
145  /*
146  * directed graph
147  *
148  * is dead end when:
149  * (2) one incoming edge, no outgoing edge (dead end)
150  * (3) one outgoing edge, one incoming edge
151  * and both are from/to the same vertex
152  * (4) many incoming edges
153  * and no outgoing edges
154  * (5) many outgoing edges TODO but all go to same vertex
155  * and no incoming edges
156  *
157  * NOT dead end when:
158  * (3) one outgoing edge, one incoming edge
159  * and both from/to different vertex
160  *
161  * note: when contracting case 4 & 5, the vertex has to be
162  * part of all the adjacent vertices
163  */
164 
165  if (graph.in_degree(v) == 0 && graph.out_degree(v) == 1) {
190  return true;
191  }
192 
193  if (graph.in_degree(v) == 1 && graph.out_degree(v) == 0) {
216  return true;
217  }
218 
219  if (graph.out_degree(v) == 1 && graph.in_degree(v) == 1) {
244  auto out_e = *(out_edges(v, graph.graph).first);
245  auto in_e = *(in_edges(v, graph.graph).first);
246 
247  auto out_v = graph.is_source(v, out_e) ?
248  graph.target(out_e) : graph.source(out_e);
249  auto in_v = graph.is_source(v, in_e) ?
250  graph.target(in_e) : graph.source(in_e);
251 
252  if (out_v == in_v) {
253  return true;
254  }
255  return false;
256  }
257 
258  if (graph.in_degree(v) > 0 && graph.out_degree(v) == 0) {
284  return true;
285  }
286 
287  if (graph.in_degree(v) > 0 && graph.out_degree(v) > 0) {
316  auto adjacent_vertices = graph.find_adjacent_vertices(v);
317  if (adjacent_vertices.size() == 1) {
318  return true;
319  }
320  }
321  debug << "Is Not Dead End\n";
322  return false;
323 }
bool has(const T other) const
true ids() has element
Definition: identifiers.hpp:97
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
size_t size() const
Definition: identifiers.hpp:77

Here is the call graph for this function:

Here is the caller 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.

References pgrouting::contraction::Pgr_deadend< G >::debug, and pgrouting::contraction::Pgr_deadend< G >::forbiddenVertices.

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

69  {
70 #ifndef NDEBUG
71  debug << "Setting forbidden vertices\n";
72 #endif
73  forbiddenVertices = forbidden_vertices;
74 }

Here is the caller graph for this function:

Member Data Documentation


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