PGROUTING  2.5
 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 
40 #include "../../common/src/ch_vertex.h"
41 #include "../../common/src/ch_edge.h"
42 
43 
44 namespace pgrouting {
45 
46 namespace graph {
47 template <class G, typename T_V, typename T_E>
49 }
50 
52  boost::adjacency_list < boost::listS, boost::vecS,
53  boost::undirectedS,
54  CH_vertex, CH_edge >,
56 
58  boost::adjacency_list < boost::listS, boost::vecS,
59  boost::bidirectionalS,
60  CH_vertex, CH_edge >,
62 
63 namespace graph {
64 
65 template <class G, typename T_V, typename T_E>
66 class Pgr_contractionGraph : public Pgr_base_graph<G, T_V, T_E> {
67  public:
68  typedef typename boost::graph_traits < G >::vertex_descriptor V;
69  typedef typename boost::graph_traits < G >::edge_descriptor E;
70  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
71  typedef typename boost::graph_traits < G >::edge_iterator E_i;
72  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
73  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
74  typedef typename boost::graph_traits < G >::degree_size_type
76 
78  std::vector<T_E> shortcuts;
79 
83  static bool compareById(const T_E &edge1, const T_E &edge2) {
84  return edge1.id > edge2.id;
85  }
86 
92  }
93 
99  EO_i out, out_end;
100  EI_i in, in_end;
101  Identifiers<V> adjacent_vertices;
102 
103  for (boost::tie(out, out_end) = out_edges(v, this->graph);
104  out != out_end; ++out) {
105  adjacent_vertices += this->adjacent(v, *out);
106  }
107  for (boost::tie(in, in_end) = in_edges(v, this->graph);
108  in != in_end; ++in) {
109  adjacent_vertices += this->adjacent(v, *in);
110  }
111  return adjacent_vertices;
112  }
113 
114 
115  std::vector<int64_t> get_ids(
116  Identifiers<int64_t> boost_ids) const {
117  std::vector<int64_t> ids(boost_ids.size());
118  size_t count = 0;
119  for (auto id : boost_ids) {
120  ids[count++] = this->graph[id].id;
121  }
122  return ids;
123  }
124 
125 
132  for (auto vi = vertices(this->graph).first;
133  vi != vertices(this->graph).second;
134  ++vi) {
135  if (!removed_vertices.has(*vi)
136  && this->graph[*vi].has_contracted_vertices()) {
137  vids += this->graph[*vi].id;
138  }
139  }
140  return vids;
141  }
142 
143 
149  E get_min_cost_edge(V source, V destination) {
150  EO_i out_i, out_end;
151  E min_cost_edge;
152  double min_cost = (std::numeric_limits<double>::max)();
153  for (boost::tie(out_i, out_end) =
154  boost::out_edges(source, this->graph);
155  out_i != out_end; ++out_i) {
156  auto e = *out_i;
157  if (this->target(e) == destination) {
158  if (this->graph[e].cost < min_cost) {
159  min_cost = this->graph[e].cost;
160  min_cost_edge = e;
161  }
162  }
163  }
164  return min_cost_edge;
165  }
166 
174  return out_degree_to_vertex(neighbor, vertex);
175  }
176 
184  degree_size_type degree = 0;
185  EO_i out_i, out_end;
186  for (boost::tie(out_i, out_end) =
187  boost::out_edges(vertex, this->graph);
188  out_i != out_end; ++out_i) {
189  if (this->is_directed()
190  && (this->is_source(vertex, *out_i)
191  && this->is_target(neighbor, *out_i))) {
192  degree++;
193  } else if (this->is_undirected() &&
194  this->adjacent(vertex, *out_i) == neighbor) {
195  degree++;
196  }
197  }
198  return degree;
199  }
200 
201 
205  void print_graph(std::ostringstream &log) {
206  EO_i out, out_end;
207  for (auto vi = vertices(this->graph).first;
208  vi != vertices(this->graph).second;
209  ++vi) {
210  if ((*vi) >= this->m_num_vertices) break;
211  log << this->graph[*vi].id << "(" << (*vi) << ")"
212  << this->graph[*vi].contracted_vertices() << std::endl;
213  log << " out_edges_of(" << this->graph[*vi].id << "):";
214  for (boost::tie(out, out_end) = out_edges(*vi, this->graph);
215  out != out_end; ++out) {
216  log << ' ' << this->graph[*out].id
217  << "=(" << this->graph[this->source(*out)].id
218  << ", " << this->graph[this->target(*out)].id << ") = "
219  << this->graph[*out].cost <<"\t";
220  }
221  log << std::endl;
222  }
223  }
224 
225 
226 
232  std::vector<int64_t> get_contracted_vertices(int64_t vid) {
233  if (!this->has_vertex(vid)) return std::vector<int64_t>();
234  auto v = this->get_V(vid);
235  std::vector<int64_t> ids(this->graph[v].contracted_vertices().size());
236 
237  size_t count = 0;
238  for (auto idx : this->graph[v].contracted_vertices()) {
239  ids[count++] = this->graph[idx].id;
240  }
241  return ids;
242  }
243 
244 
245 
246 
247 
252  void add_contracted_edge_vertices(V v, T_E &e) {
253  for (auto vid : e.contracted_vertices()) {
254  this->graph[v].add_vertex_id(vid);
255  }
256  e.clear_contracted_vertices();
257  }
258 
259 
275  void add_shortcut(const T_E &edge) {
276  std::ostringstream log;
277  bool inserted;
278  E e;
279  if (edge.cost < 0)
280  return;
281 
282  pgassert(this->vertices_map.find(edge.source)
283  != this->vertices_map.end());
284  pgassert(this->vertices_map.find(edge.target)
285  != this->vertices_map.end());
286 
287  auto vm_s = this->get_V(edge.source);
288  auto vm_t = this->get_V(edge.target);
289 
290  boost::tie(e, inserted) =
291  boost::add_edge(vm_s, vm_t, this->graph);
292 
293  this->graph[e].cp_members(edge);
294 
295  shortcuts.push_back(edge);
296  }
297 };
298 
299 } // namespace graph
300 } // namespace pgrouting
301 
302 #endif // SRC_CONTRACTION_SRC_PGR_CONTRACTIONGRAPH_HPP_
bool has(const T other) const
true ids() has element
Definition: identifiers.hpp:97
Identifiers< V > find_adjacent_vertices(V v) const
get the vertex descriptors of adjacent vertices of v
Definition: trsp.h:31
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
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:77
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
graphType
Definition: graph_enum.h:30
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