pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
baseGraph.hpp
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 Celia Virginia Vergara Castillo
4 vicky_vergara@hotmail.com
5 
6 ------
7 
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12 
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 
22 ********************************************************************PGR-GNU*/
23 
24 #ifndef SRC_COMMON_SRC_BASE_GRAPH_HPP_
25 #define SRC_COMMON_SRC_BASE_GRAPH_HPP_
26 
27 #include <boost/config.hpp>
28 #include <boost/graph/adjacency_list.hpp>
29 #include <boost/graph/graph_utility.hpp>
30 
31 #include <deque>
32 #include <vector>
33 #include <set>
34 #include <map>
35 #include <limits>
36 
37 #include "./pgr_types.h"
38 
83 typedef typename boost::adjacency_list < boost::vecS, boost::vecS,
84  boost::undirectedS,
85  boost_vertex_t, boost_edge_t > UndirectedGraph;
86 
87 typedef typename boost::adjacency_list < boost::vecS, boost::vecS,
88  boost::bidirectionalS,
89  boost_vertex_t, boost_edge_t > DirectedGraph;
90 
91 
92 template <class G>
94  public:
107  typedef typename boost::graph_traits < G >::vertex_descriptor V;
108  typedef typename boost::graph_traits < G >::edge_descriptor E;
109  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
110  typedef typename boost::graph_traits < G >::edge_iterator E_i;
111  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
112  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
113 
114  typedef typename boost::graph_traits < G >::vertices_size_type vertices_size_type;
115  typedef typename boost::graph_traits < G >::edges_size_type edges_size_type;
116  typedef typename boost::graph_traits < G >::degree_size_type degree_size_type;
117 
119 
129  typedef typename std::map< int64_t, V > id_to_V;
130  typedef typename std::map< V, int64_t > V_to_id;
131  typedef typename id_to_V::const_iterator LI;
132  typedef typename V_to_id::const_iterator RI;
134 
136 
137  G graph;
138  size_t m_num_vertices;
139  graphType m_gType;
140 
141 
143 
144  id_to_V vertices_map;
145  V_to_id gVertices_map;
146 
147 
149 
150  std::deque<boost_edge_t> removed_edges;
152 
154  // TODO
155 #if 0
156  std::deque<boost_edge_t> modified_edges;
157  std::deque< Point_on_edge > points;
158  // map to get wich boost edge was modified
159  std::map < int64_t, int64_t >;
160 #endif
161 
162 
163 #if 0
164  void add_point(Point_on_edge &point, int driving) {
165  // we have:
166  // point.point_id
167  // point.edge_id
168  // point.fraction
169  // Look for the edge in modified edges
170  //
171  // Driving: 0: doesnt matter (both), 1) right, 2) left
172  bool found = false;
173  int64_t edge_to_modify = 0;
174  for (const auto &edge : modified_edges) {
175  if (point.edge_id == edge.id) {
176  found = true;
177  break;
178  }
179  ++edge_to_modify;
180  }
181 
182  //was not there so look for it in the graph
183  if (!found) {
184  E_i edge_ptr, edges_end;
185  for (boost::tie(edge_ptr, edges_end) = edges(graph);
186  edge_ptr != edges_end; ++edge_ptr) {
187  if (point.edge_id == edge_ptr->id) {
188  modified_edges.push_back(*edge_ptr);
189  boost::remove_edge(edge_ptr, graph);
190  //delete the edge from the graph
191  found = true;
192  break;
193  }
194  }
195  }
196 
197  // add the point
198  int64_t vertex_id = -(points.size() + 1);
199  point.vertex_id = vertex_id;
200  points.push_back(point);
201 
202  // add the vertex
203  LI vm_s;
204  vm_s = vertices_map.find(vertex_id);
205  if (vm_s == vertices_map.end()) {
206  vertices_map[vertex_id]= m_num_vertices;
207  gVertices_map[m_num_vertices++] = vertex_id;
208  vm_s = vertices_map.find(vertex_id);
209  }
210 
211  if (!found) {
212  // the vertex remains disconnected
213  // because the edge was not found
214  return;
215  }
216 
217  }
218 #endif
219 
220 
221 
222 
223 
225 
226 
231  explicit Pgr_base_graph< G >(graphType gtype, const size_t initial_size)
232  : graph(1),
233  m_num_vertices(0),
234  m_gType(gtype)
235  {}
236 
238  void graph_insert_data(const pgr_edge_t *data_edges, int64_t count) {
239  for (unsigned int i = 0; i < count; ++i) {
240  graph_add_edge(data_edges[i]);
241  }
242  adjust_vertices();
243  for ( int64_t i = 0; (unsigned int) i < gVertices_map.size(); ++i )
244  graph[i].id = gVertices_map.find(i)->second;
245  }
246 
247  void graph_insert_data( const std::vector <pgr_edge_t > &data_edges) {
248  for (const auto edge : data_edges) {
249  graph_add_edge(edge);
250  }
251  adjust_vertices();
252  for ( int64_t i = 0; (unsigned int) i < gVertices_map.size(); ++i )
253  graph[i].id = gVertices_map.find(i)->second;
254  }
255 
257 
268  void disconnect_edge(int64_t p_from, int64_t p_to) {
269  V g_from;
270  V g_to;
271  boost_edge_t d_edge;
272  // nothing to do, the vertex doesnt exist
273  if (!get_gVertex(p_from, g_from)) return;
274  if (!get_gVertex(p_to, g_to)) return;
275  EO_i out, out_end;
276  // store the edges that are going to be removed
277  for (boost::tie(out, out_end) = out_edges(g_from, graph);
278  out != out_end; ++out) {
279  if (target(*out, graph) == g_to) {
280  d_edge.id = graph[*out].id;
281  d_edge.source = graph[source(*out, graph)].id;
282  d_edge.target = graph[target(*out, graph)].id;
283  d_edge.cost = graph[*out].cost;
284  // d_edge.reverse_cost = -1;
285  removed_edges.push_back(d_edge);
286  }
287  }
288  // the actual removal
289  boost::remove_edge(g_from, g_to, graph);
290  }
291 
292 
294 
295 
303  degree_size_type out_degree(int64_t vertex_id) const{
304  V v_from;
305  if (!get_gVertex(vertex_id, v_from)) {
306  return 0;
307  }
308  return out_degree(v_from);
309  }
310 
311  degree_size_type out_degree(V &v) const {
312  return boost::out_degree(v, graph);
313  }
315 
316 
318 
326  void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id) {
327  V v_from;
328  boost_edge_t d_edge;
329 
330  // nothing to do, the vertex doesnt exist
331  if (!get_gVertex(vertex_id, v_from)) {
332  return;
333  }
334 
335  EO_i out, out_end;
336  bool change = true;
337  // store the edge that are going to be removed
338  while (change) {
339  change = false;
340  for (boost::tie(out, out_end) = out_edges(v_from, graph);
341  out != out_end; ++out) {
342  if (graph[*out].id == edge_id) {
343  d_edge.id = graph[*out].id;
344  d_edge.source = graph[source(*out, graph)].id;
345  d_edge.target = graph[target(*out, graph)].id;
346  d_edge.cost = graph[*out].cost;
347  // d_edge.reverse_cost = -1;
348  removed_edges.push_back(d_edge);
349  boost::remove_edge((*out), graph);
350  change = true;
351  break;
352  }
353  }
354  }
355 
356  }
357 
358 
360 
373  void disconnect_vertex(int64_t p_vertex) {
374  V g_vertex;
375  boost_edge_t d_edge;
376  // nothing to do, the vertex doesnt exist
377  if (!get_gVertex(p_vertex, g_vertex)) return;
378  EO_i out, out_end;
379  // store the edges that are going to be removed
380  for (boost::tie(out, out_end) = out_edges(g_vertex, graph);
381  out != out_end; ++out) {
382  d_edge.id = graph[*out].id;
383  d_edge.source = graph[source(*out, graph)].id;
384  d_edge.target = graph[target(*out, graph)].id;
385  d_edge.cost = graph[*out].cost;
386  // d_edge.reverse_cost = -1;
387  removed_edges.push_back(d_edge);
388  }
389 
390  // special case
391  if (m_gType == DIRECTED) {
392  EI_i in, in_end;
393  for (boost::tie(in, in_end) = in_edges(g_vertex, graph);
394  in != in_end; ++in) {
395  d_edge.id = graph[*in].id;
396  d_edge.source = graph[source(*in, graph)].id;
397  d_edge.target = graph[target(*in, graph)].id;
398  d_edge.cost = graph[*in].cost;
399  // d_edge.reverse_cost = -1;
400  removed_edges.push_back(d_edge);
401  }
402  }
403 
404  V d_vertex = boost::vertex(vertices_map.find(p_vertex)->second, graph);
405  // delete incomming and outgoing edges from the vertex
406  boost::clear_vertex(d_vertex, graph);
407  }
408 
410  void restore_graph() {
411  while (removed_edges.size() != 0) {
412  graph_add_edge(removed_edges[0]);
413  removed_edges.pop_front();
414  }
415  }
417 
419 
420  void print_graph(std::ostream &log = std::cout) const {
421  EO_i out, out_end;
422  V_i vi;
423 
424  for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi) {
425  if ((*vi) >= m_num_vertices) continue;
426  log << (*vi) << " out_edges(" << graph[(*vi)].id << "):";
427  for (boost::tie(out, out_end) = out_edges(*vi, graph);
428  out != out_end; ++out) {
429  log << ' ' << graph[*out].id << "=(" << graph[source(*out, graph)].id
430  << ", " << graph[target(*out, graph)].id << ") = "
431  << graph[*out].cost <<"\t";
432  }
433  log << std::endl;
434  }
435  }
437 
438 
439  bool get_gVertex(int64_t vertex_id, V &gVertex) const {
440  LI vertex_ptr = vertices_map.find(vertex_id);
441 
442  if (vertex_ptr == vertices_map.end())
443  return false;
444 
445  gVertex = vertex(vertex_ptr->second, graph);
446  return true;
447  }
448 
449  public:
450  int64_t
451  get_edge_id(V from, V to, float8 &distance) const {
452  E e;
453  EO_i out_i, out_end;
454  V v_source, v_target;
455  float8 minCost = std::numeric_limits<float8>::max();
456  int64_t minEdge = -1;
457  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
458  out_i != out_end; ++out_i) {
459  e = *out_i;
460  v_target = target(e, graph);
461  v_source = source(e, graph);
462  if ((from == v_source) && (to == v_target)
463  && (distance == graph[e].cost))
464  return graph[e].id;
465  if ((from == v_source) && (to == v_target)
466  && (minCost > graph[e].cost)) {
467  minCost = graph[e].cost;
468  minEdge = graph[e].id;
469  }
470  }
471  distance = minEdge == -1? 0: minCost;
472  return minEdge;
473  }
474 
475  public:
476  size_t num_vertices() const { return m_num_vertices; }
477  void
478  adjust_vertices() {
479  while (boost::num_vertices(graph) != num_vertices()) {
480  if (boost::num_vertices(graph) > num_vertices()) {
481  boost::remove_vertex(boost::num_vertices(graph), graph);
482  }
483  }
484  }
485 
486 
487  boost_vertex_t operator[](V v) const {
488  return graph[v];
489  }
490 
491  private:
492 
493 
494  void
495  graph_add_edge(const boost_edge_t &edge ) {
496  bool inserted;
497  LI vm_s, vm_t;
498  E e;
499 
500  vm_s = vertices_map.find(edge.source);
501  if (vm_s == vertices_map.end()) {
502  vertices_map[edge.source]= m_num_vertices;
503  gVertices_map[m_num_vertices++] = edge.source;
504  vm_s = vertices_map.find(edge.source);
505  }
506 
507  vm_t = vertices_map.find(edge.target);
508  if (vm_t == vertices_map.end()) {
509  vertices_map[edge.target]= m_num_vertices;
510  gVertices_map[m_num_vertices++] = edge.target;
511  vm_t = vertices_map.find(edge.target);
512  }
513 
514  if (edge.cost >= 0) {
515  boost::tie(e, inserted) =
516  boost::add_edge(vm_s->second, vm_t->second, graph);
517  graph[e].cost = edge.cost;
518  graph[e].id = edge.id;
519  graph[e].first = edge.first;
520  }
521  }
522 
523  void
524  graph_add_edge(const pgr_edge_t &edge ) {
525  bool inserted;
526  LI vm_s, vm_t;
527  E e;
528  if ((edge.cost < 0) && (edge.reverse_cost < 0))
529  return;
530 
531  vm_s = vertices_map.find(edge.source);
532  if (vm_s == vertices_map.end()) {
533  vertices_map[edge.source]= m_num_vertices;
534  gVertices_map[m_num_vertices++] = edge.source;
535  vm_s = vertices_map.find(edge.source);
536  }
537 
538  vm_t = vertices_map.find(edge.target);
539  if (vm_t == vertices_map.end()) {
540  vertices_map[edge.target]= m_num_vertices;
541  gVertices_map[m_num_vertices++] = edge.target;
542  vm_t = vertices_map.find(edge.target);
543  }
544 
545  if (edge.cost >= 0) {
546  boost::tie(e, inserted) =
547  boost::add_edge(vm_s->second, vm_t->second, graph);
548  graph[e].cost = edge.cost;
549  graph[e].id = edge.id;
550  graph[e].first = true;
551  }
552 
553  if (edge.reverse_cost >= 0) {
554  boost::tie(e, inserted) =
555  boost::add_edge(vm_t->second, vm_s->second, graph);
556  graph[e].cost = edge.reverse_cost;
557  graph[e].id = edge.id;
558  graph[e].first = false;
559  }
560  }
561 };
562 
563 
564 #endif // SRC_COMMON_SRC_BASE_GRAPH_HPP_
Definition: alpha.h:33
size_t m_num_vertices
number of vertices
Definition: baseGraph.hpp:138
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
Definition: baseGraph.hpp:303
void restore_graph()
Reconnects all edges that were removed.
Definition: baseGraph.hpp:410
void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id)
Disconnects the outgoing edges with a particular original id from a vertex.
Definition: baseGraph.hpp:326
G graph
The graph.
Definition: baseGraph.hpp:137
void disconnect_edge(int64_t p_from, int64_t p_to)
Disconnects all edges from p_from to p_to.
Definition: baseGraph.hpp:268
Definition: tsp.h:34
graphType m_gType
type (DIRECTED or UNDIRECTED)
Definition: baseGraph.hpp:139
void graph_insert_data(const pgr_edge_t *data_edges, int64_t count)
Inserts count edges of type pgr_edge_t into the graph.
Definition: baseGraph.hpp:238
id_to_V vertices_map
id -> graph id
Definition: baseGraph.hpp:144
std::deque< boost_edge_t > removed_edges
Used for storing the removed_edges.
Definition: baseGraph.hpp:151
void disconnect_vertex(int64_t p_vertex)
Disconnects all incomming and outgoing edges from the vertex.
Definition: baseGraph.hpp:373
V_to_id gVertices_map
graph id -> id
Definition: baseGraph.hpp:145