PGROUTING  2.4
 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 #ifndef SRC_COMMON_SRC_PGR_BASE_GRAPH_HPP_
26 #define SRC_COMMON_SRC_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 "./pgr_types.h" // for pgr_edge_t
41 
42 #include "./ch_vertex.h"
43 #include "./ch_edge.h"
44 #include "./basic_vertex.h"
45 #include "./xy_vertex.h"
46 
47 #include "./basic_edge.h"
48 #include "./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 typename boost::graph_traits < G >::vertex_descriptor V;
276  typedef typename boost::graph_traits < G >::edge_descriptor E;
277  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
278  typedef typename boost::graph_traits < G >::edge_iterator E_i;
279  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
280  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
281 
282  typedef typename boost::graph_traits < G >::vertices_size_type
284  typedef typename boost::graph_traits < G >::edges_size_type
286  typedef typename boost::graph_traits < G >::degree_size_type
288 
290 
298 
299  typedef typename std::map< int64_t, V > id_to_V;
300  typedef typename id_to_V::const_iterator LI;
301 
303 
305 
306  G graph;
307  size_t m_num_vertices;
309 
310 
312 
313 
315 
317 
319 
320 
322  std::deque< T_E > removed_edges;
323 
325 
326 
327 
329 
330 
337  const std::vector< T_V > &vertices, graphType gtype)
338  : graph(vertices.size()),
339  m_num_vertices(vertices.size()),
340  m_gType(gtype) {
341  pgassert(boost::num_vertices(graph) == num_vertices());
342  pgassert(boost::num_vertices(graph) == vertices.size());
343 #if 0
344  // This code does not work with contraction
345  pgassert(pgrouting::check_vertices(vertices) == 0);
346 #endif
347  size_t i = 0;
348  for (auto vi = boost::vertices(graph).first;
349  vi != boost::vertices(graph).second; ++vi) {
350  vertices_map[vertices[i].id] = (*vi);
351  graph[(*vi)].cp_members(vertices[i++]);
352  }
353  }
354 
359  : graph(0),
360  m_num_vertices(0),
361  m_gType(gtype) {
362  }
363 
364 
366 
367 
375  template < typename T >
376  void insert_edges(const T *edges, int64_t count) {
377  insert_edges(std::vector < T >(edges, edges + count));
378  }
379 
398  template < typename T >
399  void insert_edges(const std::vector < T > &edges) {
400 #if 0
401  // This code does not work with contraction
402  if (num_vertices() == 0) {
403  auto vertices = pgrouting::extract_vertices(edges);
404  pgassert(pgrouting::check_vertices(vertices) == 0);
405  add_vertices(vertices);
406  }
407 #endif
408  for (const auto edge : edges) {
410  }
411  }
413 
414  private:
431  void add_vertices(std::vector< T_V > vertices);
432 
433  public:
435 
436 
443  degree_size_type out_degree(int64_t vertex_id) const {
444  if (!has_vertex(vertex_id)) {
445  return 0;
446  }
447  return out_degree(get_V(vertex_id));
448  }
449  degree_size_type in_degree(int64_t vertex_id) const {
450  if (!has_vertex(vertex_id)) {
451  return 0;
452  }
453  return is_directed()?
454  in_degree(get_V(vertex_id))
455  : out_degree(get_V(vertex_id));
456  }
457 
458 
466  V get_V(const T_V &vertex) {
467  auto vm_s(vertices_map.find(vertex.id));
468  if (vm_s == vertices_map.end()) {
469  auto v = add_vertex(graph);
470  graph[v].cp_members(vertex);
471  vertices_map[vertex.id] = v;
472  return v;
473  }
474  return vm_s->second;
475  }
476 
483  V get_V(int64_t vid) const {
484  pgassert(has_vertex(vid));
485  return vertices_map.find(vid)->second;
486  }
487 
489  bool has_vertex(int64_t vid) const {
490  return vertices_map.find(vid) != vertices_map.end();
491  }
492 
493 
494 
496 
497 
498  bool is_directed() const {return m_gType == DIRECTED;}
499  bool is_undirected() const {return m_gType == UNDIRECTED;}
500  bool is_source(V v_idx, E e_idx) const {return v_idx == source(e_idx);}
501  bool is_target(V v_idx, E e_idx) const {return v_idx == target(e_idx);}
502 
504 
506 
507 
508 
509  T_E& operator[](E e_idx) {return graph[e_idx];}
510  const T_E& operator[](E e_idx) const {return graph[e_idx];}
511 
512  T_V& operator[](V v_idx) {return graph[v_idx];}
513  const T_V& operator[](V v_idx) const {return graph[v_idx];}
514 
515  V source(E e_idx) const {return boost::source(e_idx, graph);}
516  V target(E e_idx) const {return boost::target(e_idx, graph);}
517  V adjacent(V v_idx, E e_idx) const {
518  pgassert(is_source(v_idx, e_idx) || is_target(v_idx, e_idx));
519  return is_source(v_idx, e_idx)?
520  target(e_idx) :
521  source(e_idx);
522  }
523 
524 
532  return is_directed()?
533  boost::in_degree(v, graph) :
534  boost::out_degree(v, graph);
535  }
536 
543  return boost::out_degree(v, graph);
544  }
545 
547 
548 
550 
551 
564  void disconnect_edge(int64_t p_from, int64_t p_to);
565 
566 
568 
577  void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id);
578 
579 
580 
581 
583 
596  void disconnect_vertex(int64_t p_vertex);
597  void disconnect_vertex(V vertex);
598 
599 
601  void restore_graph();
602 
604 
606 
607 
608  friend std::ostream& operator<<(
609  std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g) {
610  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
611 
612  for (auto vi = vertices(g.graph).first;
613  vi != vertices(g.graph).second; ++vi) {
614  if ((*vi) >= g.m_num_vertices) break;
615  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
616  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
617  out != out_end; ++out) {
618  log << ' '
619  << g.graph[*out].id << "=("
620  << g[g.source(*out)].id << ", "
621  << g[g.target(*out)].id << ") = "
622  << g.graph[*out].cost <<"\t";
623  }
624  log << std::endl;
625  }
626  return log;
627  }
628 
630 
631 
632  int64_t get_edge_id(V from, V to, double &distance) const;
633 
634  size_t num_vertices() const { return boost::num_vertices(graph);}
635 
636 
637  void graph_add_edge(const T_E &edge);
638 
639  template < typename T >
640  void graph_add_edge(const T &edge);
641 };
642 
643 
644 
645 
646 template < class G, typename T_V, typename T_E >
647 void
648 Pgr_base_graph< G, T_V, T_E >::disconnect_edge(int64_t p_from, int64_t p_to) {
649  T_E d_edge;
650 
651  // nothing to do, the vertex doesn't exist
652  if (!has_vertex(p_from) || !has_vertex(p_to)) return;
653 
654  EO_i out, out_end;
655  V g_from(get_V(p_from));
656  V g_to(get_V(p_to));
657 
658  // store the edges that are going to be removed
659  for (boost::tie(out, out_end) = out_edges(g_from, graph);
660  out != out_end; ++out) {
661  if (target(*out) == g_to) {
662  d_edge.id = graph[*out].id;
663  d_edge.source = graph[source(*out)].id;
664  d_edge.target = graph[target(*out)].id;
665  d_edge.cost = graph[*out].cost;
666  removed_edges.push_back(d_edge);
667  }
668  }
669  // the actual removal
670  boost::remove_edge(g_from, g_to, graph);
671 }
672 
673 
674 
675 template < class G, typename T_V, typename T_E >
676 void
678  int64_t vertex_id, int64_t edge_id) {
679  T_E d_edge;
680 
681  // nothing to do, the vertex doesn't exist
682  if (!has_vertex(vertex_id)) return;
683  auto v_from(get_V(vertex_id));
684 
685  EO_i out, out_end;
686  bool change = true;
687  // store the edge that are going to be removed
688  while (change) {
689  change = false;
690  for (boost::tie(out, out_end) = out_edges(v_from, graph);
691  out != out_end; ++out) {
692  if (graph[*out].id == edge_id) {
693  d_edge.id = graph[*out].id;
694  d_edge.source = graph[source(*out)].id;
695  d_edge.target = graph[target(*out)].id;
696  d_edge.cost = graph[*out].cost;
697  removed_edges.push_back(d_edge);
698  boost::remove_edge((*out), graph);
699  change = true;
700  break;
701  }
702  }
703  }
704 }
705 
706 
707 template < class G, typename T_V, typename T_E >
708 void
710  if (!has_vertex(vertex)) return;
711  disconnect_vertex(get_V(vertex));
712 }
713 
714 template < class G, typename T_V, typename T_E >
715 void
717  T_E d_edge;
718 
719  EO_i out, out_end;
720  // store the edges that are going to be removed
721  for (boost::tie(out, out_end) = out_edges(vertex, graph);
722  out != out_end; ++out) {
723  d_edge.id = graph[*out].id;
724  d_edge.source = graph[source(*out)].id;
725  d_edge.target = graph[target(*out)].id;
726  d_edge.cost = graph[*out].cost;
727  removed_edges.push_back(d_edge);
728  }
729 
730  // special case
731  if (m_gType == DIRECTED) {
732  EI_i in, in_end;
733  for (boost::tie(in, in_end) = in_edges(vertex, graph);
734  in != in_end; ++in) {
735  d_edge.id = graph[*in].id;
736  d_edge.source = graph[source(*in)].id;
737  d_edge.target = graph[target(*in)].id;
738  d_edge.cost = graph[*in].cost;
739  removed_edges.push_back(d_edge);
740  }
741  }
742 
743  // delete incoming and outgoing edges from the vertex
744  boost::clear_vertex(vertex, graph);
745 }
746 
747 template < class G, typename T_V, typename T_E >
748 void
750  while (removed_edges.size() != 0) {
751  graph_add_edge(removed_edges[0]);
752  removed_edges.pop_front();
753  }
754 }
755 
756 
757 template < class G, typename T_V, typename T_E >
758 int64_t
760  V from,
761  V to,
762  double &distance) const {
763  E e;
764  EO_i out_i, out_end;
765  V v_source, v_target;
766  double minCost = (std::numeric_limits<double>::max)();
767  int64_t minEdge = -1;
768  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
769  out_i != out_end; ++out_i) {
770  e = *out_i;
771  v_target = target(e);
772  v_source = source(e);
773  if ((from == v_source) && (to == v_target)
774  && (distance == graph[e].cost))
775  return graph[e].id;
776  if ((from == v_source) && (to == v_target)
777  && (minCost > graph[e].cost)) {
778  minCost = graph[e].cost;
779  minEdge = graph[e].id;
780  }
781  }
782  distance = minEdge == -1? 0: minCost;
783  return minEdge;
784 }
785 
786 
787 template < class G, typename T_V, typename T_E >
788 void
790  bool inserted;
791  typename Pgr_base_graph< G, T_V, T_E >::LI vm_s, vm_t;
793 
794  vm_s = vertices_map.find(edge.source);
795  if (vm_s == vertices_map.end()) {
796  vertices_map[edge.source]= m_num_vertices;
797  vm_s = vertices_map.find(edge.source);
798  }
799 
800  vm_t = vertices_map.find(edge.target);
801  if (vm_t == vertices_map.end()) {
802  vertices_map[edge.target]= m_num_vertices;
803  vm_t = vertices_map.find(edge.target);
804  }
805 
806  if (edge.cost >= 0) {
807  boost::tie(e, inserted) =
808  boost::add_edge(vm_s->second, vm_t->second, graph);
809  graph[e].cp_members(edge);
810  }
811 }
812 
813 
814 template < class G, typename T_V, typename T_E >
815 template < typename T>
816 void
818  bool inserted;
820  if ((edge.cost < 0) && (edge.reverse_cost < 0))
821  return;
822 
823  /*
824  * true: for source
825  * false: for target
826  */
827  auto vm_s = get_V(T_V(edge, true));
828  auto vm_t = get_V(T_V(edge, false));
829 
830  pgassert(vertices_map.find(edge.source) != vertices_map.end());
831  pgassert(vertices_map.find(edge.target) != vertices_map.end());
832  if (edge.cost >= 0) {
833  boost::tie(e, inserted) =
834  boost::add_edge(vm_s, vm_t, graph);
835  graph[e].cost = edge.cost;
836  graph[e].id = edge.id;
837  }
838 
839  if (edge.reverse_cost >= 0) {
840  boost::tie(e, inserted) =
841  boost::add_edge(vm_t, vm_s, graph);
842 
843  graph[e].cost = edge.reverse_cost;
844  graph[e].id = edge.id;
845  }
846 }
847 
848 /****************** PRIVATE *******************/
849 
850 template < class G, typename T_V, typename T_E >
851 void
853  std::vector< T_V > vertices) {
854  pgassert(m_num_vertices == 0);
855  for (const auto vertex : vertices) {
856  pgassert(vertices_map.find(vertex.id) == vertices_map.end());
857 
858  auto v = add_vertex(graph);
859  vertices_map[vertex.id] = m_num_vertices++;
860  graph[v].cp_members(vertex);
861 
862  pgassert(boost::num_vertices(graph) == num_vertices());
863  }
864  return;
865 }
866 
867 } // namespace graph
868 } // namespace pgrouting
869 
870 #endif // SRC_COMMON_SRC_PGR_BASE_GRAPH_HPP_
const T_E & operator[](E e_idx) const
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.
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
edge_astar_t * edges
Definition: BDATester.cpp:46
boost::graph_traits< G >::edge_iterator E_i
graphType
Definition: pgr_types.h:222
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.
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.
bool is_target(V v_idx, E e_idx) const
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
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