PGROUTING  3.2
pgr_base_graph.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2  *
3 Copyright (c) 2015 Celia Virginia Vergara Castillo
4 vicky_vergara@hotmail.com
5 ------
6 
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11 
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16 
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20 
21  ********************************************************************PGR-GNU*/
22 
25 #ifndef INCLUDE_CPP_COMMON_PGR_BASE_GRAPH_HPP_
26 #define INCLUDE_CPP_COMMON_PGR_BASE_GRAPH_HPP_
27 #pragma once
28 
29 #include <boost/graph/iteration_macros.hpp>
30 #include <boost/config.hpp>
31 #include <boost/graph/adjacency_list.hpp>
32 #include <boost/graph/graph_utility.hpp>
33 
34 #include <deque>
35 #include <vector>
36 #include <set>
37 #include <map>
38 #include <limits>
39 
40 #include "c_types/graph_enum.h"
41 
43 #include "cpp_common/xy_vertex.h"
44 #include "cpp_common/basic_edge.h"
45 
46 #include "cpp_common/pgr_assert.h"
47 
48 namespace pgrouting {
49 
166 namespace graph {
167 template <class G, typename Vertex, typename Edge>
169 
170 } // namespace graph
171 
172 
182 typedef graph::Pgr_base_graph <
183 boost::adjacency_list < boost::vecS, boost::vecS,
184  boost::undirectedS,
187 
188 typedef graph::Pgr_base_graph <
189 boost::adjacency_list < boost::vecS, boost::vecS,
190  boost::bidirectionalS,
193 
194 typedef graph::Pgr_base_graph <
195 boost::adjacency_list < boost::listS, boost::vecS,
196  boost::undirectedS,
199 
200 typedef graph::Pgr_base_graph <
201 boost::adjacency_list < boost::listS, boost::vecS,
202  boost::bidirectionalS,
205 
207 
208 
209 namespace graph {
210 
211 template <typename G, typename T_V, typename T_E>
212 class Pgr_base_graph {
213  public:
226  typedef G B_G;
227  typedef T_E G_T_E;
228  typedef T_V G_T_V;
229  typedef typename boost::graph_traits < G >::vertex_descriptor V;
230  typedef typename boost::graph_traits < G >::edge_descriptor E;
231  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
232  typedef typename boost::graph_traits < G >::edge_iterator E_i;
233  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
234  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
235 
236  typedef typename boost::graph_traits < G >::vertices_size_type
238  typedef typename boost::graph_traits < G >::edges_size_type
240  typedef typename boost::graph_traits < G >::degree_size_type
242 
244 
252 
253  typedef typename std::map< int64_t, V > id_to_V;
254  typedef typename id_to_V::const_iterator LI;
255 
257 
259 
262 
263 
265 
266 
268 
269  typename boost::property_map<G, boost::vertex_index_t>::type vertIndex;
270 
271  typedef std::map<V, size_t> IndexMap;
273  boost::associative_property_map<IndexMap> propmapIndex;
274 
276 
278 
279 
281  std::deque< T_E > removed_edges;
282 
284 
285 
286 
288 
289 
296  const std::vector< T_V > &vertices, graphType gtype)
297  : graph(vertices.size()),
298 #if 0
299  m_num_vertices(vertices.size()),
300 #endif
301  m_gType(gtype),
302  vertIndex(boost::get(boost::vertex_index, graph)),
304  // add_vertices(vertices);
305  // This code does not work with contraction
306 #if 0
307  pgassert(pgrouting::check_vertices(vertices) == 0);
308 #endif
309  size_t i = 0;
310  for (auto vi = boost::vertices(graph).first;
311  vi != boost::vertices(graph).second; ++vi) {
312  vertices_map[vertices[i].id] = (*vi);
313  graph[(*vi)].cp_members(vertices[i]);
314  // put(propmapIndex, *vi, num_vertices());
315  pgassert(vertIndex[*vi] == i);
316  ++i;
317  }
318 
319  std::ostringstream log;
320  for (auto iter = vertices_map.begin();
321  iter != vertices_map.end();
322  iter++) {
323  log << "Key: "
324  << iter->first <<"\tValue:" << iter->second << "\n";
325  }
326  for (const auto vertex : vertices) {
327  pgassert(has_vertex(vertex.id));
328  }
329  // pgassert(mapIndex.size() == vertices.size());
330  }
331 
336  : graph(0),
337 #if 0
338  m_num_vertices(0),
339 #endif
340  m_gType(gtype),
341  vertIndex(boost::get(boost::vertex_index, graph)),
343  }
344 
345 
347 
348 
356  template < typename T >
357  void insert_edges(const T *edges, size_t count) {
358  insert_edges(std::vector < T >(edges, edges + count));
359  }
360 
361  template < typename T >
362  void insert_edges_neg(const T *edges, size_t count) {
363  insert_edges(std::vector < T >(edges, edges + count), false);
364  }
365 
366  template < typename T>
367  void insert_edges(T *edges, size_t count, bool) {
368  for (size_t i = 0; i < count; ++i) {
369  pgassert(has_vertex(edges[i].source));
370  pgassert(has_vertex(edges[i].target));
372  }
373  }
374 
375  template < typename T >
376  void insert_negative_edges(const T *edges, int64_t count) {
377  insert_negative_edges(std::vector < T >(edges, edges + count));
378  }
379 
393  template <typename T>
394  void
395  insert_edges(const std::vector<T> &edges, bool normal = true) {
396 #if 0
397  // This code does not work with contraction
398  if (num_vertices() == 0) {
399  auto vertices = pgrouting::extract_vertices(edges);
400  pgassert(pgrouting::check_vertices(vertices) == 0);
401  add_vertices(vertices);
402  }
403 #endif
404  for (const auto edge : edges) {
405  graph_add_edge(edge, normal);
406  }
407  }
408 
409  template <typename T>
410  void insert_min_edges_no_parallel(const T *edges, size_t count) {
411  insert_edges(std::vector<T>(edges, edges + count));
412  }
413 
414  template <typename T>
415  void
416  insert_min_edges_no_parallel(const std::vector<T> &edges) {
417  for (const auto edge : edges) {
419  }
420  }
421 
422  template < typename T >
424  const std::vector<T> &edges,
425  bool normal = true) {
426  for (const auto edge : edges) {
427  graph_add_neg_edge(edge, normal);
428  }
429  }
431 
432  private:
463  std::vector< T_V > vertices) {
464  pgassert(num_vertices() == 0);
465  for (const auto vertex : vertices) {
466  pgassert(!has_vertex(vertex.id));
467 
468  auto v = add_vertex(graph);
469  vertices_map[vertex.id] = v;
470  graph[v].cp_members(vertex);
471  // put(propmapIndex, v, num_vertices());
472 
473  pgassert(has_vertex(vertex.id));
474  }
475  // pgassert(mapIndex.size() == vertices.size());
476  pgassert(num_vertices() == vertices.size());
477  }
478 
479 
480  public:
482 
483 
489  degree_size_type out_degree(int64_t vertex_id) const {
490  if (!has_vertex(vertex_id)) {
491  return 0;
492  }
493  auto v = get_V(vertex_id);
494  auto d = out_degree(v);
495  return d;
496  }
497  degree_size_type in_degree(int64_t vertex_id) const {
498  if (!has_vertex(vertex_id)) {
499  return 0;
500  }
501  return is_directed()?
502  in_degree(get_V(vertex_id))
503  : out_degree(get_V(vertex_id));
504  }
505 
506 
512  V get_V(const T_V &vertex) {
513  auto vm_s(vertices_map.find(vertex.id));
514  if (vm_s == vertices_map.end()) {
515  auto v = add_vertex(graph);
516  graph[v].cp_members(vertex);
517  vertices_map[vertex.id] = v;
518  put(propmapIndex, v, num_vertices());
519  return v;
520  }
521  return vm_s->second;
522  }
523 
528  V get_V(int64_t vid) const {
529  pgassert(has_vertex(vid));
530  return vertices_map.find(vid)->second;
531  }
532 
534  bool has_vertex(int64_t vid) const {
535  return vertices_map.find(vid) != vertices_map.end();
536  }
537 
538 
539 
541 
542 
543  bool is_directed() const {return m_gType == DIRECTED;}
544  bool is_undirected() const {return m_gType == UNDIRECTED;}
545  bool is_source(V v_idx, E e_idx) const {return v_idx == source(e_idx);}
546  bool is_target(V v_idx, E e_idx) const {return v_idx == target(e_idx);}
547 
549 
551 
552 
553 
554  T_E& operator[](E e_idx) {return graph[e_idx];}
555  const T_E& operator[](E e_idx) const {return graph[e_idx];}
556 
557  T_V& operator[](V v_idx) {return graph[v_idx];}
558  const T_V& operator[](V v_idx) const {return graph[v_idx];}
559 
560  V source(E e_idx) const {return boost::source(e_idx, graph);}
561  V target(E e_idx) const {return boost::target(e_idx, graph);}
562  V adjacent(V v_idx, E e_idx) const {
563  pgassert(is_source(v_idx, e_idx) || is_target(v_idx, e_idx));
564  return is_source(v_idx, e_idx)?
565  target(e_idx) :
566  source(e_idx);
567  }
568 
569 
577  return is_directed()?
578  boost::in_degree(v, graph) :
579  boost::out_degree(v, graph);
580  }
581 
588  return boost::out_degree(v, graph);
589  }
590 
592 
593 
595 
596 
606  void disconnect_edge(int64_t p_from, int64_t p_to);
607 
608 
610 
617  void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id);
618 
619 
620 
621 
623 
633  void disconnect_vertex(int64_t p_vertex);
634  void disconnect_vertex(V vertex);
635 
636 
638  void restore_graph();
639 
641 
643 
644 
645  friend std::ostream& operator<<(
646  std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g) {
647  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
648 
649  for (auto vi = vertices(g.graph).first;
650  vi != vertices(g.graph).second; ++vi) {
651  if ((*vi) >= g.num_vertices()) break;
652  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
653  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
654  out != out_end; ++out) {
655  log << ' '
656  << g.graph[*out].id << "=("
657  << g[g.source(*out)].id << ", "
658  << g[g.target(*out)].id << ") = "
659  << g.graph[*out].cost <<"\t";
660  }
661  log << std::endl;
662  }
663  return log;
664  }
665 
667 
668 
669  int64_t get_edge_id(V from, V to, double &distance) const;
670 
672  V from,
673  V to,
674  double &distance) const {
675  E e;
676  EO_i out_i, out_end;
677  V v_source, v_target;
678  double minCost = (std::numeric_limits<double>::max)();
679  E minEdge;
680  bool valid = false;
681  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
682  out_i != out_end; ++out_i) {
683  e = *out_i;
684  if (!valid) {
685  minEdge = e;
686  valid = true;
687  }
688  v_target = target(e);
689  v_source = source(e);
690  if ((from == v_source) && (to == v_target)
691  && (distance == graph[e].cost)) {
692  return e;
693  }
694  if ((from == v_source) && (to == v_target)
695  && (minCost > graph[e].cost)) {
696  minCost = graph[e].cost;
697  minEdge = e;
698  }
699  }
700  return minEdge;
701  }
702 
703  size_t num_vertices() const { return boost::num_vertices(graph);}
704  size_t num_edges() const { return boost::num_edges(graph);}
705 
706 
707  void graph_add_edge(const T_E &edge);
708 
709  template < typename T >
710  void graph_add_edge(const T &edge, bool normal = true);
711 
712  template < typename T >
713  void graph_add_min_edge_no_parallel(const T &edge);
714 
715  template < typename T >
716  void graph_add_neg_edge(const T &edge, bool normal = true);
720  template < typename T>
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());
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 
750  if (edge.reverse_cost >= 0 && (is_directed()
751  || (is_undirected() && edge.cost != edge.reverse_cost))) {
752  boost::tie(e, inserted) =
753  boost::add_edge(vm_t, vm_s, graph);
754  graph[e].cost = edge.reverse_cost;
755  graph[e].id = edge.id;
756  }
757  }
758 };
759 
760 
761 
762 
763 template < class G, typename T_V, typename T_E >
764 void
765 Pgr_base_graph< G, T_V, T_E >::disconnect_edge(int64_t p_from, int64_t p_to) {
766  T_E d_edge;
767 
768  // nothing to do, the vertex doesn't exist
769  if (!has_vertex(p_from) || !has_vertex(p_to)) return;
770 
771  EO_i out, out_end;
772  V g_from(get_V(p_from));
773  V g_to(get_V(p_to));
774 
775  // store the edges that are going to be removed
776  for (boost::tie(out, out_end) = out_edges(g_from, graph);
777  out != out_end; ++out) {
778  if (target(*out) == g_to) {
779  d_edge.id = graph[*out].id;
780  d_edge.source = graph[source(*out)].id;
781  d_edge.target = graph[target(*out)].id;
782  d_edge.cost = graph[*out].cost;
783  removed_edges.push_back(d_edge);
784  }
785  }
786  // the actual removal
787  boost::remove_edge(g_from, g_to, graph);
788 }
789 
790 
791 
792 template < class G, typename T_V, typename T_E >
793 void
795  int64_t vertex_id, int64_t edge_id) {
796  T_E d_edge;
797 
798  // nothing to do, the vertex doesn't exist
799  if (!has_vertex(vertex_id)) return;
800  auto v_from(get_V(vertex_id));
801 
802  EO_i out, out_end;
803  bool change = true;
804  // store the edge that are going to be removed
805  while (change) {
806  change = false;
807  for (boost::tie(out, out_end) = out_edges(v_from, graph);
808  out != out_end; ++out) {
809  if (graph[*out].id == edge_id) {
810  d_edge.id = graph[*out].id;
811  d_edge.source = graph[source(*out)].id;
812  d_edge.target = graph[target(*out)].id;
813  d_edge.cost = graph[*out].cost;
814  removed_edges.push_back(d_edge);
815  boost::remove_edge((*out), graph);
816  change = true;
817  break;
818  }
819  }
820  }
821 }
822 
823 
824 template < class G, typename T_V, typename T_E >
825 void
827  if (!has_vertex(vertex)) return;
828  disconnect_vertex(get_V(vertex));
829 }
830 
831 template < class G, typename T_V, typename T_E >
832 void
834  T_E d_edge;
835 
836  EO_i out, out_end;
837  // store the edges that are going to be removed
838  for (boost::tie(out, out_end) = out_edges(vertex, graph);
839  out != out_end; ++out) {
840  d_edge.id = graph[*out].id;
841  d_edge.source = graph[source(*out)].id;
842  d_edge.target = graph[target(*out)].id;
843  d_edge.cost = graph[*out].cost;
844  removed_edges.push_back(d_edge);
845  }
846 
847  // special case
848  if (m_gType == DIRECTED) {
849  EI_i in, in_end;
850  for (boost::tie(in, in_end) = in_edges(vertex, graph);
851  in != in_end; ++in) {
852  d_edge.id = graph[*in].id;
853  d_edge.source = graph[source(*in)].id;
854  d_edge.target = graph[target(*in)].id;
855  d_edge.cost = graph[*in].cost;
856  removed_edges.push_back(d_edge);
857  }
858  }
859 
860  // delete incoming and outgoing edges from the vertex
861  boost::clear_vertex(vertex, graph);
862 }
863 
864 template < class G, typename T_V, typename T_E >
865 void
867  while (removed_edges.size() != 0) {
868  graph_add_edge(removed_edges[0]);
869  removed_edges.pop_front();
870  }
871 }
872 
873 
874 
875 
876 template < class G, typename T_V, typename T_E >
877 int64_t
879  V from,
880  V to,
881  double &distance) const {
882  E e;
883  EO_i out_i, out_end;
884  V v_source, v_target;
885  double minCost = (std::numeric_limits<double>::max)();
886  int64_t minEdge = -1;
887  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
888  out_i != out_end; ++out_i) {
889  e = *out_i;
890  v_target = target(e);
891  v_source = source(e);
892  if ((from == v_source) && (to == v_target)
893  && (distance == graph[e].cost))
894  return graph[e].id;
895  if ((from == v_source) && (to == v_target)
896  && (minCost > graph[e].cost)) {
897  minCost = graph[e].cost;
898  minEdge = graph[e].id;
899  }
900  }
901  distance = minEdge == -1? 0: minCost;
902  return minEdge;
903 }
904 
905 
906 template < class G, typename T_V, typename T_E >
907 void
909  typename Pgr_base_graph< G, T_V, T_E >::LI vm_s, vm_t;
911 
912  vm_s = vertices_map.find(edge.source);
913  if (vm_s == vertices_map.end()) {
914  vertices_map[edge.source]= num_vertices();
915  vm_s = vertices_map.find(edge.source);
916  }
917 
918  vm_t = vertices_map.find(edge.target);
919  if (vm_t == vertices_map.end()) {
920  vertices_map[edge.target]= num_vertices();
921  vm_t = vertices_map.find(edge.target);
922  }
923 
924  if (edge.cost >= 0) {
925  bool inserted;
926  boost::tie(e, inserted) =
927  boost::add_edge(vm_s->second, vm_t->second, graph);
928  graph[e].cp_members(edge);
929  }
930 }
931 
932 
933 template < class G, typename T_V, typename T_E >
934 template < typename T>
935 void
937  bool inserted;
939  if ((edge.cost < 0) && (edge.reverse_cost < 0))
940  return;
941 
942  /*
943  * true: for source
944  * false: for target
945  */
946  auto vm_s = get_V(T_V(edge, true));
947  auto vm_t = get_V(T_V(edge, false));
948 
949  pgassert(vertices_map.find(edge.source) != vertices_map.end());
950  pgassert(vertices_map.find(edge.target) != vertices_map.end());
951  if (edge.cost >= 0) {
952  boost::tie(e, inserted) =
953  boost::add_edge(vm_s, vm_t, graph);
954  graph[e].cost = edge.cost;
955  graph[e].id = edge.id;
956  }
957 
958  if (edge.reverse_cost >= 0
959  && (m_gType == DIRECTED
960  || (m_gType == UNDIRECTED && edge.cost != edge.reverse_cost))) {
961  boost::tie(e, inserted) =
962  boost::add_edge(vm_t, vm_s, graph);
963 
964  graph[e].cost = edge.reverse_cost;
965  graph[e].id = normal? edge.id : -edge.id;
966  }
967 }
968 
969 template < class G, typename T_V, typename T_E >
970 template < typename T>
971 void
973  bool inserted;
975  if ((edge.cost < 0) && (edge.reverse_cost < 0))
976  return;
977 
978  /*
979  * true: for source
980  * false: for target
981  */
982  auto vm_s = get_V(T_V(edge, true));
983  auto vm_t = get_V(T_V(edge, false));
984 
985  pgassert(vertices_map.find(edge.source) != vertices_map.end());
986  pgassert(vertices_map.find(edge.target) != vertices_map.end());
987  if (edge.cost >= 0) {
988  E e1;
989  bool found;
990  boost::tie(e1, found) = edge(vm_s, vm_t, graph);
991  if (found) {
992  if (edge.cost < graph[e1].cost) {
993  graph[e1].cost = edge.cost;
994  graph[e1].id = edge.id;
995  }
996  } else {
997  boost::tie(e, inserted) =
998  boost::add_edge(vm_s, vm_t, graph);
999  graph[e].cost = edge.cost;
1000  graph[e].id = edge.id;
1001  }
1002  }
1003 
1004  if (edge.reverse_cost >= 0
1005  && (m_gType == DIRECTED
1006  || (m_gType == UNDIRECTED && edge.cost != edge.reverse_cost))) {
1007  E e1;
1008  bool found;
1009  boost::tie(e1, found) = edge(vm_t, vm_s, graph);
1010  if (found) {
1011  if (edge.reverse_cost < graph[e1].cost) {
1012  graph[e1].cost = edge.reverse_cost;
1013  graph[e1].id = edge.id;
1014  }
1015  } else {
1016  boost::tie(e, inserted) =
1017  boost::add_edge(vm_t, vm_s, graph);
1018 
1019  graph[e].cost = edge.reverse_cost;
1020  graph[e].id = edge.id;
1021  }
1022  }
1023 }
1024 
1025 #if 1
1026 /*
1027 Add edges with negative cost(either cost or reverse_cost or both)
1028 Reading them into graph as positive cost ( edge_cost = (-1)* edge_negative_cost) [L931 & L941]
1029 To Do: Read and apply edges with negative cost in function as it is
1030 */
1031 
1032 template < class G, typename T_V, typename T_E >
1033 template < typename T>
1034 void
1036  bool inserted;
1038 
1039  auto vm_s = get_V(T_V(edge, true));
1040  auto vm_t = get_V(T_V(edge, false));
1041 
1042  pgassert(vertices_map.find(edge.source) != vertices_map.end());
1043  pgassert(vertices_map.find(edge.target) != vertices_map.end());
1044 
1045  boost::tie(e, inserted) =
1046  boost::add_edge(vm_s, vm_t, graph);
1047  if (edge.cost < 0) {
1048  // reading negative edges as positive
1049  graph[e].cost = (-0.5)*edge.cost;
1050  } else {
1051  graph[e].cost = edge.cost;
1052  }
1053  graph[e].id = edge.id;
1054 
1055  if (m_gType == DIRECTED
1056  || (m_gType == UNDIRECTED && edge.cost > edge.reverse_cost)) {
1057  boost::tie(e, inserted) =
1058  boost::add_edge(vm_t, vm_s, graph);
1059  if (edge.reverse_cost < 0) {
1060  // reading negative edges as positive
1061  graph[e].cost = (-0.5)*edge.reverse_cost;
1062  } else {
1063  graph[e].cost = edge.reverse_cost;
1064  }
1065 
1066  graph[e].id = normal? edge.id : -edge.id;
1067  }
1068 }
1069 #endif
1070 
1071 /****************** PRIVATE *******************/
1072 
1073 } // namespace graph
1074 } // namespace pgrouting
1075 #endif // INCLUDE_CPP_COMMON_PGR_BASE_GRAPH_HPP_
pgrouting::graph::Pgr_base_graph::graph_add_edge_no_create_vertex
void graph_add_edge_no_create_vertex(const T &edge)
Use this function when the vertices are already inserted in the graph.
Definition: pgr_base_graph.hpp:721
pgrouting::graph::Pgr_base_graph::propmapIndex
boost::associative_property_map< IndexMap > propmapIndex
Definition: pgr_base_graph.hpp:273
pgrouting::XY_vertex
Definition: xy_vertex.h:40
pgrouting::graph::Pgr_base_graph::graph
G graph
The graph.
Definition: pgr_base_graph.hpp:260
pgrouting::graph::Pgr_base_graph::vertIndex
boost::property_map< G, boost::vertex_index_t >::type vertIndex
Definition: pgr_base_graph.hpp:269
edge::reverse_cost
float8 reverse_cost
Definition: trsp.h:46
pgrouting::graph::Pgr_base_graph::insert_negative_edges
void insert_negative_edges(const T *edges, int64_t count)
Definition: pgr_base_graph.hpp:376
pgrouting::graph::Pgr_base_graph::disconnect_out_going_edge
void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id)
Disconnects the outgoing edges of a vertex.
Definition: pgr_base_graph.hpp:794
pgrouting::graph::Pgr_base_graph::out_degree
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
Definition: pgr_base_graph.hpp:489
edge::cost
float8 cost
Definition: trsp.h:45
pgrouting::graph::Pgr_base_graph::get_V
V get_V(int64_t vid) const
get the vertex descriptor of the vid Call has_vertex(vid) before calling this function
Definition: pgr_base_graph.hpp:528
edge::target
int64 target
Definition: trsp.h:44
pgrouting::UndirectedGraph
graph::Pgr_base_graph< boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Basic_vertex, Basic_edge >, Basic_vertex, Basic_edge > UndirectedGraph
Definition: pgr_base_graph.hpp:186
pgrouting::graph::Pgr_base_graph::get_edge
E get_edge(V from, V to, double &distance) const
Definition: pgr_base_graph.hpp:671
pgrouting::graph::Pgr_base_graph::m_gType
graphType m_gType
type (DIRECTED or UNDIRECTED)
Definition: pgr_base_graph.hpp:261
pgrouting::graph::Pgr_base_graph::LI
id_to_V::const_iterator LI
Definition: pgr_base_graph.hpp:254
pgrouting::graph::Pgr_base_graph::is_source
bool is_source(V v_idx, E e_idx) const
Definition: pgr_base_graph.hpp:545
pgrouting::graph::Pgr_base_graph::B_G
G B_G
Definition: pgr_base_graph.hpp:226
pgrouting::graph::Pgr_base_graph::restore_graph
void restore_graph()
Reconnects all edges that were removed.
Definition: pgr_base_graph.hpp:866
pgrouting::graph::Pgr_base_graph::target
V target(E e_idx) const
Definition: pgr_base_graph.hpp:561
pgrouting::graph::Pgr_base_graph::EI_i
boost::graph_traits< G >::in_edge_iterator EI_i
Definition: pgr_base_graph.hpp:234
pgrouting::graph::Pgr_base_graph::G_T_E
T_E G_T_E
Definition: pgr_base_graph.hpp:227
pgrouting::check_vertices
size_t check_vertices(std::vector< Basic_vertex > vertices)
Definition: basic_vertex.cpp:42
pgrouting::graph::Pgr_base_graph::degree_size_type
boost::graph_traits< G >::degree_size_type degree_size_type
Definition: pgr_base_graph.hpp:241
pgassertwm
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:117
pgrouting::graph::Pgr_base_graph::operator[]
const T_V & operator[](V v_idx) const
Definition: pgr_base_graph.hpp:558
pgrouting::graph::Pgr_base_graph::G_T_V
T_V G_T_V
Definition: pgr_base_graph.hpp:228
pgrouting::graph::Pgr_base_graph::has_vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
Definition: pgr_base_graph.hpp:534
pgrouting::graph::Pgr_base_graph::num_edges
size_t num_edges() const
Definition: pgr_base_graph.hpp:704
pgrouting::Basic_edge
Definition: basic_edge.h:35
pgrouting::graph::Pgr_base_graph::in_degree
degree_size_type in_degree(V &v) const
in degree of a vertex
Definition: pgr_base_graph.hpp:576
edge
Definition: trsp.h:41
pgassert
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
basic_edge.h
pgrouting::graph::Pgr_base_graph::IndexMap
std::map< V, size_t > IndexMap
Definition: pgr_base_graph.hpp:271
pgrouting::graph::Pgr_base_graph::insert_edges
void insert_edges(T *edges, size_t count, bool)
Definition: pgr_base_graph.hpp:367
UNDIRECTED
@ UNDIRECTED
Definition: graph_enum.h:30
pgrouting::graph::Pgr_base_graph::insert_edges
void insert_edges(const T *edges, size_t count)
Inserts count edges of type T into the graph.
Definition: pgr_base_graph.hpp:357
pgrouting::graph::Pgr_base_graph::get_V
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex When the vertex does not exist
Definition: pgr_base_graph.hpp:512
pgrouting::graph::Pgr_base_graph::is_target
bool is_target(V v_idx, E e_idx) const
Definition: pgr_base_graph.hpp:546
pgrouting::graph::Pgr_base_graph::insert_edges
void insert_edges(const std::vector< T > &edges, bool normal=true)
Inserts count edges of type pgr_edge_t into the graph The set of edges should not have an illegal ver...
Definition: pgr_base_graph.hpp:395
pgrouting::graph::Pgr_base_graph::E_i
boost::graph_traits< G >::edge_iterator E_i
Definition: pgr_base_graph.hpp:232
pgrouting::graph::Pgr_base_graph::id_to_V
std::map< int64_t, V > id_to_V
Definition: pgr_base_graph.hpp:253
pgrouting::graph::Pgr_base_graph::disconnect_edge
void disconnect_edge(int64_t p_from, int64_t p_to)
Disconnects all edges from p_from to p_to.
Definition: pgr_base_graph.hpp:765
pgrouting::graph::Pgr_base_graph::graph_add_neg_edge
void graph_add_neg_edge(const T &edge, bool normal=true)
Definition: pgr_base_graph.hpp:1035
pgrouting::graph::Pgr_base_graph::insert_negative_edges
void insert_negative_edges(const std::vector< T > &edges, bool normal=true)
Definition: pgr_base_graph.hpp:423
pgrouting::graph::Pgr_base_graph::source
V source(E e_idx) const
Definition: pgr_base_graph.hpp:560
pgrouting::graph::Pgr_base_graph::E
boost::graph_traits< G >::edge_descriptor E
Definition: pgr_base_graph.hpp:230
pgrouting::graph::Pgr_base_graph::is_directed
bool is_directed() const
Definition: pgr_base_graph.hpp:543
edge::source
int64 source
Definition: trsp.h:43
pgrouting::graph::Pgr_base_graph::num_vertices
size_t num_vertices() const
Definition: pgr_base_graph.hpp:703
graphType
graphType
Definition: graph_enum.h:30
pgrouting::Basic_vertex
Definition: basic_vertex.h:40
xy_vertex.h
graph_enum.h
pgrouting::graph::Pgr_base_graph::removed_edges
std::deque< T_E > removed_edges
Used for storing the removed_edges.
Definition: pgr_base_graph.hpp:281
pgr_assert.h
An assert functionality that uses C++ throw().
pgrouting::graph::Pgr_base_graph::add_vertices
void add_vertices(std::vector< T_V > vertices)
adds the vertices into the graph
Definition: pgr_base_graph.hpp:462
pgrouting::graph::Pgr_base_graph::mapIndex
IndexMap mapIndex
Definition: pgr_base_graph.hpp:272
pgrouting::graph::Pgr_base_graph::operator[]
T_E & operator[](E e_idx)
Definition: pgr_base_graph.hpp:554
pgrouting::graph::Pgr_base_graph::EO_i
boost::graph_traits< G >::out_edge_iterator EO_i
Definition: pgr_base_graph.hpp:233
DIRECTED
@ DIRECTED
Definition: graph_enum.h:30
pgrouting::graph::Pgr_base_graph::V_i
boost::graph_traits< G >::vertex_iterator V_i
Definition: pgr_base_graph.hpp:231
pgrouting::graph::Pgr_base_graph::insert_edges_neg
void insert_edges_neg(const T *edges, size_t count)
Definition: pgr_base_graph.hpp:362
if
if(DOXYGEN_FOUND) configure_file($
Definition: doxygen/CMakeLists.txt:13
pgrouting::graph::Pgr_base_graph::is_undirected
bool is_undirected() const
Definition: pgr_base_graph.hpp:544
pgrouting::DirectedGraph
graph::Pgr_base_graph< boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, Basic_vertex, Basic_edge >, Basic_vertex, Basic_edge > DirectedGraph
Definition: pgr_base_graph.hpp:192
pgrouting::graph::Pgr_base_graph::operator[]
const T_E & operator[](E e_idx) const
Definition: pgr_base_graph.hpp:555
pgrouting::graph::Pgr_base_graph::operator[]
T_V & operator[](V v_idx)
Definition: pgr_base_graph.hpp:557
basic_vertex.h
pgrouting::graph::Pgr_base_graph::graph_add_min_edge_no_parallel
void graph_add_min_edge_no_parallel(const T &edge)
Definition: pgr_base_graph.hpp:972
edge::id
int64 id
Definition: trsp.h:42
pgrouting::graph::Pgr_base_graph::edges_size_type
boost::graph_traits< G >::edges_size_type edges_size_type
Definition: pgr_base_graph.hpp:239
pgrouting::graph::Pgr_base_graph::operator<<
friend std::ostream & operator<<(std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g)
Definition: pgr_base_graph.hpp:645
pgrouting::alphashape::G
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
Definition: pgr_alphaShape.h:56
pgrouting::graph::Pgr_base_graph::V
boost::graph_traits< G >::vertex_descriptor V
Definition: pgr_base_graph.hpp:229
pgrouting::graph::Pgr_base_graph::get_edge_id
int64_t get_edge_id(V from, V to, double &distance) const
Definition: pgr_base_graph.hpp:878
pgrouting::graph::Pgr_base_graph
Definition: pgr_base_graph.hpp:168
pgrouting::graph::Pgr_base_graph::graph_add_edge
void graph_add_edge(const T_E &edge)
Definition: pgr_base_graph.hpp:908
pgrouting::graph::Pgr_base_graph::insert_min_edges_no_parallel
void insert_min_edges_no_parallel(const std::vector< T > &edges)
Definition: pgr_base_graph.hpp:416
pgrouting::graph::Pgr_base_graph::out_degree
degree_size_type out_degree(V &v) const
out degree of a vertex
Definition: pgr_base_graph.hpp:587
pgrouting::graph::Pgr_base_graph::insert_min_edges_no_parallel
void insert_min_edges_no_parallel(const T *edges, size_t count)
Definition: pgr_base_graph.hpp:410
pgrouting::graph::Pgr_base_graph::disconnect_vertex
void disconnect_vertex(int64_t p_vertex)
Disconnects all incoming and outgoing edges from the vertex.
Definition: pgr_base_graph.hpp:826
pgrouting::xyUndirectedGraph
graph::Pgr_base_graph< boost::adjacency_list< boost::listS, boost::vecS, boost::undirectedS, XY_vertex, Basic_edge >, XY_vertex, Basic_edge > xyUndirectedGraph
Definition: pgr_base_graph.hpp:198
pgrouting::extract_vertices
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
Definition: basic_vertex.cpp:59
pgrouting::graph::Pgr_base_graph::in_degree
degree_size_type in_degree(int64_t vertex_id) const
Definition: pgr_base_graph.hpp:497
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56
pgrouting::graph::Pgr_base_graph::vertices_map
id_to_V vertices_map
id -> graph id
Definition: pgr_base_graph.hpp:267
pgrouting::graph::Pgr_base_graph::adjacent
V adjacent(V v_idx, E e_idx) const
Definition: pgr_base_graph.hpp:562
pgrouting::graph::Pgr_base_graph::vertices_size_type
boost::graph_traits< G >::vertices_size_type vertices_size_type
Definition: pgr_base_graph.hpp:237
pgrouting::xyDirectedGraph
graph::Pgr_base_graph< boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, XY_vertex, Basic_edge >, XY_vertex, Basic_edge > xyDirectedGraph
Definition: pgr_base_graph.hpp:204