PGROUTING  2.6-dev
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 
27 #ifndef INCLUDE_CPP_COMMON_PGR_BASE_GRAPH_HPP_
28 #define INCLUDE_CPP_COMMON_PGR_BASE_GRAPH_HPP_
29 #pragma once
30 
31 #include <boost/graph/iteration_macros.hpp>
32 #include <boost/config.hpp>
33 #include <boost/graph/adjacency_list.hpp>
34 #include <boost/graph/graph_utility.hpp>
35 
36 #include <deque>
37 #include <vector>
38 #include <set>
39 #include <map>
40 #include <limits>
41 
42 #include "c_types/graph_enum.h"
43 
45 #include "cpp_common/xy_vertex.h"
46 #include "cpp_common/basic_edge.h"
47 
48 #include "cpp_common/pgr_assert.h"
49 
50 namespace pgrouting {
51 
213 namespace graph {
214 template <class G, typename Vertex, typename Edge>
216 
217 } // namespace graph
218 
219 
229 typedef graph::Pgr_base_graph <
230 boost::adjacency_list < boost::vecS, boost::vecS,
231  boost::undirectedS,
233  Basic_vertex, Basic_edge > UndirectedGraph;
234 
235 typedef graph::Pgr_base_graph <
236 boost::adjacency_list < boost::vecS, boost::vecS,
237  boost::bidirectionalS,
238  Basic_vertex, Basic_edge >,
239  Basic_vertex, Basic_edge > DirectedGraph;
240 
241 typedef graph::Pgr_base_graph <
242 boost::adjacency_list < boost::listS, boost::vecS,
243  boost::undirectedS,
244  XY_vertex, Basic_edge >,
245  XY_vertex, Basic_edge > xyUndirectedGraph;
246 
247 typedef graph::Pgr_base_graph <
248 boost::adjacency_list < boost::listS, boost::vecS,
249  boost::bidirectionalS,
250  XY_vertex, Basic_edge >,
251  XY_vertex, Basic_edge > xyDirectedGraph;
252 
254 
255 
256 namespace graph {
257 
258 template <class G, typename T_V, typename T_E>
259 class Pgr_base_graph {
260  public:
273  typedef G B_G;
274  typedef T_E G_T_E;
275  typedef T_V G_T_V;
276  typedef typename boost::graph_traits < G >::vertex_descriptor V;
277  typedef typename boost::graph_traits < G >::edge_descriptor E;
278  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
279  typedef typename boost::graph_traits < G >::edge_iterator E_i;
280  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
281  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
282 
283  typedef typename boost::graph_traits < G >::vertices_size_type
285  typedef typename boost::graph_traits < G >::edges_size_type
287  typedef typename boost::graph_traits < G >::degree_size_type
289 
291 
299 
300  typedef typename std::map< int64_t, V > id_to_V;
301  typedef typename id_to_V::const_iterator LI;
302 
304 
306 
307  G graph;
309 
310 
312 
313 
314  id_to_V vertices_map;
315 
316  typename boost::property_map<G, boost::vertex_index_t>::type vertIndex;
317 
318  typedef std::map<V, size_t> IndexMap;
319  IndexMap mapIndex;
320  boost::associative_property_map<IndexMap> propmapIndex;
321 
323 
325 
326 
328  std::deque< T_E > removed_edges;
329 
331 
332 
333 
335 
336 
343  const std::vector< T_V > &vertices, graphType gtype)
344  : graph(vertices.size()),
345 #if 0
346  m_num_vertices(vertices.size()),
347 #endif
348  m_gType(gtype),
349  vertIndex(boost::get(boost::vertex_index, graph)),
350  propmapIndex(mapIndex) {
351  // add_vertices(vertices);
352  // This code does not work with contraction
353 #if 0
354  pgassert(pgrouting::check_vertices(vertices) == 0);
355 #endif
356  size_t i = 0;
357  for (auto vi = boost::vertices(graph).first;
358  vi != boost::vertices(graph).second; ++vi) {
359  vertices_map[vertices[i].id] = (*vi);
360  graph[(*vi)].cp_members(vertices[i]);
361  // put(propmapIndex, *vi, num_vertices());
362  pgassert(vertIndex[*vi] == i);
363  ++i;
364  }
365 
366  std::ostringstream log;
367  for (auto iter = vertices_map.begin();
368  iter != vertices_map.end();
369  iter++) {
370  log << "Key: "
371  << iter->first <<"\tValue:" << iter->second << "\n";
372  }
373  for (const auto vertex : vertices) {
374  pgassert(has_vertex(vertex.id));
375  }
376  // pgassert(mapIndex.size() == vertices.size());
377  }
378 
383  : graph(0),
384 #if 0
385  m_num_vertices(0),
386 #endif
387  m_gType(gtype),
388  vertIndex(boost::get(boost::vertex_index, graph)),
389  propmapIndex(mapIndex) {
390  }
391 
392 
394 
395 
403  template < typename T >
404  void insert_edges(const T *edges, int64_t count) {
405  insert_edges(std::vector < T >(edges, edges + count));
406  }
407 
408  template < typename T >
409  void insert_edges_neg(const T *edges, int64_t count) {
410  insert_edges(std::vector < T >(edges, edges + count), false);
411  }
412 
413  template < typename T>
414  void insert_edges(T *edges, int64_t count, bool) {
415  for (int64_t i = 0; i < count; ++i) {
416  pgassert(has_vertex(edges[i].source));
417  pgassert(has_vertex(edges[i].target));
418  graph_add_edge_no_create_vertex(edges[i]);
419  }
420  }
421 
422 
441  template < typename T >
442  void insert_edges(const std::vector<T> &edges, bool normal = true) {
443 #if 0
444  // This code does not work with contraction
445  if (num_vertices() == 0) {
446  auto vertices = pgrouting::extract_vertices(edges);
447  pgassert(pgrouting::check_vertices(vertices) == 0);
448  add_vertices(vertices);
449  }
450 #endif
451  for (const auto edge : edges) {
452  graph_add_edge(edge, normal);
453  }
454  }
456 
457  private:
488  std::vector< T_V > vertices) {
489  pgassert(num_vertices() == 0);
490  for (const auto vertex : vertices) {
491  pgassert(!has_vertex(vertex.id));
492 
493  auto v = add_vertex(graph);
494  vertices_map[vertex.id] = v;
495  graph[v].cp_members(vertex);
496  // put(propmapIndex, v, num_vertices());
497 
498  pgassert(has_vertex(vertex.id));
499  }
500  // pgassert(mapIndex.size() == vertices.size());
501  pgassert(num_vertices() == vertices.size());
502  }
503 
504 
505  public:
507 
508 
515  degree_size_type out_degree(int64_t vertex_id) const {
516  if (!has_vertex(vertex_id)) {
517  return 0;
518  }
519  return out_degree(get_V(vertex_id));
520  }
521  degree_size_type in_degree(int64_t vertex_id) const {
522  if (!has_vertex(vertex_id)) {
523  return 0;
524  }
525  return is_directed()?
526  in_degree(get_V(vertex_id))
527  : out_degree(get_V(vertex_id));
528  }
529 
530 
538  V get_V(const T_V &vertex) {
539  auto vm_s(vertices_map.find(vertex.id));
540  if (vm_s == vertices_map.end()) {
541  auto v = add_vertex(graph);
542  graph[v].cp_members(vertex);
543  vertices_map[vertex.id] = v;
544  put(propmapIndex, v, num_vertices());
545  return v;
546  }
547  return vm_s->second;
548  }
549 
556  V get_V(int64_t vid) const {
557  pgassert(has_vertex(vid));
558  return vertices_map.find(vid)->second;
559  }
560 
562  bool has_vertex(int64_t vid) const {
563  return vertices_map.find(vid) != vertices_map.end();
564  }
565 
566 
567 
569 
570 
571  bool is_directed() const {return m_gType == DIRECTED;}
572  bool is_undirected() const {return m_gType == UNDIRECTED;}
573  bool is_source(V v_idx, E e_idx) const {return v_idx == source(e_idx);}
574  bool is_target(V v_idx, E e_idx) const {return v_idx == target(e_idx);}
575 
577 
579 
580 
581 
582  T_E& operator[](E e_idx) {return graph[e_idx];}
583  const T_E& operator[](E e_idx) const {return graph[e_idx];}
584 
585  T_V& operator[](V v_idx) {return graph[v_idx];}
586  const T_V& operator[](V v_idx) const {return graph[v_idx];}
587 
588  V source(E e_idx) const {return boost::source(e_idx, graph);}
589  V target(E e_idx) const {return boost::target(e_idx, graph);}
590  V adjacent(V v_idx, E e_idx) const {
591  pgassert(is_source(v_idx, e_idx) || is_target(v_idx, e_idx));
592  return is_source(v_idx, e_idx)?
593  target(e_idx) :
594  source(e_idx);
595  }
596 
597 
605  return is_directed()?
606  boost::in_degree(v, graph) :
607  boost::out_degree(v, graph);
608  }
609 
616  return boost::out_degree(v, graph);
617  }
618 
620 
621 
623 
624 
637  void disconnect_edge(int64_t p_from, int64_t p_to);
638 
639 
641 
650  void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id);
651 
652 
653 
654 
656 
669  void disconnect_vertex(int64_t p_vertex);
670  void disconnect_vertex(V vertex);
671 
672 
674  void restore_graph();
675 
677 
679 
680 
681  friend std::ostream& operator<<(
682  std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g) {
683  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
684 
685  for (auto vi = vertices(g.graph).first;
686  vi != vertices(g.graph).second; ++vi) {
687  if ((*vi) >= g.num_vertices()) break;
688  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
689  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
690  out != out_end; ++out) {
691  log << ' '
692  << g.graph[*out].id << "=("
693  << g[g.source(*out)].id << ", "
694  << g[g.target(*out)].id << ") = "
695  << g.graph[*out].cost <<"\t";
696  }
697  log << std::endl;
698  }
699  return log;
700  }
701 
703 
704 
705  int64_t get_edge_id(V from, V to, double &distance) const;
706 
707  size_t num_vertices() const { return boost::num_vertices(graph);}
708  size_t num_edges() const { return boost::num_edges(graph);}
709 
710 
711  void graph_add_edge(const T_E &edge);
712 
713  template < typename T >
714  void graph_add_edge(const T &edge, bool normal = true);
715 
716 
720  template < typename T>
721  void graph_add_edge_no_create_vertex(const T &edge) {
722  bool inserted;
723  E e;
724  if ((edge.cost < 0) && (edge.reverse_cost < 0))
725  return;
726 
727 #if 0
728  std::ostringstream log;
729  for (auto iter = vertices_map.begin();
730  iter != vertices_map.end();
731  iter++) {
732  log << "Key: " << iter->first <<"\tValue:" << iter->second << "\n";
733  }
734  pgassertwm(has_vertex(edge.source), log.str().c_str());
735  pgassert(has_vertex(edge.target));
736 #endif
737 
738  auto vm_s = get_V(edge.source);
739  auto vm_t = get_V(edge.target);
740 
741 
742  if (edge.cost >= 0) {
743  boost::tie(e, inserted) =
744  boost::add_edge(vm_s, vm_t, graph);
745  graph[e].cost = edge.cost;
746  graph[e].id = edge.id;
747  }
748 
749  if (edge.reverse_cost >= 0 && (is_directed()
750  || (is_undirected() && edge.cost != edge.reverse_cost))) {
751  boost::tie(e, inserted) =
752  boost::add_edge(vm_t, vm_s, graph);
753  graph[e].cost = edge.reverse_cost;
754  graph[e].id = edge.id;
755  }
756  }
757 };
758 
759 
760 
761 
762 template < class G, typename T_V, typename T_E >
763 void
764 Pgr_base_graph< G, T_V, T_E >::disconnect_edge(int64_t p_from, int64_t p_to) {
765  T_E d_edge;
766 
767  // nothing to do, the vertex doesn't exist
768  if (!has_vertex(p_from) || !has_vertex(p_to)) return;
769 
770  EO_i out, out_end;
771  V g_from(get_V(p_from));
772  V g_to(get_V(p_to));
773 
774  // store the edges that are going to be removed
775  for (boost::tie(out, out_end) = out_edges(g_from, graph);
776  out != out_end; ++out) {
777  if (target(*out) == g_to) {
778  d_edge.id = graph[*out].id;
779  d_edge.source = graph[source(*out)].id;
780  d_edge.target = graph[target(*out)].id;
781  d_edge.cost = graph[*out].cost;
782  removed_edges.push_back(d_edge);
783  }
784  }
785  // the actual removal
786  boost::remove_edge(g_from, g_to, graph);
787 }
788 
789 
790 
791 template < class G, typename T_V, typename T_E >
792 void
794  int64_t vertex_id, int64_t edge_id) {
795  T_E d_edge;
796 
797  // nothing to do, the vertex doesn't exist
798  if (!has_vertex(vertex_id)) return;
799  auto v_from(get_V(vertex_id));
800 
801  EO_i out, out_end;
802  bool change = true;
803  // store the edge that are going to be removed
804  while (change) {
805  change = false;
806  for (boost::tie(out, out_end) = out_edges(v_from, graph);
807  out != out_end; ++out) {
808  if (graph[*out].id == edge_id) {
809  d_edge.id = graph[*out].id;
810  d_edge.source = graph[source(*out)].id;
811  d_edge.target = graph[target(*out)].id;
812  d_edge.cost = graph[*out].cost;
813  removed_edges.push_back(d_edge);
814  boost::remove_edge((*out), graph);
815  change = true;
816  break;
817  }
818  }
819  }
820 }
821 
822 
823 template < class G, typename T_V, typename T_E >
824 void
826  if (!has_vertex(vertex)) return;
827  disconnect_vertex(get_V(vertex));
828 }
829 
830 template < class G, typename T_V, typename T_E >
831 void
833  T_E d_edge;
834 
835  EO_i out, out_end;
836  // store the edges that are going to be removed
837  for (boost::tie(out, out_end) = out_edges(vertex, graph);
838  out != out_end; ++out) {
839  d_edge.id = graph[*out].id;
840  d_edge.source = graph[source(*out)].id;
841  d_edge.target = graph[target(*out)].id;
842  d_edge.cost = graph[*out].cost;
843  removed_edges.push_back(d_edge);
844  }
845 
846  // special case
847  if (m_gType == DIRECTED) {
848  EI_i in, in_end;
849  for (boost::tie(in, in_end) = in_edges(vertex, graph);
850  in != in_end; ++in) {
851  d_edge.id = graph[*in].id;
852  d_edge.source = graph[source(*in)].id;
853  d_edge.target = graph[target(*in)].id;
854  d_edge.cost = graph[*in].cost;
855  removed_edges.push_back(d_edge);
856  }
857  }
858 
859  // delete incoming and outgoing edges from the vertex
860  boost::clear_vertex(vertex, graph);
861 }
862 
863 template < class G, typename T_V, typename T_E >
864 void
866  while (removed_edges.size() != 0) {
867  graph_add_edge(removed_edges[0]);
868  removed_edges.pop_front();
869  }
870 }
871 
872 
873 template < class G, typename T_V, typename T_E >
874 int64_t
876  V from,
877  V to,
878  double &distance) const {
879  E e;
880  EO_i out_i, out_end;
881  V v_source, v_target;
882  double minCost = (std::numeric_limits<double>::max)();
883  int64_t minEdge = -1;
884  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
885  out_i != out_end; ++out_i) {
886  e = *out_i;
887  v_target = target(e);
888  v_source = source(e);
889  if ((from == v_source) && (to == v_target)
890  && (distance == graph[e].cost))
891  return graph[e].id;
892  if ((from == v_source) && (to == v_target)
893  && (minCost > graph[e].cost)) {
894  minCost = graph[e].cost;
895  minEdge = graph[e].id;
896  }
897  }
898  distance = minEdge == -1? 0: minCost;
899  return minEdge;
900 }
901 
902 
903 template < class G, typename T_V, typename T_E >
904 void
906  bool inserted;
907  typename Pgr_base_graph< G, T_V, T_E >::LI vm_s, vm_t;
909 
910  vm_s = vertices_map.find(edge.source);
911  if (vm_s == vertices_map.end()) {
912  vertices_map[edge.source]= num_vertices();
913  vm_s = vertices_map.find(edge.source);
914  }
915 
916  vm_t = vertices_map.find(edge.target);
917  if (vm_t == vertices_map.end()) {
918  vertices_map[edge.target]= num_vertices();
919  vm_t = vertices_map.find(edge.target);
920  }
921 
922  if (edge.cost >= 0) {
923  boost::tie(e, inserted) =
924  boost::add_edge(vm_s->second, vm_t->second, graph);
925  graph[e].cp_members(edge);
926  }
927 }
928 
929 
930 template < class G, typename T_V, typename T_E >
931 template < typename T>
932 void
934  bool inserted;
936  if ((edge.cost < 0) && (edge.reverse_cost < 0))
937  return;
938 
939  /*
940  * true: for source
941  * false: for target
942  */
943  auto vm_s = get_V(T_V(edge, true));
944  auto vm_t = get_V(T_V(edge, false));
945 
946  pgassert(vertices_map.find(edge.source) != vertices_map.end());
947  pgassert(vertices_map.find(edge.target) != vertices_map.end());
948  if (edge.cost >= 0) {
949  boost::tie(e, inserted) =
950  boost::add_edge(vm_s, vm_t, graph);
951  graph[e].cost = edge.cost;
952  graph[e].id = edge.id;
953  }
954 
955  if (edge.reverse_cost >= 0
956  && (m_gType == DIRECTED
957  || (m_gType == UNDIRECTED && edge.cost != edge.reverse_cost))) {
958  boost::tie(e, inserted) =
959  boost::add_edge(vm_t, vm_s, graph);
960 
961  graph[e].cost = edge.reverse_cost;
962  graph[e].id = normal? edge.id : -edge.id;
963  }
964 }
965 
966 
967 /****************** PRIVATE *******************/
968 
969 } // namespace graph
970 } // namespace pgrouting
971 #endif // INCLUDE_CPP_COMMON_PGR_BASE_GRAPH_HPP_
void graph_add_edge_no_create_vertex(const T &edge)
Use this function when the vertices are already inserted in the graph.
boost::graph_traits< G >::vertex_iterator V_i
void insert_edges_neg(const T *edges, int64_t count)
boost::graph_traits< G >::out_edge_iterator EO_i
boost::graph_traits< G >::degree_size_type degree_size_type
const T_V & operator[](V v_idx) const
V get_V(int64_t vid) const
get the vertex descriptor of the vid
Definition: trsp.h:31
degree_size_type out_degree(V &v) const
out degree of a vertex
void insert_edges(T *edges, int64_t count, bool)
void disconnect_vertex(int64_t p_vertex)
Disconnects all incoming and outgoing edges from the vertex.
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
boost::graph_traits< G >::vertices_size_type vertices_size_type
void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id)
Disconnects the outgoing edges of a vertex.
void insert_edges(const T *edges, int64_t count)
Inserts count edges of type T into the graph.
std::deque< T_E > removed_edges
Used for storing the removed_edges.
V adjacent(V v_idx, E e_idx) const
boost::associative_property_map< IndexMap > propmapIndex
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
void insert_edges(const std::vector< T > &edges, bool normal=true)
Inserts count edges of type pgr_edge_t into the graph.
int64_t get_edge_id(V from, V to, double &distance) const
degree_size_type in_degree(int64_t vertex_id) const
boost::graph_traits< G >::edge_iterator E_i
boost::property_map< G, boost::vertex_index_t >::type vertIndex
degree_size_type in_degree(V &v) const
in degree of a vertex
graphType m_gType
type (DIRECTED or UNDIRECTED)
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
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
boost::graph_traits< G >::in_edge_iterator EI_i
friend std::ostream & operator<<(std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g)
const T_E & operator[](E e_idx) const
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
bool is_source(V v_idx, E e_idx) const
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
Assertions Handling.
graph::Pgr_base_graph< boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Basic_vertex, Basic_edge >, Basic_vertex, Basic_edge > UndirectedGraph
boost::graph_traits< G >::edges_size_type edges_size_type
graph::Pgr_base_graph< boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, XY_vertex, Basic_edge >, XY_vertex, Basic_edge > xyDirectedGraph
graphType
Definition: graph_enum.h:30
id_to_V vertices_map
id -> graph id
std::map< int64_t, V > id_to_V
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
bool is_target(V v_idx, E e_idx) const
bool has_vertex(int64_t vid) const
True when vid is in the graph.
boost::graph_traits< G >::vertex_descriptor V
boost::graph_traits< G >::edge_descriptor E
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex