PGROUTING  2.5
 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 
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,
234 
235 typedef graph::Pgr_base_graph <
236 boost::adjacency_list < boost::vecS, boost::vecS,
237  boost::bidirectionalS,
240 
241 typedef graph::Pgr_base_graph <
242 boost::adjacency_list < boost::listS, boost::vecS,
243  boost::undirectedS,
246 
247 typedef graph::Pgr_base_graph <
248 boost::adjacency_list < boost::listS, boost::vecS,
249  boost::bidirectionalS,
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;
308  size_t m_num_vertices;
310 
311 
313 
314 
316 
317  typename boost::property_map<G, boost::vertex_index_t>::type vertIndex;
318 
319  typedef std::map<V, size_t> IndexMap;
321  boost::associative_property_map<IndexMap> propmapIndex;
322 
324 
326 
327 
329  std::deque< T_E > removed_edges;
330 
332 
333 
334 
336 
337 
344  const std::vector< T_V > &vertices, graphType gtype)
345  : graph(vertices.size()),
346  m_num_vertices(vertices.size()),
347  m_gType(gtype),
348  vertIndex(boost::get(boost::vertex_index, graph)),
350  //add_vertices(vertices);
351  // This code does not work with contraction
352 #if 0
353  pgassert(pgrouting::check_vertices(vertices) == 0);
354 #endif
355  size_t i = 0;
356  for (auto vi = boost::vertices(graph).first;
357  vi != boost::vertices(graph).second; ++vi) {
358  vertices_map[vertices[i].id] = (*vi);
359  graph[(*vi)].cp_members(vertices[i]);
360  //put(propmapIndex, *vi, num_vertices());
361  pgassert(vertIndex[*vi] == i);
362  ++i;
363  }
364 
365  std::ostringstream log;
366  for (auto iter = vertices_map.begin(); iter != vertices_map.end(); iter++) {
367  log << "Key: " << iter->first <<"\tValue:" << iter->second << "\n";
368  }
369  for (const auto vertex : vertices) {
371  }
372  //pgassert(mapIndex.size() == vertices.size());
373  }
374 
379  : graph(0),
380  m_num_vertices(0),
381  m_gType(gtype),
382  vertIndex(boost::get(boost::vertex_index, graph)),
384  }
385 
386 
388 
389 
397  template < typename T >
398  void insert_edges(const T *edges, int64_t count) {
399  insert_edges(std::vector < T >(edges, edges + count));
400  }
401 
402  template < typename T>
403  void insert_edges(T *edges, int64_t count, bool) {
404  for (int64_t i = 0; i < count; ++i) {
405  pgassert(has_vertex(edges[i].source));
406  pgassert(has_vertex(edges[i].target));
408  }
409  }
410 
411 
430  template < typename T >
431  void insert_edges(const std::vector < T > &edges) {
432 #if 0
433  // This code does not work with contraction
434  if (num_vertices() == 0) {
435  auto vertices = pgrouting::extract_vertices(edges);
436  pgassert(pgrouting::check_vertices(vertices) == 0);
437  add_vertices(vertices);
438  }
439 #endif
440  for (const auto edge : edges) {
442  }
443  }
445 
446  private:
477  std::vector< T_V > vertices) {
478  pgassert(m_num_vertices == 0);
479  for (const auto vertex : vertices) {
480  pgassert(!has_vertex(vertex.id));
481 
482  auto v = add_vertex(graph);
483  vertices_map[vertex.id] = v;
484  graph[v].cp_members(vertex);
485  //put(propmapIndex, v, num_vertices());
486 
488  }
489  //pgassert(mapIndex.size() == vertices.size());
490  pgassert(num_vertices() == vertices.size());
491  }
492 
493 
494  public:
496 
497 
504  degree_size_type out_degree(int64_t vertex_id) const {
505  if (!has_vertex(vertex_id)) {
506  return 0;
507  }
508  return out_degree(get_V(vertex_id));
509  }
510  degree_size_type in_degree(int64_t vertex_id) const {
511  if (!has_vertex(vertex_id)) {
512  return 0;
513  }
514  return is_directed()?
515  in_degree(get_V(vertex_id))
516  : out_degree(get_V(vertex_id));
517  }
518 
519 
527  V get_V(const T_V &vertex) {
528  auto vm_s(vertices_map.find(vertex.id));
529  if (vm_s == vertices_map.end()) {
530  auto v = add_vertex(graph);
531  graph[v].cp_members(vertex);
532  vertices_map[vertex.id] = v;
533  put(propmapIndex, v, m_num_vertices++);
534  return v;
535  }
536  return vm_s->second;
537  }
538 
545  V get_V(int64_t vid) const {
546  pgassert(has_vertex(vid));
547  return vertices_map.find(vid)->second;
548  }
549 
551  bool has_vertex(int64_t vid) const {
552  return vertices_map.find(vid) != vertices_map.end();
553  }
554 
555 
556 
558 
559 
560  bool is_directed() const {return m_gType == DIRECTED;}
561  bool is_undirected() const {return m_gType == UNDIRECTED;}
562  bool is_source(V v_idx, E e_idx) const {return v_idx == source(e_idx);}
563  bool is_target(V v_idx, E e_idx) const {return v_idx == target(e_idx);}
564 
566 
568 
569 
570 
571  T_E& operator[](E e_idx) {return graph[e_idx];}
572  const T_E& operator[](E e_idx) const {return graph[e_idx];}
573 
574  T_V& operator[](V v_idx) {return graph[v_idx];}
575  const T_V& operator[](V v_idx) const {return graph[v_idx];}
576 
577  V source(E e_idx) const {return boost::source(e_idx, graph);}
578  V target(E e_idx) const {return boost::target(e_idx, graph);}
579  V adjacent(V v_idx, E e_idx) const {
580  pgassert(is_source(v_idx, e_idx) || is_target(v_idx, e_idx));
581  return is_source(v_idx, e_idx)?
582  target(e_idx) :
583  source(e_idx);
584  }
585 
586 
594  return is_directed()?
595  boost::in_degree(v, graph) :
596  boost::out_degree(v, graph);
597  }
598 
605  return boost::out_degree(v, graph);
606  }
607 
609 
610 
612 
613 
626  void disconnect_edge(int64_t p_from, int64_t p_to);
627 
628 
630 
639  void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id);
640 
641 
642 
643 
645 
658  void disconnect_vertex(int64_t p_vertex);
659  void disconnect_vertex(V vertex);
660 
661 
663  void restore_graph();
664 
666 
668 
669 
670  friend std::ostream& operator<<(
671  std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g) {
672  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
673 
674  for (auto vi = vertices(g.graph).first;
675  vi != vertices(g.graph).second; ++vi) {
676  if ((*vi) >= g.m_num_vertices) break;
677  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
678  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
679  out != out_end; ++out) {
680  log << ' '
681  << g.graph[*out].id << "=("
682  << g[g.source(*out)].id << ", "
683  << g[g.target(*out)].id << ") = "
684  << g.graph[*out].cost <<"\t";
685  }
686  log << std::endl;
687  }
688  return log;
689  }
690 
692 
693 
694  int64_t get_edge_id(V from, V to, double &distance) const;
695 
696  size_t num_vertices() const { return boost::num_vertices(graph);}
697 
698 
699  void graph_add_edge(const T_E &edge);
700 
701  template < typename T >
702  void graph_add_edge(const T &edge);
703 
704 
706  template < typename T>
708  bool inserted;
709  E e;
710  if ((edge.cost < 0) && (edge.reverse_cost < 0))
711  return;
712 
713 #if 0
714  std::ostringstream log;
715  for (auto iter = vertices_map.begin(); iter != vertices_map.end(); iter++) {
716  log << "Key: " << iter->first <<"\tValue:" << iter->second << "\n";
717  }
718  pgassertwm(has_vertex(edge.source), log.str().c_str());
719  pgassert(has_vertex(edge.target));
720 #endif
721 
722  auto vm_s = get_V(edge.source);
723  auto vm_t = get_V(edge.target);
724 
725 
726  if (edge.cost >= 0) {
727  boost::tie(e, inserted) =
728  boost::add_edge(vm_s, vm_t, graph);
729  graph[e].cost = edge.cost;
730  graph[e].id = edge.id;
731  }
732 
733  if (edge.reverse_cost >= 0
734  && (is_directed() || (is_undirected() && edge.cost != edge.reverse_cost))) {
735  boost::tie(e, inserted) =
736  boost::add_edge(vm_t, vm_s, graph);
737  graph[e].cost = edge.reverse_cost;
738  graph[e].id = edge.id;
739  }
740  }
741 };
742 
743 
744 
745 
746 template < class G, typename T_V, typename T_E >
747 void
748 Pgr_base_graph< G, T_V, T_E >::disconnect_edge(int64_t p_from, int64_t p_to) {
749  T_E d_edge;
750 
751  // nothing to do, the vertex doesn't exist
752  if (!has_vertex(p_from) || !has_vertex(p_to)) return;
753 
754  EO_i out, out_end;
755  V g_from(get_V(p_from));
756  V g_to(get_V(p_to));
757 
758  // store the edges that are going to be removed
759  for (boost::tie(out, out_end) = out_edges(g_from, graph);
760  out != out_end; ++out) {
761  if (target(*out) == g_to) {
762  d_edge.id = graph[*out].id;
763  d_edge.source = graph[source(*out)].id;
764  d_edge.target = graph[target(*out)].id;
765  d_edge.cost = graph[*out].cost;
766  removed_edges.push_back(d_edge);
767  }
768  }
769  // the actual removal
770  boost::remove_edge(g_from, g_to, graph);
771 }
772 
773 
774 
775 template < class G, typename T_V, typename T_E >
776 void
778  int64_t vertex_id, int64_t edge_id) {
779  T_E d_edge;
780 
781  // nothing to do, the vertex doesn't exist
782  if (!has_vertex(vertex_id)) return;
783  auto v_from(get_V(vertex_id));
784 
785  EO_i out, out_end;
786  bool change = true;
787  // store the edge that are going to be removed
788  while (change) {
789  change = false;
790  for (boost::tie(out, out_end) = out_edges(v_from, graph);
791  out != out_end; ++out) {
792  if (graph[*out].id == edge_id) {
793  d_edge.id = graph[*out].id;
794  d_edge.source = graph[source(*out)].id;
795  d_edge.target = graph[target(*out)].id;
796  d_edge.cost = graph[*out].cost;
797  removed_edges.push_back(d_edge);
798  boost::remove_edge((*out), graph);
799  change = true;
800  break;
801  }
802  }
803  }
804 }
805 
806 
807 template < class G, typename T_V, typename T_E >
808 void
810  if (!has_vertex(vertex)) return;
811  disconnect_vertex(get_V(vertex));
812 }
813 
814 template < class G, typename T_V, typename T_E >
815 void
817  T_E d_edge;
818 
819  EO_i out, out_end;
820  // store the edges that are going to be removed
821  for (boost::tie(out, out_end) = out_edges(vertex, graph);
822  out != out_end; ++out) {
823  d_edge.id = graph[*out].id;
824  d_edge.source = graph[source(*out)].id;
825  d_edge.target = graph[target(*out)].id;
826  d_edge.cost = graph[*out].cost;
827  removed_edges.push_back(d_edge);
828  }
829 
830  // special case
831  if (m_gType == DIRECTED) {
832  EI_i in, in_end;
833  for (boost::tie(in, in_end) = in_edges(vertex, graph);
834  in != in_end; ++in) {
835  d_edge.id = graph[*in].id;
836  d_edge.source = graph[source(*in)].id;
837  d_edge.target = graph[target(*in)].id;
838  d_edge.cost = graph[*in].cost;
839  removed_edges.push_back(d_edge);
840  }
841  }
842 
843  // delete incoming and outgoing edges from the vertex
844  boost::clear_vertex(vertex, graph);
845 }
846 
847 template < class G, typename T_V, typename T_E >
848 void
850  while (removed_edges.size() != 0) {
851  graph_add_edge(removed_edges[0]);
852  removed_edges.pop_front();
853  }
854 }
855 
856 
857 template < class G, typename T_V, typename T_E >
858 int64_t
860  V from,
861  V to,
862  double &distance) const {
863  E e;
864  EO_i out_i, out_end;
865  V v_source, v_target;
866  double minCost = (std::numeric_limits<double>::max)();
867  int64_t minEdge = -1;
868  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
869  out_i != out_end; ++out_i) {
870  e = *out_i;
871  v_target = target(e);
872  v_source = source(e);
873  if ((from == v_source) && (to == v_target)
874  && (distance == graph[e].cost))
875  return graph[e].id;
876  if ((from == v_source) && (to == v_target)
877  && (minCost > graph[e].cost)) {
878  minCost = graph[e].cost;
879  minEdge = graph[e].id;
880  }
881  }
882  distance = minEdge == -1? 0: minCost;
883  return minEdge;
884 }
885 
886 
887 template < class G, typename T_V, typename T_E >
888 void
890  bool inserted;
891  typename Pgr_base_graph< G, T_V, T_E >::LI vm_s, vm_t;
893 
894  vm_s = vertices_map.find(edge.source);
895  if (vm_s == vertices_map.end()) {
896  vertices_map[edge.source]= m_num_vertices;
897  vm_s = vertices_map.find(edge.source);
898  }
899 
900  vm_t = vertices_map.find(edge.target);
901  if (vm_t == vertices_map.end()) {
902  vertices_map[edge.target]= m_num_vertices;
903  vm_t = vertices_map.find(edge.target);
904  }
905 
906  if (edge.cost >= 0) {
907  boost::tie(e, inserted) =
908  boost::add_edge(vm_s->second, vm_t->second, graph);
909  graph[e].cp_members(edge);
910  }
911 }
912 
913 
914 template < class G, typename T_V, typename T_E >
915 template < typename T>
916 void
918  bool inserted;
920  if ((edge.cost < 0) && (edge.reverse_cost < 0))
921  return;
922 
923  /*
924  * true: for source
925  * false: for target
926  */
927  auto vm_s = get_V(T_V(edge, true));
928  auto vm_t = get_V(T_V(edge, false));
929 
930  pgassert(vertices_map.find(edge.source) != vertices_map.end());
931  pgassert(vertices_map.find(edge.target) != vertices_map.end());
932  if (edge.cost >= 0) {
933  boost::tie(e, inserted) =
934  boost::add_edge(vm_s, vm_t, graph);
935  graph[e].cost = edge.cost;
936  graph[e].id = edge.id;
937  }
938 
939  if (edge.reverse_cost >= 0) {
940  boost::tie(e, inserted) =
941  boost::add_edge(vm_t, vm_s, graph);
942 
943  graph[e].cost = edge.reverse_cost;
944  graph[e].id = edge.id;
945  }
946 }
947 
948 
949 /****************** PRIVATE *******************/
950 
951 } // namespace graph
952 } // namespace pgrouting
953 #endif // INCLUDE_CPP_COMMON_PGR_BASE_GRAPH_HPP_
static edge_t edges[22573]
const T_E & operator[](E e_idx) const
boost::associative_property_map< IndexMap > propmapIndex
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 >::edges_size_type edges_size_type
Definition: trsp.h:31
boost::graph_traits< G >::edge_descriptor E
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
void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id)
Disconnects the outgoing edges of a vertex.
void add_vertices(std::vector< T_V > vertices)
adds the vertices into the graph
void insert_edges(const T *edges, int64_t count)
Inserts count edges of type T into the graph.
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.
V adjacent(V v_idx, E e_idx) const
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
degree_size_type in_degree(int64_t vertex_id) const
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
void insert_edges(const std::vector< T > &edges)
Inserts count edges of type pgr_edge_t into the graph.
boost::graph_traits< G >::vertex_iterator V_i
bool is_source(V v_idx, E e_idx) const
boost::graph_traits< G >::edge_iterator E_i
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
const T_V & operator[](V v_idx) const
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.
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.
bool is_target(V v_idx, E e_idx) const
void insert_edges(T *edges, int64_t count, bool)
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
graphType
Definition: graph_enum.h:30
degree_size_type in_degree(V &v) const
in degree of a vertex
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
out degree of a vertex
boost::graph_traits< G >::in_edge_iterator EI_i
boost::property_map< G, boost::vertex_index_t >::type vertIndex