PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgrouting::contraction::Pgr_linear< G > Class Template Reference

#include "pgr_linearContraction.hpp"

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

Public Member Functions

 Pgr_linear ()
 
void calculateVertices (G &graph)
 
void doContraction (G &graph)
 
void setForbiddenVertices (Identifiers< V > forbidden_vertices)
 

Private Types

typedef G::degree_size_type degree_size_type
 
typedef G::E E
 
typedef G::E_i E_i
 
typedef G::EI_i EI_i
 
typedef G::EO_i EO_i
 
typedef G::V V
 
typedef G::V_i V_i
 

Private Member Functions

void add_edge_pair (V vertex, int64_t &incoming_eid, int64_t &outgoing_eid)
 
void add_if_linear (G &graph, V v)
 
void add_shortcut (G &graph, V vertex, E incoming_edge, E outgoing_edge)
 add edges(shortuct) to the graph during contraction More...
 
void add_shortcut (G &graph, pgrouting::CH_edge &shortcut)
 
int64_t get_next_id ()
 
bool is_linear (G &graph, V v)
 

Private Attributes

std::ostringstream debug
 
Identifiers< VforbiddenVertices
 
int64_t last_edge_id
 
Identifiers< VlinearVertices
 

Detailed Description

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

Definition at line 46 of file pgr_linearContraction.hpp.

Member Typedef Documentation

template<class G>
typedef G::degree_size_type pgrouting::contraction::Pgr_linear< G >::degree_size_type
private

Definition at line 54 of file pgr_linearContraction.hpp.

template<class G>
typedef G::E pgrouting::contraction::Pgr_linear< G >::E
private

Definition at line 49 of file pgr_linearContraction.hpp.

template<class G>
typedef G::E_i pgrouting::contraction::Pgr_linear< G >::E_i
private

Definition at line 51 of file pgr_linearContraction.hpp.

template<class G>
typedef G::EI_i pgrouting::contraction::Pgr_linear< G >::EI_i
private

Definition at line 53 of file pgr_linearContraction.hpp.

template<class G>
typedef G::EO_i pgrouting::contraction::Pgr_linear< G >::EO_i
private

Definition at line 52 of file pgr_linearContraction.hpp.

template<class G>
typedef G::V pgrouting::contraction::Pgr_linear< G >::V
private

Definition at line 48 of file pgr_linearContraction.hpp.

template<class G>
typedef G::V_i pgrouting::contraction::Pgr_linear< G >::V_i
private

Definition at line 50 of file pgr_linearContraction.hpp.

Constructor & Destructor Documentation

template<class G>
pgrouting::contraction::Pgr_linear< G >::Pgr_linear ( )
inline

Member Function Documentation

template<class G>
void pgrouting::contraction::Pgr_linear< G >::add_edge_pair ( V  vertex,
int64_t &  incoming_eid,
int64_t &  outgoing_eid 
)
private
template<class G>
void pgrouting::contraction::Pgr_linear< G >::add_if_linear ( G &  graph,
V  v 
)
private
template<class G >
void pgrouting::contraction::Pgr_linear< G >::add_shortcut ( G &  graph,
V  vertex,
E  incoming_edge,
E  outgoing_edge 
)
private

add edges(shortuct) to the graph during contraction

a –incomming–> b —outgoing–> c

a -> c

edge (a, c) is a new edge: shortcut e.contracted_vertices = b + b.contracted vertices b is "removed" disconnected from the graph

  • by removing all edges to/from b

Definition at line 227 of file pgr_linearContraction.hpp.

References pgrouting::CH_edge::add_contracted_edge_vertices(), pgrouting::CH_edge::add_contracted_vertex(), Identifiers< T >::front(), pgassert, and Identifiers< T >::pop_front().

230  {
231  pgassert(incoming_edge != outgoing_edge);
232 
233  auto a = graph.adjacent(vertex, incoming_edge);
234  auto c = graph.adjacent(vertex, outgoing_edge);
235  pgassert(a != vertex);
236  pgassert(a != c);
237  pgassert(vertex != c);
238 
239  if (graph.is_undirected()) {
240  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(vertex);
241 
242  V vertex_1 = adjacent_vertices.front();
243  adjacent_vertices.pop_front();
244  V vertex_2 = adjacent_vertices.front();
245  adjacent_vertices.pop_front();
246 
247  E shortcut_E;
248  CH_edge shortcut(get_next_id(), graph[vertex_1].id,
249  graph[vertex_2].id,
250  graph[incoming_edge].cost + graph[outgoing_edge].cost);
251  shortcut.add_contracted_vertex(graph[vertex], vertex);
252  shortcut.add_contracted_edge_vertices(graph[incoming_edge]);
253  shortcut.add_contracted_edge_vertices(graph[outgoing_edge]);
254  debug << "Adding shortcut\n";
255  debug << shortcut;
256  graph.add_shortcut(shortcut);
257  debug << "Added shortcut\n";
258  } else {
259  CH_edge shortcut(
260  get_next_id(),
261  graph[a].id,
262  graph[c].id,
263  graph[incoming_edge].cost + graph[outgoing_edge].cost);
264  shortcut.add_contracted_vertex(graph[vertex], vertex);
265  shortcut.add_contracted_edge_vertices(graph[incoming_edge]);
266  shortcut.add_contracted_edge_vertices(graph[outgoing_edge]);
267  debug << "Adding shortcut\n";
268  debug << shortcut;
269  graph.add_shortcut(shortcut);
270  debug << "Added shortcut\n";
271  }
272 }
void pop_front()
Definition: identifiers.hpp:82
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
T front() const
Definition: identifiers.hpp:79

Here is the call graph for this function:

template<class G >
void pgrouting::contraction::Pgr_linear< G >::add_shortcut ( G &  graph,
pgrouting::CH_edge shortcut 
)
private

Definition at line 274 of file pgr_linearContraction.hpp.

275  {
276  graph.add_shortcut(shortcut);
277 }
template<class G >
void pgrouting::contraction::Pgr_linear< G >::calculateVertices ( G &  graph)

Definition at line 115 of file pgr_linearContraction.hpp.

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

115  {
116  debug << "Calculating vertices\n";
117  V_i vi;
118  for (vi = vertices(graph.graph).first;
119  vi != vertices(graph.graph).second;
120  ++vi) {
121  debug << "Checking vertex " << graph.graph[(*vi)].id << '\n';
122  if (is_linear(graph, *vi)) {
123  linearVertices += (*vi);
124  }
125  }
127 }

Here is the caller graph for this function:

template<class G >
void pgrouting::contraction::Pgr_linear< G >::doContraction ( G &  graph)

Definition at line 132 of file pgr_linearContraction.hpp.

References DIRECTED, Identifiers< T >::front(), pgassert, Identifiers< T >::pop_front(), Identifiers< T >::size(), and UNDIRECTED.

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

132  {
133  std::ostringstream contraction_debug;
134  contraction_debug << "Performing contraction\n";
135  std::priority_queue<V, std::vector<V>, std::greater<V> > linearPriority;
136  for (const auto linearVertex : linearVertices) {
137  linearPriority.push(linearVertex);
138  }
139  contraction_debug << "Linear vertices" << std::endl;
140  for (const auto v : linearVertices) {
141  contraction_debug << graph[v].id << ", ";
142  }
143  contraction_debug << std::endl;
144  while (!linearPriority.empty()) {
145  V current_vertex = linearPriority.top();
146  linearPriority.pop();
147  if (!is_linear(graph, current_vertex)) {
148  linearVertices -= current_vertex;
149  continue;
150  }
151  Identifiers<V> adjacent_vertices =
152  graph.find_adjacent_vertices(current_vertex);
153  pgassert(adjacent_vertices.size() == 2);
154 
155  V vertex_1 = adjacent_vertices.front();
156  adjacent_vertices.pop_front();
157  V vertex_2 = adjacent_vertices.front();
158  adjacent_vertices.pop_front();
159 
160  contraction_debug << "Adjacent vertices\n";
161  contraction_debug << graph[vertex_1].id
162  << ", " << graph[vertex_2].id
163  << std::endl;
164 
165  if (graph.m_gType == DIRECTED) {
166  if (graph.out_degree_to_vertex(vertex_1, current_vertex) > 0 &&
167  graph.in_degree_from_vertex(vertex_2, current_vertex) > 0) {
168  E e1 = graph.get_min_cost_edge(vertex_1,
169  current_vertex);
170  E e2 = graph.get_min_cost_edge(current_vertex,
171  vertex_2);
172  add_shortcut(graph, current_vertex, e1, e2);
173  }
174 
175  if (graph.out_degree_to_vertex(vertex_2, current_vertex) > 0 &&
176  graph.in_degree_from_vertex(vertex_1, current_vertex) > 0) {
177  E e1 = graph.get_min_cost_edge(vertex_2,
178  current_vertex);
179  E e2 = graph.get_min_cost_edge(current_vertex,
180  vertex_1);
181  add_shortcut(graph, current_vertex, e1, e2);
182  }
183  } else if (graph.m_gType == UNDIRECTED) {
184  if (graph.out_degree_to_vertex(vertex_1, current_vertex) > 0 &&
185  graph.in_degree_from_vertex(vertex_2, current_vertex) > 0) {
186  contraction_debug << "UNDIRECTED graph before contraction\n";
187  graph.print_graph(contraction_debug);
188  E e1 = graph.get_min_cost_edge(vertex_1,
189  current_vertex);
190  E e2 = graph.get_min_cost_edge(current_vertex,
191  vertex_2);
192  add_shortcut(graph, current_vertex, e1, e2);
193  }
194  }
195 
196  graph.disconnect_vertex(current_vertex);
197  linearVertices -= current_vertex;
198  if (is_linear(graph, vertex_1)
199  && !forbiddenVertices.has(vertex_1)) {
200  linearPriority.push(vertex_1);
201  linearVertices += vertex_1;
202  }
203  if (is_linear(graph, vertex_2)
204  && !forbiddenVertices.has(vertex_2)) {
205  linearPriority.push(vertex_2);
206  linearVertices += vertex_2;
207  }
208  }
209  debug << contraction_debug.str().c_str() << "\n";
210 }
bool has(const T other) const
true ids() has element
Definition: identifiers.hpp:97
void add_shortcut(G &graph, V vertex, E incoming_edge, E outgoing_edge)
add edges(shortuct) to the graph during contraction
void pop_front()
Definition: identifiers.hpp:82
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
size_t size() const
Definition: identifiers.hpp:77
T front() const
Definition: identifiers.hpp:79

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G>
int64_t pgrouting::contraction::Pgr_linear< G >::get_next_id ( )
inlineprivate
template<class G >
bool pgrouting::contraction::Pgr_linear< G >::is_linear ( G &  graph,
V  v 
)
private

Definition at line 99 of file pgr_linearContraction.hpp.

References Identifiers< T >::size().

99  {
100  degree_size_type in_degree, out_degree;
101  in_degree = graph.in_degree(v);
102  out_degree = graph.out_degree(v);
103  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(v);
104  if (adjacent_vertices.size() == 2) {
105  if (in_degree > 0 && out_degree > 0) {
106  debug << graph.graph[v].id << " is linear " << std::endl;
107  return true;
108  }
109  }
110  debug << graph.graph[v].id << " is not linear " << std::endl;
111  return false;
112 }
size_t size() const
Definition: identifiers.hpp:77

Here is the call graph for this function:

template<class G >
void pgrouting::contraction::Pgr_linear< G >::setForbiddenVertices ( Identifiers< V forbidden_vertices)

Definition at line 91 of file pgr_linearContraction.hpp.

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

92  {
93  debug << "Setting forbidden vertices\n";
94  forbiddenVertices = forbidden_vertices;
95 }

Here is the caller graph for this function:

Member Data Documentation

template<class G>
std::ostringstream pgrouting::contraction::Pgr_linear< G >::debug
private

Definition at line 84 of file pgr_linearContraction.hpp.

template<class G>
Identifiers<V> pgrouting::contraction::Pgr_linear< G >::forbiddenVertices
private

Definition at line 81 of file pgr_linearContraction.hpp.

template<class G>
int64_t pgrouting::contraction::Pgr_linear< G >::last_edge_id
private
template<class G>
Identifiers<V> pgrouting::contraction::Pgr_linear< G >::linearVertices
private

Definition at line 80 of file pgr_linearContraction.hpp.


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