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_base_graph.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2  *
3 
4 Copyright (c) 2015 Celia Virginia Vergara Castillo
5 vicky_vergara@hotmail.com
6 
7 ------
8 
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13 
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 
23 ********************************************************************PGR-GNU*/
24 
25 #pragma once
26 #if defined(__MinGW32__) || defined(_MSC_VER)
27 #include <winsock2.h>
28 #include <windows.h>
29 #undef min
30 #undef max
31 #ifdef open
32 #undef open
33 #endif
34 #endif
35 
36 
37 
38 #include <boost/graph/iteration_macros.hpp>
39 #include <boost/config.hpp>
40 #include <boost/graph/adjacency_list.hpp>
41 #include <boost/graph/graph_utility.hpp>
42 
43 #include <deque>
44 #include <vector>
45 #include <set>
46 #include <map>
47 #include <limits>
48 
49 #include "./pgr_types.h" // for pgr_edge_t
50 
51 #include "./ch_vertex.h"
52 #include "./ch_edge.h"
53 #include "./basic_vertex.h"
54 #include "./xy_vertex.h"
55 
56 #include "./basic_edge.h"
57 #include "./pgr_assert.h"
58 
219 namespace pgrouting {
220 
221 namespace graph {
222 template <class G, typename Vertex, typename Edge>
224 
225 } // namespace graph
226 
227 
237 typedef graph::Pgr_base_graph <
238 boost::adjacency_list < boost::vecS, boost::vecS,
239  boost::undirectedS,
242 
243 typedef graph::Pgr_base_graph <
244 boost::adjacency_list < boost::vecS, boost::vecS,
245  boost::bidirectionalS,
248 
249 typedef graph::Pgr_base_graph <
250 boost::adjacency_list < boost::listS, boost::vecS,
251  boost::undirectedS,
254 
255 typedef graph::Pgr_base_graph <
256 boost::adjacency_list < boost::listS, boost::vecS,
257  boost::bidirectionalS,
260 
261 #if 0
262 // TODO(Rohith) this is only used on internal query tests
263 typedef graph::Pgr_base_graph <
264 boost::adjacency_list < boost::listS, boost::vecS,
265  boost::undirectedS,
267  contraction::Vertex, Basic_edge > CUndirectedGraph;
268 
269 typedef graph::Pgr_base_graph <
270 boost::adjacency_list < boost::listS, boost::vecS,
271  boost::bidirectionalS,
273  contraction::Vertex, Basic_edge > CDirectedGraph;
274 #endif
275 
276 
277 
278 namespace graph {
279 
280 template <class G, typename T_V, typename T_E>
281 class Pgr_base_graph {
282  public:
295  typedef G B_G;
296  typedef typename boost::graph_traits < G >::vertex_descriptor V;
297  typedef typename boost::graph_traits < G >::edge_descriptor E;
298  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
299  typedef typename boost::graph_traits < G >::edge_iterator E_i;
300  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
301  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
302 
303  typedef typename boost::graph_traits < G >::vertices_size_type
305  typedef typename boost::graph_traits < G >::edges_size_type
307  typedef typename boost::graph_traits < G >::degree_size_type
309 
311 
319 
320  typedef typename std::map< int64_t, V > id_to_V;
321  typedef typename id_to_V::const_iterator LI;
322 
324 
326 
327  G graph;
328  size_t m_num_vertices;
330 
331 
333 
334 
336 
338 
340 
341 
343  std::deque< T_E > removed_edges;
344 
346 
347 
348 
350 
351 
358  const std::vector< T_V > &vertices, graphType gtype)
359  : graph(vertices.size()),
360  m_num_vertices(vertices.size()),
361  m_gType(gtype) {
362  pgassert(boost::num_vertices(graph) == num_vertices());
363  pgassert(boost::num_vertices(graph) == vertices.size());
364 #if 0
365  // This code does not work with contraction
366  pgassert(pgrouting::check_vertices(vertices) == 0);
367 #endif
368  size_t i = 0;
369  for (auto vi = boost::vertices(graph).first;
370  vi != boost::vertices(graph).second; ++vi) {
371  vertices_map[vertices[i].id] = (*vi);
372  graph[(*vi)].cp_members(vertices[i++]);
373  }
374  }
375 
380  : graph(0),
381  m_num_vertices(0),
382  m_gType(gtype) {
383  }
384 
385 
387 
388 
396  template < typename T >
397  void graph_insert_data(const T *edges, int64_t count) {
398  graph_insert_data(std::vector < T >(edges, edges + count));
399  }
418  template < typename T >
419  void graph_insert_data(const std::vector < T > &edges) {
420 #if 0
421  // This code does not work with contraction
422  if (num_vertices() == 0) {
423  auto vertices = pgrouting::extract_vertices(edges);
424  pgassert(pgrouting::check_vertices(vertices) == 0);
425  add_vertices(vertices);
426  }
427 #endif
428  for (const auto edge : edges) {
430  }
431  }
433 
434  private:
451  void add_vertices(std::vector< T_V > vertices);
452 
453  public:
455 
456 
463  degree_size_type out_degree(int64_t vertex_id) const {
464  if (!has_vertex(vertex_id)) {
465  return 0;
466  }
467  return out_degree(get_V(vertex_id));
468  }
469 
470 
478  V get_V(const T_V &vertex) {
479  auto vm_s(vertices_map.find(vertex.id));
480  if (vm_s == vertices_map.end()) {
481  auto v = add_vertex(graph);
482  graph[v].cp_members(vertex);
483  vertices_map[vertex.id] = v;
484  return v;
485  }
486  return vm_s->second;
487  }
488 
495  V get_V(int64_t vid) const {
496  pgassert(has_vertex(vid));
497  return vertices_map.find(vid)->second;
498  }
499 
501  bool has_vertex(int64_t vid) const {
502  return vertices_map.find(vid) != vertices_map.end();
503  }
504 
507  return boost::in_degree(v, graph);
508  }
509 
512  return boost::out_degree(v, graph);
513  }
514 
516 
517 
519 
520 
533  void disconnect_edge(int64_t p_from, int64_t p_to);
534 
535 
537 
546  void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id);
547 
548 
549 
550 
552 
565  void disconnect_vertex(int64_t p_vertex);
566  void disconnect_vertex(V vertex);
567 
568 
570  void restore_graph();
571 
573 
575 
576 
577  friend std::ostream& operator<<(
578  std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g) {
579  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
580 
581  for (auto vi = vertices(g.graph).first;
582  vi != vertices(g.graph).second; ++vi) {
583  if ((*vi) >= g.m_num_vertices) break;
584  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
585  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
586  out != out_end; ++out) {
587  log << ' '
588  << g.graph[*out].id << "=("
589  << g.graph[source(*out, g.graph)].id << ", "
590  << g.graph[target(*out, g.graph)].id << ") = "
591  << g.graph[*out].cost <<"@t";
592  }
593  log << std::endl;
594  }
595  return log;
596  }
597 
599 
600 
601  int64_t get_edge_id(V from, V to, double &distance) const;
602 
603  size_t num_vertices() const { return boost::num_vertices(graph);}
604 
605  T_V operator[](V v) const {
606  return graph[v];
607  }
608 
609 
610  void graph_add_edge(const T_E &edge);
611 
612  template < typename T >
613  void graph_add_edge(const T &edge);
614 };
615 
616 
617 
618 
619 template < class G, typename T_V, typename T_E >
620 void
621 Pgr_base_graph< G, T_V, T_E >::disconnect_edge(int64_t p_from, int64_t p_to) {
622  T_E d_edge;
623 
624  // nothing to do, the vertex doesn't exist
625  if (!has_vertex(p_from) || !has_vertex(p_to)) return;
626 
627  EO_i out, out_end;
628  V g_from(get_V(p_from));
629  V g_to(get_V(p_to));
630 
631  // store the edges that are going to be removed
632  for (boost::tie(out, out_end) = out_edges(g_from, graph);
633  out != out_end; ++out) {
634  if (target(*out, graph) == g_to) {
635  d_edge.id = graph[*out].id;
636  d_edge.source = graph[source(*out, graph)].id;
637  d_edge.target = graph[target(*out, graph)].id;
638  d_edge.cost = graph[*out].cost;
639  removed_edges.push_back(d_edge);
640  }
641  }
642  // the actual removal
643  boost::remove_edge(g_from, g_to, graph);
644 }
645 
646 
647 
648 template < class G, typename T_V, typename T_E >
649 void
651  int64_t vertex_id, int64_t edge_id) {
652  T_E d_edge;
653 
654  // nothing to do, the vertex doesn't exist
655  if (!has_vertex(vertex_id)) return;
656  auto v_from(get_V(vertex_id));
657 
658  EO_i out, out_end;
659  bool change = true;
660  // store the edge that are going to be removed
661  while (change) {
662  change = false;
663  for (boost::tie(out, out_end) = out_edges(v_from, graph);
664  out != out_end; ++out) {
665  if (graph[*out].id == edge_id) {
666  d_edge.id = graph[*out].id;
667  d_edge.source = graph[source(*out, graph)].id;
668  d_edge.target = graph[target(*out, graph)].id;
669  d_edge.cost = graph[*out].cost;
670  removed_edges.push_back(d_edge);
671  boost::remove_edge((*out), graph);
672  change = true;
673  break;
674  }
675  }
676  }
677 }
678 
679 
680 template < class G, typename T_V, typename T_E >
681 void
683  if (!has_vertex(vertex)) return;
684  disconnect_vertex(get_V(vertex));
685 }
686 
687 template < class G, typename T_V, typename T_E >
688 void
690  T_E d_edge;
691 
692  EO_i out, out_end;
693  // store the edges that are going to be removed
694  for (boost::tie(out, out_end) = out_edges(vertex, graph);
695  out != out_end; ++out) {
696  d_edge.id = graph[*out].id;
697  d_edge.source = graph[source(*out, graph)].id;
698  d_edge.target = graph[target(*out, graph)].id;
699  d_edge.cost = graph[*out].cost;
700  removed_edges.push_back(d_edge);
701  }
702 
703  // special case
704  if (m_gType == DIRECTED) {
705  EI_i in, in_end;
706  for (boost::tie(in, in_end) = in_edges(vertex, graph);
707  in != in_end; ++in) {
708  d_edge.id = graph[*in].id;
709  d_edge.source = graph[source(*in, graph)].id;
710  d_edge.target = graph[target(*in, graph)].id;
711  d_edge.cost = graph[*in].cost;
712  removed_edges.push_back(d_edge);
713  }
714  }
715 
716  // delete incoming and outgoing edges from the vertex
717  boost::clear_vertex(vertex, graph);
718 }
719 
720 template < class G, typename T_V, typename T_E >
721 void
723  while (removed_edges.size() != 0) {
724  graph_add_edge(removed_edges[0]);
725  removed_edges.pop_front();
726  }
727 }
728 
729 
730 template < class G, typename T_V, typename T_E >
731 int64_t
733  V from,
734  V to,
735  double &distance) const {
736  E e;
737  EO_i out_i, out_end;
738  V v_source, v_target;
739  double minCost = std::numeric_limits<double>::max();
740  int64_t minEdge = -1;
741  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
742  out_i != out_end; ++out_i) {
743  e = *out_i;
744  v_target = target(e, graph);
745  v_source = source(e, graph);
746  if ((from == v_source) && (to == v_target)
747  && (distance == graph[e].cost))
748  return graph[e].id;
749  if ((from == v_source) && (to == v_target)
750  && (minCost > graph[e].cost)) {
751  minCost = graph[e].cost;
752  minEdge = graph[e].id;
753  }
754  }
755  distance = minEdge == -1? 0: minCost;
756  return minEdge;
757 }
758 
759 
760 template < class G, typename T_V, typename T_E >
761 void
763  bool inserted;
764  typename Pgr_base_graph< G, T_V, T_E >::LI vm_s, vm_t;
766 
767  vm_s = vertices_map.find(edge.source);
768  if (vm_s == vertices_map.end()) {
769  vertices_map[edge.source]= m_num_vertices;
770  vm_s = vertices_map.find(edge.source);
771  }
772 
773  vm_t = vertices_map.find(edge.target);
774  if (vm_t == vertices_map.end()) {
775  vertices_map[edge.target]= m_num_vertices;
776  vm_t = vertices_map.find(edge.target);
777  }
778 
779  if (edge.cost >= 0) {
780  boost::tie(e, inserted) =
781  boost::add_edge(vm_s->second, vm_t->second, graph);
782  graph[e].cp_members(edge);
783  }
784 }
785 
786 
787 template < class G, typename T_V, typename T_E >
788 template < typename T>
789 void
791  bool inserted;
793  if ((edge.cost < 0) && (edge.reverse_cost < 0))
794  return;
795 
796  /*
797  * true: for source
798  * false: for target
799  */
800  auto vm_s = get_V(T_V(edge, true));
801  auto vm_t = get_V(T_V(edge, false));
802 
803  pgassert(vertices_map.find(edge.source) != vertices_map.end());
804  pgassert(vertices_map.find(edge.target) != vertices_map.end());
805  if (edge.cost >= 0) {
806  boost::tie(e, inserted) =
807  boost::add_edge(vm_s, vm_t, graph);
808  graph[e].cost = edge.cost;
809  graph[e].id = edge.id;
810  graph[e].first = true;
811  }
812 
813  if (edge.reverse_cost >= 0) {
814  boost::tie(e, inserted) =
815  boost::add_edge(vm_t, vm_s, graph);
816 
817  graph[e].cost = edge.reverse_cost;
818  graph[e].id = edge.id;
819  graph[e].first = false;
820  }
821 }
822 
823 /****************** PRIVATE *******************/
824 
825 template < class G, typename T_V, typename T_E >
826 void
828  std::vector< T_V > vertices) {
829  pgassert(m_num_vertices == 0);
830  for (const auto vertex : vertices) {
831  pgassert(vertices_map.find(vertex.id) == vertices_map.end());
832 
833  auto v = add_vertex(graph);
834  vertices_map[vertex.id] = m_num_vertices++;
835  graph[v].cp_members(vertex);
836 
837  pgassert(boost::num_vertices(graph) == num_vertices());
838  }
839  return;
840 }
841 
842 } // namespace graph
843 } // namespace pgrouting
void graph_insert_data(const std::vector< T > &edges)
Inserts count edges of type pgr_edge_t into the graph.
boost::graph_traits< G >::edges_size_type edges_size_type
boost::graph_traits< G >::edge_descriptor E
void disconnect_vertex(int64_t p_vertex)
Disconnects all incoming and outgoing edges from the vertex.
void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id)
Disconnects the outgoing edges of a vertex.
graphType m_gType
type (DIRECTED or UNDIRECTED)
int64_t get_edge_id(V from, V to, double &distance) const
bool has_vertex(int64_t vid) const
True when vid is in the graph.
std::map< int64_t, V > id_to_V
boost::graph_traits< G >::vertex_descriptor V
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
boost::graph_traits< G >::out_edge_iterator EO_i
boost::graph_traits< G >::vertices_size_type vertices_size_type
V get_V(int64_t vid) const
get the vertex descriptor of the vid
graph::Pgr_base_graph< boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, Basic_vertex, Basic_edge >, Basic_vertex, Basic_edge > DirectedGraph
void graph_add_edge(const T_E &edge)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
boost::graph_traits< G >::vertex_iterator V_i
edge_astar_t * edges
Definition: BDATester.cpp:46
boost::graph_traits< G >::edge_iterator E_i
graphType
Definition: pgr_types.h:192
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
friend std::ostream & operator<<(std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g)
id_to_V vertices_map
id -> graph id
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
void disconnect_edge(int64_t p_from, int64_t p_to)
Disconnects all edges from p_from to p_to.
void add_vertices(std::vector< T_V > vertices)
adds the vertices into the graph
Assertions Handling.
graph::Pgr_base_graph< boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Basic_vertex, Basic_edge >, Basic_vertex, Basic_edge > UndirectedGraph
std::deque< T_E > removed_edges
Used for storing the removed_edges.
boost::graph_traits< G >::degree_size_type degree_size_type
graph::Pgr_base_graph< boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, XY_vertex, Basic_edge >, XY_vertex, Basic_edge > xyDirectedGraph
degree_size_type in_degree(V &v) const
True when vid is in the graph.
void restore_graph()
Reconnects all edges that were removed.
size_t check_vertices(std::vector< Basic_vertex > vertices)
graph::Pgr_base_graph< boost::adjacency_list< boost::listS, boost::vecS, boost::undirectedS, XY_vertex, Basic_edge >, XY_vertex, Basic_edge > xyUndirectedGraph
degree_size_type out_degree(V &v) const
True when vid is in the graph.
boost::graph_traits< G >::in_edge_iterator EI_i
void graph_insert_data(const T *edges, int64_t count)
Inserts count edges of type T into the graph.