PGROUTING  2.4
 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 #ifndef SRC_CONTRACTION_SRC_PGR_CONTRACTIONGRAPH_HPP_
31 #define SRC_CONTRACTION_SRC_PGR_CONTRACTIONGRAPH_HPP_
32 #pragma once
33 
34 
35 #include <limits>
36 #include <algorithm>
37 #include <vector>
38 
39 #include "../../common/src/pgr_base_graph.hpp"
40 
41 
42 namespace pgrouting {
43 
44 namespace graph {
45 template <class G, typename T_V, typename T_E>
47 }
48 
50  boost::adjacency_list < boost::listS, boost::vecS,
51  boost::undirectedS,
52  CH_vertex, CH_edge >,
54 
56  boost::adjacency_list < boost::listS, boost::vecS,
57  boost::bidirectionalS,
58  CH_vertex, CH_edge >,
60 
61 namespace graph {
62 
63 template <class G, typename T_V, typename T_E>
64 class Pgr_contractionGraph : public Pgr_base_graph<G, T_V, T_E> {
65  public:
66  typedef typename boost::graph_traits < G >::vertex_descriptor V;
67  typedef typename boost::graph_traits < G >::edge_descriptor E;
68  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
69  typedef typename boost::graph_traits < G >::edge_iterator E_i;
70  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
71  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
72  typedef typename boost::graph_traits < G >::degree_size_type
74 
76  std::vector<T_E> shortcuts;
77 
81  static bool compareById(const T_E &edge1, const T_E &edge2) {
82  return edge1.id > edge2.id;
83  }
84 
90  }
91 
97  EO_i out, out_end;
98  EI_i in, in_end;
99  Identifiers<V> adjacent_vertices;
100 
101  for (boost::tie(out, out_end) = out_edges(v, this->graph);
102  out != out_end; ++out) {
103  adjacent_vertices += this->adjacent(v, *out);
104  }
105  for (boost::tie(in, in_end) = in_edges(v, this->graph);
106  in != in_end; ++in) {
107  adjacent_vertices += this->adjacent(v, *in);
108  }
109  return adjacent_vertices;
110  }
111 
112 
113  std::vector<int64_t> get_ids(
114  Identifiers<int64_t> boost_ids) const {
115  std::vector<int64_t> ids(boost_ids.size());
116  size_t count = 0;
117  for (auto id : boost_ids) {
118  ids[count++] = this->graph[id].id;
119  }
120  return ids;
121  }
122 
123 
130  for (auto vi = vertices(this->graph).first;
131  vi != vertices(this->graph).second;
132  ++vi) {
133  if (!removed_vertices.has(*vi)
134  && this->graph[*vi].has_contracted_vertices()) {
135  vids += this->graph[*vi].id;
136  }
137  }
138  return vids;
139  }
140 
141 
147  E get_min_cost_edge(V source, V destination) {
148  EO_i out_i, out_end;
149  E min_cost_edge;
150  double min_cost = (std::numeric_limits<double>::max)();
151  for (boost::tie(out_i, out_end) =
152  boost::out_edges(source, this->graph);
153  out_i != out_end; ++out_i) {
154  auto e = *out_i;
155  if (this->target(e) == destination) {
156  if (this->graph[e].cost < min_cost) {
157  min_cost = this->graph[e].cost;
158  min_cost_edge = e;
159  }
160  }
161  }
162  return min_cost_edge;
163  }
164 
172  return out_degree_to_vertex(neighbor, vertex);
173  }
174 
182  degree_size_type degree = 0;
183  EO_i out_i, out_end;
184  for (boost::tie(out_i, out_end) =
185  boost::out_edges(vertex, this->graph);
186  out_i != out_end; ++out_i) {
187  if (this->is_directed()
188  && (this->is_source(vertex, *out_i)
189  && this->is_target(neighbor, *out_i))) {
190  degree++;
191  } else if (this->is_undirected() &&
192  this->adjacent(vertex, *out_i) == neighbor) {
193  degree++;
194  }
195  }
196  return degree;
197  }
198 
199 
203  void print_graph(std::ostringstream &log) {
204  EO_i out, out_end;
205  for (auto vi = vertices(this->graph).first;
206  vi != vertices(this->graph).second;
207  ++vi) {
208  if ((*vi) >= this->m_num_vertices) break;
209  log << this->graph[*vi].id << "(" << (*vi) << ")"
210  << this->graph[*vi].contracted_vertices() << std::endl;
211  log << " out_edges_of(" << this->graph[*vi].id << "):";
212  for (boost::tie(out, out_end) = out_edges(*vi, this->graph);
213  out != out_end; ++out) {
214  log << ' ' << this->graph[*out].id
215  << "=(" << this->graph[this->source(*out)].id
216  << ", " << this->graph[this->target(*out)].id << ") = "
217  << this->graph[*out].cost <<"\t";
218  }
219  log << std::endl;
220  }
221  }
222 
223 
224 
230  std::vector<int64_t> get_contracted_vertices(int64_t vid) {
231  if (!this->has_vertex(vid)) return std::vector<int64_t>();
232  auto v = this->get_V(vid);
233  std::vector<int64_t> ids(this->graph[v].contracted_vertices().size());
234 
235  size_t count = 0;
236  for (auto idx : this->graph[v].contracted_vertices()) {
237  ids[count++] = this->graph[idx].id;
238  }
239  return ids;
240  }
241 
242 
243 
244 
245 
250  void add_contracted_edge_vertices(V v, T_E &e) {
251  for (auto vid : e.contracted_vertices()) {
252  this->graph[v].add_vertex_id(vid);
253  }
254  e.clear_contracted_vertices();
255  }
256 
257 
273  void add_shortcut(const T_E &edge) {
274  std::ostringstream log;
275  bool inserted;
276  E e;
277  if (edge.cost < 0)
278  return;
279 
280  pgassert(this->vertices_map.find(edge.source)
281  != this->vertices_map.end());
282  pgassert(this->vertices_map.find(edge.target)
283  != this->vertices_map.end());
284 
285  auto vm_s = this->get_V(edge.source);
286  auto vm_t = this->get_V(edge.target);
287 
288  boost::tie(e, inserted) =
289  boost::add_edge(vm_s, vm_t, this->graph);
290 
291  this->graph[e].cp_members(edge);
292 
293  shortcuts.push_back(edge);
294  }
295 };
296 
297 } // namespace graph
298 } // namespace pgrouting
299 
300 #endif // SRC_CONTRACTION_SRC_PGR_CONTRACTIONGRAPH_HPP_
Identifiers< V > find_adjacent_vertices(V v) const
get the vertex descriptors of adjacent vertices of v
bool has(const T element) const
Returns a boolean value true or false.
void print_graph(std::ostringstream &log)
print the graph with contracted vertices of all vertices and edges
Identifiers< int64_t > get_changed_vertices()
vertices with at least one contracted vertex
boost::graph_traits< G >::edge_iterator E_i
std::vector< int64_t > get_contracted_vertices(int64_t vid)
get the contracted vertex ids of a given vertex in array format
boost::graph_traits< G >::vertex_iterator V_i
boost::graph_traits< G >::edge_descriptor E
boost::graph_traits< G >::vertex_descriptor V
bool has_vertex(int64_t vid) const
True when vid is in the graph.
boost::graph_traits< G >::degree_size_type degree_size_type
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 add_shortcut(const T_E &edge)
add edges(shortuct) to the graph during contraction
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
graphType
Definition: pgr_types.h:222
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:56
graph::Pgr_contractionGraph< boost::adjacency_list< boost::listS, boost::vecS, boost::undirectedS, CH_vertex, CH_edge >, CH_vertex, CH_edge > CHUndirectedGraph
boost::graph_traits< G >::out_edge_iterator EO_i
graph::Pgr_contractionGraph< boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, CH_vertex, CH_edge >, CH_vertex, CH_edge > CHDirectedGraph
std::vector< int64_t > get_ids(Identifiers< int64_t > boost_ids) const
degree_size_type out_degree_to_vertex(V vertex, V neighbor)
The number of edges from vertex to neighbor.
degree_size_type in_degree_from_vertex(V vertex, V neighbor)
The number of edges from neighbor to vertex.
boost::graph_traits< G >::in_edge_iterator EI_i
E get_min_cost_edge(V source, V destination)
get the edge with minimum cost between two vertices