pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_contractionGraph.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_contractionGraph.hpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 Function's developer:
9 Copyright (c) 2016 Rohith Reddy
10 Mail:
11 
12 ------
13 
14 This program is free software; you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation; either version 2 of the License, or
17 (at your option) any later version.
18 
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23 
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 
28  ********************************************************************PGR-GNU*/
29 
30 #pragma once
31 
32 #if defined(__MINGW32__) || defined(_MSC_VER)
33 #include <winsock2.h>
34 #include <windows.h>
35 
36 #ifdef open
37 #undef open
38 #endif
39 
40 #ifdef unlink
41 #undef unlink
42 #endif
43 
44 #endif
45 
46 
47 #include <limits>
48 #include <algorithm>
49 #include <vector>
50 #include <map>
51 #include "../../common/src/pgr_base_graph.hpp"
52 
53 
54 namespace pgrouting {
55 
56 namespace graph {
57 template <class G, typename T_V, typename T_E>
59 }
60 
62  boost::adjacency_list < boost::listS, boost::vecS,
63  boost::undirectedS,
66 
68  boost::adjacency_list < boost::listS, boost::vecS,
69  boost::bidirectionalS,
72 
73 namespace graph {
74 
75 template <class G, typename T_V, typename T_E>
76 class Pgr_contractionGraph : public Pgr_base_graph<G, T_V, T_E> {
77  public:
78  typedef typename boost::graph_traits < G >::vertex_descriptor V;
79  typedef typename boost::graph_traits < G >::edge_descriptor E;
80  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
81  typedef typename boost::graph_traits < G >::edge_iterator E_i;
82  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
83  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
84  typedef typename std::map< int64_t, V > id_to_V;
85  typedef typename id_to_V::const_iterator LI;
87  std::vector< T_E > shortcuts;
88  typedef typename boost::graph_traits < G >::degree_size_type degree_size_type;
89 
93  static bool compareById(const T_E &edge1, const T_E &edge2) {
94  return edge1.id > edge2.id;
95  }
96 
100  Pgr_contractionGraph< G , T_V, T_E >(const std::vector< T_V > &vertices, graphType gtype)
101  : Pgr_base_graph< G , T_V, T_E >(vertices, gtype) {
102  }
103 
109  }
110 
111  // ! @name Insert data
112  // @{
121  template < typename T >
122  void graph_insert_data(const T *edges, int64_t count) {
123  graph_insert_data(std::vector < T >(edges, edges + count));
124  }
129  template < typename T >
130  void graph_insert_data(const std::vector < T > &edges) {
131  for (const auto edge : edges) {
133  }
134  }
135  // @}
136 
137  // ! @brief True when *v* is in the graph
144  bool is_connected(int64_t v) const {
145  if (this->in_degree(this->get_V(v)) == 0 && this->out_degree(this->get_V(v)) == 0) {
146  return false;
147  }
148  return true;
149  }
150 
151  // ! @brief get the vertex descriptor of the vertex adjacent to *v*
158  EO_i out, out_end;
159  EI_i in, in_end;
160  V out_vertex, in_vertex;
161  out_vertex = in_vertex = -1;
162  for (boost::tie(out, out_end) = out_edges(v, this->graph);
163  out != out_end; ++out) {
164  out_vertex = target(*out, this->graph);
165  }
166  for (boost::tie(in, in_end) = in_edges(v, this->graph);
167  in != in_end; ++in) {
168  in_vertex = source(*in, this->graph);
169  }
170  if (in_vertex == -1)
171  return out_vertex;
172  else if (out_vertex == -1)
173  return in_vertex;
174  else if (out_vertex == in_vertex)
175  return in_vertex;
176  return out_vertex;
177  }
178 
184  EO_i out, out_end;
185  EI_i in, in_end;
186  Identifiers<V> adjacent_vertices;
187  V out_vertex, in_vertex;
188  out_vertex = in_vertex = -1;
189  for (boost::tie(out, out_end) = out_edges(v, this->graph);
190  out != out_end; ++out) {
191  out_vertex = target(*out, this->graph);
192  adjacent_vertices += out_vertex;
193  }
194  for (boost::tie(in, in_end) = in_edges(v, this->graph);
195  in != in_end; ++in) {
196  in_vertex = source(*in, this->graph);
197  adjacent_vertices += in_vertex;
198  }
199  return adjacent_vertices;
200  }
201 
202  T_V& operator[](V v) {
203  return this->graph[v];
204  }
205 
206  T_E& operator[](E e) {
207  return this->graph[e];
208  }
209 
214  void get_ids(std::ostringstream &log,
215  Identifiers<int64_t> boost_ids) {
216  log << "{";
217  for (auto id : boost_ids) {
218  log << this->graph[id].id << ", ";
219  }
220  log << "}";
221  }
222 
228  void get_ids(int64_t **contracted_vertices,
229  int &contracted_vertices_size,
230  Identifiers<int64_t> boost_ids) {
231  contracted_vertices_size = (int)boost_ids.size();
232  (*contracted_vertices) = (int64_t*)malloc(sizeof(int64_t)*contracted_vertices_size);
233  int64_t count = 0;
234  for (auto id : boost_ids) {
235  (*contracted_vertices)[count++] = this->graph[id].id;
236  }
237  }
238 
242  void get_remaining_vertices(std::vector<T_V>& remaining_vertices) {
243  for (auto vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi) {
244  if (!removed_vertices.has(*vi)) {
245  remaining_vertices.push_back(this->graph[*vi]);
246  }
247  }
248  }
249 
253  void get_changed_vertices(Identifiers<int64_t>& remaining_vertices) {
254  // log << "remaining_vertices\n";
255  for (auto vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi) {
256  if (!removed_vertices.has(*vi) && this->graph[*vi].has_contracted_vertices()) {
257  remaining_vertices += this->graph[*vi].id;
258  }
259  }
260  }
261 
265  void get_shortcuts(std::vector<T_E>& shortcut_edges) {
266  // log << "Getting shortcuts\n";
267  for (auto shortcut : shortcuts) {
268  // log << shortcut;
269  shortcut_edges.push_back(shortcut);
270  }
271  std::sort(shortcut_edges.begin(), shortcut_edges.end(), compareById);
272  }
273 
279  E get_min_cost_edge(V source, V destination) {
280  E e;
281  EO_i out_i, out_end;
282  E min_cost_edge;
283  double min_cost = std::numeric_limits<double>::max();
284  for (boost::tie(out_i, out_end) = boost::out_edges(source, this->graph);
285  out_i != out_end; ++out_i) {
286  e = *out_i;
287  if (target(e, this->graph) == destination) {
288  if (this->graph[e].cost < min_cost) {
289  min_cost = this->graph[e].cost;
290  min_cost_edge = e;
291  }
292  }
293  }
294  // log << "Min cost edge from " << this->graph[source].id << " to " << this->graph[destination].id << std::endl;
295  // log << this->graph[min_cost_edge];
296  return min_cost_edge;
297  }
298 
305  degree_size_type degree = 0;
306  EI_i in_i, in_end;
307  E e;
308  for (boost::tie(in_i, in_end) = boost::in_edges(vertex, this->graph);
309  in_i != in_end; ++in_i) {
310  e = *in_i;
311 
312  if (source(e, this->graph) == neighbor) {
313  degree++;
314  }
315  }
316  return degree;
317  }
324  degree_size_type degree = 0;
325  EO_i out_i, out_end;
326  E e;
327  for (boost::tie(out_i, out_end) = boost::out_edges(vertex, this->graph);
328  out_i != out_end; ++out_i) {
329  e = *out_i;
330 
331  if (target(e, this->graph) == neighbor) {
332  degree++;
333  }
334  }
335  return degree;
336  }
337 
340  void print_shortcuts(std::ostringstream& log) {
341  log << "Printing shortcuts\n";
342  for (auto shortcut : shortcuts) {
343  log << shortcut;
344  }
345  }
346 
350  void print_graph(std::ostringstream &log) {
351  EO_i out, out_end;
352  for (auto vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi) {
353  if ((*vi) >= this->m_num_vertices) break;
354  log << this->graph[(*vi)].id << "(" << (*vi) << ")"
355  << this->graph[(*vi)].contracted_vertices() << std::endl;
356  log << " out_edges_of(" << this->graph[(*vi)].id << "):";
357  for (boost::tie(out, out_end) = out_edges(*vi, this->graph);
358  out != out_end; ++out) {
359  log << ' ' << this->graph[*out].id << "=(" << this->graph[source(*out, this->graph)].id
360  << ", " << this->graph[target(*out, this->graph)].id << ") = "
361  << this->graph[*out].cost <<"\t";
362  }
363  log << std::endl;
364  }
365  }
366 
371  void get_contracted_vertices(std::ostringstream &log, int64_t vid) {
372  if (!this->has_vertex(vid)) return;
373  V v = this->get_V(vid);
374  log << "{";
375  for (auto vertex : this->graph[v].contracted_vertices()) {
376  log << this->graph[vertex].id << ", ";
377  }
378  log << "}";
379  }
380 
381 
387  void get_contracted_vertices(int64_t **contracted_vertices,
388  int &contracted_vertices_size, int64_t vid) {
389  if (!this->has_vertex(vid)) return;
390  V v = this->get_V(vid);
391  contracted_vertices_size = (int)this->graph[v].contracted_vertices().size();
392  (*contracted_vertices) = (int64_t*)malloc(sizeof(int64_t)*contracted_vertices_size);
393  int64_t count = 0;
394  for (auto vertex : this->graph[v].contracted_vertices()) {
395  (*contracted_vertices)[count++] = this->graph[vertex].id;
396  }
397  }
398 
403  void add_contracted_edge_vertices(V v, T_E &e) {
404  for (auto vid : e.contracted_vertices()) {
405  this->graph[v].add_vertex_id(vid);
406  }
407  e.clear_contracted_vertices();
408  }
409 
413  template < typename T>
414  void graph_add_edge(const T &edge) {
415  bool inserted;
416  E e;
417  if ((edge.cost < 0) && (edge.reverse_cost < 0))
418  return;
419  /*
420  * true: for source
421  * false: for target
422  */
423  auto vm_s = this->get_V(T_V(edge, true));
424  auto vm_t = this->get_V(T_V(edge, false));
425  pgassert(this->vertices_map.find(edge.source) != this->vertices_map.end());
426  pgassert(this->vertices_map.find(edge.target) != this->vertices_map.end());
427  if (edge.cost >= 0) {
428  boost::tie(e, inserted) =
429  boost::add_edge(vm_s, vm_t, this->graph);
430  this->graph[e].cost = edge.cost;
431  this->graph[e].id = edge.id;
432  this->graph[e].first = true;
433  this->graph[e].source = edge.source;
434  this->graph[e].target = edge.target;
435  }
436  if (edge.reverse_cost >= 0) {
437  boost::tie(e, inserted) =
438  boost::add_edge(vm_t, vm_s, this->graph);
439 
440  this->graph[e].cost = edge.reverse_cost;
441  this->graph[e].id = edge.id;
442  this->graph[e].first = false;
443  this->graph[e].target = edge.source;
444  this->graph[e].source = edge.target;
445  }
446  }
447 
452  void graph_add_shortcut(const T_E &edge, std::ostringstream& log) {
453  bool inserted;
454  E e;
455  if (edge.cost < 0)
456  return;
457  /*
458  * true: for source
459  * false: for target
460  */
461  log << "Graph before adding shortcut\n";
462  print_graph(log);
463  pgassert(this->vertices_map.find(edge.source) != this->vertices_map.end());
464  pgassert(this->vertices_map.find(edge.target) != this->vertices_map.end());
465  auto vm_s = this->get_V(edge.source);
466  auto vm_t = this->get_V(edge.target);
467  log << "Adding edge between " << this->graph[vm_s] << ", "
468  << this->graph[vm_t] << std::endl;
469 
470  if (edge.cost >= 0) {
471  boost::tie(e, inserted) =
472  boost::add_edge(vm_s, vm_t, this->graph);
473  log << "inserted: " << inserted << std::endl;
474  this->graph[e].cp_members(edge, log);
475  log << this->graph[e];
476  // this->graph[e].id = this->graph[e].eid;
477  log << "Graph after adding shortcut\n";
478  print_graph(log);
479  T_E shortcut;
480  shortcut.cp_members(edge, log);
481  shortcuts.push_back(shortcut);
482  }
483  }
484 
494  void disconnect_vertex(std::ostringstream &log, V vertex) {
495  T_E d_edge;
496  EO_i out, out_end;
497  log << "Disconnecting current vertex " << this->graph[vertex].id << "\n";
498  removed_vertices += vertex;
499  // store the edges that are going to be removed
500  for (boost::tie(out, out_end) = out_edges(vertex, this->graph);
501  out != out_end; ++out) {
502  d_edge.id = this->graph[*out].id;
503  d_edge.source = this->graph[source(*out, this->graph)].id;
504  d_edge.target = this->graph[target(*out, this->graph)].id;
505  d_edge.cost = this->graph[*out].cost;
506  this->removed_edges.push_back(d_edge);
507  }
508 
509  // special case
510  if (this->m_gType == DIRECTED) {
511  EI_i in, in_end;
512  for (boost::tie(in, in_end) = in_edges(vertex, this->graph);
513  in != in_end; ++in) {
514  d_edge.id = this->graph[*in].id;
515  d_edge.source = this->graph[source(*in, this->graph)].id;
516  d_edge.target = this->graph[target(*in, this->graph)].id;
517  d_edge.cost = this->graph[*in].cost;
518  this->removed_edges.push_back(d_edge);
519  }
520  }
521  try {
522  boost::clear_vertex(vertex, this->graph);
523  }
524  catch ( ... ) {
525  log << "Caught unknown exception!\n";
526  }
527  }
528 };
529 } // namespace graph
530 } // namespace pgrouting
void get_ids(std::ostringstream &log, Identifiers< int64_t > boost_ids)
get the user ids given the boost graph ids in string format
bool has(const T other) const
Returns a boolean value true or false.
Identifiers< V > find_adjacent_vertices(V v) const
get the vertex descriptors of adjacent vertices of v
graph::Pgr_contractionGraph< boost::adjacency_list< boost::listS, boost::vecS, boost::undirectedS, contraction::Vertex, contraction::Edge >, contraction::Vertex, contraction::Edge > CHUndirectedGraph
void print_graph(std::ostringstream &log)
print the graph with contracted vertices of all vertices and edges
void print_shortcuts(std::ostringstream &log)
print the edges added during contraction
void disconnect_vertex(std::ostringstream &log, V vertex)
Disconnects all incoming and outgoing edges from the vertex boost::graph doesn't recommend th to inse...
boost::graph_traits< G >::edge_iterator E_i
bool is_connected(int64_t v) const
True when.
void get_contracted_vertices(std::ostringstream &log, int64_t vid)
get the contracted vertex ids of a given vertex in string format
boost::graph_traits< G >::vertex_iterator V_i
void get_remaining_vertices(std::vector< T_V > &remaining_vertices)
get the remaining vertices of the graph after contraction
void graph_add_edge(const T &edge)
Inserts an edge of type T into the graph.
boost::graph_traits< G >::edge_descriptor E
boost::graph_traits< G >::vertex_descriptor V
graphType m_gType
type (DIRECTED or UNDIRECTED)
bool has_vertex(int64_t vid) const
True when vid is in the graph.
boost::graph_traits< G >::degree_size_type degree_size_type
void get_contracted_vertices(int64_t **contracted_vertices, int &contracted_vertices_size, int64_t vid)
get the contracted vertex ids of a given vertex in string format
static bool compareById(const T_E &edge1, const T_E &edge2)
Binary function that accepts two elements , and returns a value convertible to bool.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
void get_shortcuts(std::vector< T_E > &shortcut_edges)
get the edges of the graph that are added during contraction
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
graph::Pgr_contractionGraph< boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, contraction::Vertex, contraction::Edge >, contraction::Vertex, contraction::Edge > CHDirectedGraph
void graph_add_shortcut(const T_E &edge, std::ostringstream &log)
add edges(shortuct) to the graph during contraction
edge_astar_t * edges
Definition: BDATester.cpp:46
graphType
Definition: pgr_types.h:192
void add_contracted_edge_vertices(V v, T_E &e)
add the contracted vertices of an edge e to the vertex v
size_t size() const
Definition: identifiers.hpp:49
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
void get_changed_vertices(Identifiers< int64_t > &remaining_vertices)
get the vertices of the graph with atleast one contracted vertex
std::deque< T_E > removed_edges
Used for storing the removed_edges.
boost::graph_traits< G >::out_edge_iterator EO_i
void graph_insert_data(const std::vector< T > &edges)
Inserts vector of edges of type T into the graph.
degree_size_type in_degree(V &v) const
True when vid is in the graph.
degree_size_type out_degree_to_vertex(V vertex, V neighbor)
get the out-degree of a vertex to its neighbor
degree_size_type in_degree_from_vertex(V vertex, V neighbor)
get the in-degree of a vertex from its neighbor
boost::graph_traits< G >::in_edge_iterator EI_i
void get_ids(int64_t **contracted_vertices, int &contracted_vertices_size, Identifiers< int64_t > boost_ids)
get the user ids given the boost graph ids in array format
void graph_insert_data(const T *edges, int64_t count)
Inserts count edges of type T into the graph.
E get_min_cost_edge(V source, V destination)
get the edge with minimum cost between two vertices