PGROUTING  2.5
pgrouting::graph::Pgr_base_graph< G, T_V, T_E > Class Template Reference

#include "pgr_base_graph.hpp"

Inheritance diagram for pgrouting::graph::Pgr_base_graph< G, T_V, T_E >:
Collaboration diagram for pgrouting::graph::Pgr_base_graph< G, T_V, T_E >:

Public Types

Graph related types
Type boost meaning pgRouting meaning
G boost::adjacency_list Graph
V vertex_descriptor Think of it as local ID of a vertex
E edge_descriptor Think of it as local ID of an edge
V_i vertex_iterator To cycle the vertices of the Graph
E_i edge_iterator To cycle the edges of the Graph
EO_i out_edge_iterator To cycle the out going edges of a vertex
EI_i in_edge_iterator To cycle the in coming edges of a vertex (only in bidirectional graphs)
typedef G B_G
 
typedef T_E G_T_E
 
typedef T_V G_T_V
 
typedef boost::graph_traits< G >::vertex_descriptor V
 
typedef boost::graph_traits< G >::edge_descriptor E
 
typedef boost::graph_traits< G >::vertex_iterator V_i
 
typedef boost::graph_traits< G >::edge_iterator E_i
 
typedef boost::graph_traits< G >::out_edge_iterator EO_i
 
typedef boost::graph_traits< G >::in_edge_iterator EI_i
 
typedef boost::graph_traits< G >::vertices_size_type vertices_size_type
 
typedef boost::graph_traits< G >::edges_size_type edges_size_type
 
typedef boost::graph_traits< G >::degree_size_type degree_size_type
 
Id handling related types
Type Meaning pgRouting Meaning
id_to_V maps id -> V given an id store the V
LI Left Iterator iterates over id_to_V
typedef std::map< int64_t, Vid_to_V
 
typedef id_to_V::const_iterator LI
 

Public Member Functions

int64_t get_edge_id (V from, V to, double &distance) const
 
void graph_add_edge (const T_E &edge)
 
template<typename T >
void graph_add_edge (const T &edge)
 
template<typename T >
void graph_add_edge_no_create_vertex (const T &edge)
 Use this function when the vertices are already inserted in the graph. More...
 
size_t num_vertices () const
 
Insert edges
template<typename T >
void insert_edges (const T *edges, int64_t count)
 Inserts count edges of type T into the graph. More...
 
template<typename T >
void insert_edges (T *edges, int64_t count, bool)
 
template<typename T >
void insert_edges (const std::vector< T > &edges)
 Inserts count edges of type pgr_edge_t into the graph. More...
 
boost wrappers with original id
degree_size_type out_degree (int64_t vertex_id) const
 get the out-degree of a vertex More...
 
degree_size_type in_degree (int64_t vertex_id) const
 
V get_V (const T_V &vertex)
 get the vertex descriptor of the vertex More...
 
V get_V (int64_t vid) const
 get the vertex descriptor of the vid More...
 
bool has_vertex (int64_t vid) const
 True when vid is in the graph. More...
 
to be or not to be
bool is_directed () const
 
bool is_undirected () const
 
bool is_source (V v_idx, E e_idx) const
 
bool is_target (V v_idx, E e_idx) const
 
boost wrappers with V
T_E & operator[] (E e_idx)
 
const T_E & operator[] (E e_idx) const
 
T_V & operator[] (V v_idx)
 
const T_V & operator[] (V v_idx) const
 
V source (E e_idx) const
 
V target (E e_idx) const
 
V adjacent (V v_idx, E e_idx) const
 
degree_size_type in_degree (V &v) const
 in degree of a vertex More...
 
degree_size_type out_degree (V &v) const
 out degree of a vertex More...
 
edge disconection/reconnection
void disconnect_edge (int64_t p_from, int64_t p_to)
 Disconnects all edges from p_from to p_to. More...
 
void disconnect_out_going_edge (int64_t vertex_id, int64_t edge_id)
 Disconnects the outgoing edges of a vertex. More...
 
void disconnect_vertex (int64_t p_vertex)
 Disconnects all incoming and outgoing edges from the vertex. More...
 
void disconnect_vertex (V vertex)
 
void restore_graph ()
 Reconnects all edges that were removed. More...
 

Public Attributes

Graph Modification
std::deque< T_E > removed_edges
 Used for storing the removed_edges. More...
 

Private Member Functions

void add_vertices (std::vector< T_V > vertices)
 adds the vertices into the graph More...
 

Friends

only for stand by program
std::ostream & operator<< (std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g)
 

The Graph

graph
 The graph. More...
 
size_t m_num_vertices
 local count. More...
 
graphType m_gType
 type (DIRECTED or UNDIRECTED) More...
 
 Pgr_base_graph (const std::vector< T_V > &vertices, graphType gtype)
 Constructor. More...
 
 Pgr_base_graph (graphType gtype)
 Prepares the graph to be of type gtype with 0 vertices. More...
 

Id mapping handling

typedef std::map< V, size_t > IndexMap
 
id_to_V vertices_map
 id -> graph id More...
 
boost::property_map< G, boost::vertex_index_t >::type vertIndex
 
IndexMap mapIndex
 
boost::associative_property_map< IndexMappropmapIndex
 

Detailed Description

template<class G, typename T_V, typename T_E>
class pgrouting::graph::Pgr_base_graph< G, T_V, T_E >

Definition at line 215 of file pgr_base_graph.hpp.

Member Typedef Documentation

template<class G, typename T_V, typename T_E>
typedef G pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::B_G

Definition at line 273 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::degree_size_type

Definition at line 288 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::edge_descriptor pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::E

Definition at line 277 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::edge_iterator pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::E_i

Definition at line 279 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::edges_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::edges_size_type

Definition at line 286 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::in_edge_iterator pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::EI_i

Definition at line 281 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::out_edge_iterator pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::EO_i

Definition at line 280 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef T_E pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::G_T_E

Definition at line 274 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef T_V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::G_T_V

Definition at line 275 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef std::map< int64_t, V > pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::id_to_V

Definition at line 300 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef std::map<V, size_t> pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::IndexMap

Definition at line 319 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef id_to_V::const_iterator pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::LI

Definition at line 301 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::vertex_descriptor pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::V

Definition at line 276 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::vertex_iterator pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::V_i

Definition at line 278 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::vertices_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::vertices_size_type

Definition at line 284 of file pgr_base_graph.hpp.

Constructor & Destructor Documentation

template<class G, typename T_V, typename T_E>
pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::Pgr_base_graph ( const std::vector< T_V > &  vertices,
graphType  gtype 
)
inline

Constructor.

  • Prepares the graph to be of type gtype
  • inserts the vertices
  • The vertices must be checked (if necessary) before calling the constructor

Definition at line 343 of file pgr_base_graph.hpp.

References pgrouting::check_vertices(), and pgassert.

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  }
boost::associative_property_map< IndexMap > propmapIndex
boost::property_map< G, boost::vertex_index_t >::type vertIndex
graphType m_gType
type (DIRECTED or UNDIRECTED)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id
size_t check_vertices(std::vector< Basic_vertex > vertices)
bool has_vertex(int64_t vid) const
True when vid is in the graph.

Here is the call graph for this function:

template<class G, typename T_V, typename T_E>
pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::Pgr_base_graph ( graphType  gtype)
inlineexplicit

Prepares the graph to be of type gtype with 0 vertices.

Definition at line 378 of file pgr_base_graph.hpp.

379  : graph(0),
380  m_num_vertices(0),
381  m_gType(gtype),
382  vertIndex(boost::get(boost::vertex_index, graph)),
384  }
boost::associative_property_map< IndexMap > propmapIndex
boost::property_map< G, boost::vertex_index_t >::type vertIndex
graphType m_gType
type (DIRECTED or UNDIRECTED)

Member Function Documentation

template<class G, typename T_V, typename T_E>
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::add_vertices ( std::vector< T_V >  vertices)
inlineprivate

adds the vertices into the graph

PRECONDITIONS:

  • The graph has not being initialized before
  • There are no dupicated vertices
precondition(boost::num_vertices(graph) == 0);
for (vertex : vertices)
precondition(!has_vertex(vertex.id));

POSTCONDITIONS:

postcondition(boost::num_vertices(graph) == vertices.size());
for (vertex : vertices)
postcondition(has_vertex(vertex.id));

Example use:

pgrouting::DirectedGraph digraph(gType);
auto vertices(pgrouting::extract_vertices(data_edges, total_edges));
digraph.add_vertices(vertices);

Definition at line 476 of file pgr_base_graph.hpp.

References pgassert.

477  {
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  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id
bool has_vertex(int64_t vid) const
True when vid is in the graph.
template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::adjacent ( V  v_idx,
E  e_idx 
) const
inline

Definition at line 579 of file pgr_base_graph.hpp.

References pgassert.

579  {
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  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
bool is_source(V v_idx, E e_idx) const
bool is_target(V v_idx, E e_idx) const
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::disconnect_edge ( int64_t  p_from,
int64_t  p_to 
)

Disconnects all edges from p_from to p_to.

  • No edge is disconnected if the vertices id's do not exist in the graph
  • All removed edges are stored for future reinsertion
  • All parallel edges are disconnected (automatically by boost)
disconnectEdgeUndirected.png
disconnect_edge(2,3) on an UNDIRECTED graph
disconnectEdgeDirected.png
disconnect_edge(2,3) on a DIRECTED graph
Parameters
[in]p_fromoriginal vertex id of the starting point of the edge
[in]p_tooriginal vertex id of the ending point of the edge

Definition at line 748 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::get_postgres_results_directed().

748  {
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 }
boost::graph_traits< G >::out_edge_iterator EO_i
std::deque< T_E > removed_edges
Used for storing the removed_edges.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
boost::graph_traits< G >::vertex_descriptor V

Here is the caller graph for this function:

template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::disconnect_out_going_edge ( int64_t  vertex_id,
int64_t  edge_id 
)

Disconnects the outgoing edges of a vertex.

  • No edge is disconnected if it doesn't exist in the graph
  • Removed edges are stored for future reinsertion
  • all outgoing edges with the edge_id are removed if they exist
Parameters
[in]vertex_idoriginal vertex
[in]edge_idoriginal edge_id

Definition at line 777 of file pgr_base_graph.hpp.

778  {
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 }
boost::graph_traits< G >::out_edge_iterator EO_i
std::deque< T_E > removed_edges
Used for storing the removed_edges.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::disconnect_vertex ( int64_t  p_vertex)

Disconnects all incoming and outgoing edges from the vertex.

boost::graph doesn't recommend th to insert/remove vertices, so a vertex removal is simulated by disconnecting the vertex from the graph

  • No edge is disconnected if the vertices id's do not exist in the graph
  • All removed edges are stored for future reinsertion
  • All parallel edges are disconnected (automatically by boost)
disconnectVertexUndirected.png
disconnect_vertex(2) on an UNDIRECTED graph
disconnectVertexDirected.png
disconnect_vertex(2) on a DIRECTED graph
Parameters
[in]p_vertexoriginal vertex id of the starting point of the edge

Definition at line 809 of file pgr_base_graph.hpp.

809  {
810  if (!has_vertex(vertex)) return;
812 }
void disconnect_vertex(int64_t p_vertex)
Disconnects all incoming and outgoing edges from the vertex.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::disconnect_vertex ( V  vertex)

Definition at line 816 of file pgr_base_graph.hpp.

References DIRECTED.

816  {
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 }
boost::graph_traits< G >::out_edge_iterator EO_i
std::deque< T_E > removed_edges
Used for storing the removed_edges.
graphType m_gType
type (DIRECTED or UNDIRECTED)
boost::graph_traits< G >::in_edge_iterator EI_i
template<class G , typename T_V , typename T_E >
int64_t pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_edge_id ( V  from,
V  to,
double &  distance 
) const

Definition at line 859 of file pgr_base_graph.hpp.

862  {
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 }
boost::graph_traits< G >::out_edge_iterator EO_i
boost::graph_traits< G >::vertex_descriptor V
boost::graph_traits< G >::edge_descriptor E
template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_V ( const T_V &  vertex)
inline

get the vertex descriptor of the vertex

When the vertex does not exist

  • creates a new vetex
Returns
V: The vertex descriptor of the vertex

Definition at line 527 of file pgr_base_graph.hpp.

Referenced by do_pgr_test_c_edges(), and pgrouting::graph::Pgr_componentsGraph< G, T_V, T_E >::graph_add_edge().

527  {
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  }
boost::associative_property_map< IndexMap > propmapIndex
id_to_V vertices_map
id -> graph id

Here is the caller graph for this function:

template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_V ( int64_t  vid) const
inline

get the vertex descriptor of the vid

Call has_vertex(vid) before calling this function

Returns
V: The vertex descriptor of the vertex

Definition at line 545 of file pgr_base_graph.hpp.

References pgassert.

545  {
546  pgassert(has_vertex(vid));
547  return vertices_map.find(vid)->second;
548  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id
bool has_vertex(int64_t vid) const
True when vid is in the graph.
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph_add_edge ( const T_E &  edge)

Definition at line 889 of file pgr_base_graph.hpp.

889  {
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()) {
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()) {
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 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
id_to_V vertices_map
id -> graph id
long target
Definition: trsp.h:34
boost::graph_traits< G >::edge_descriptor E
long source
Definition: trsp.h:33
template<class G , typename T_V , typename T_E >
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph_add_edge ( const T &  edge)

Definition at line 917 of file pgr_base_graph.hpp.

References pgassert.

917  {
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 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
long id
Definition: trsp.h:32
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id
long target
Definition: trsp.h:34
float8 reverse_cost
Definition: trsp.h:36
boost::graph_traits< G >::edge_descriptor E
long source
Definition: trsp.h:33
template<class G, typename T_V, typename T_E>
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph_add_edge_no_create_vertex ( const T &  edge)
inline

Use this function when the vertices are already inserted in the graph.

Definition at line 707 of file pgr_base_graph.hpp.

References pgassert, and pgassertwm.

707  {
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());
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  }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
long id
Definition: trsp.h:32
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id
long target
Definition: trsp.h:34
bool has_vertex(int64_t vid) const
True when vid is in the graph.
float8 reverse_cost
Definition: trsp.h:36
boost::graph_traits< G >::edge_descriptor E
long source
Definition: trsp.h:33
template<class G, typename T_V, typename T_E>
bool pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::has_vertex ( int64_t  vid) const
inline

True when vid is in the graph.

Definition at line 551 of file pgr_base_graph.hpp.

551  {
552  return vertices_map.find(vid) != vertices_map.end();
553  }
id_to_V vertices_map
id -> graph id
template<class G, typename T_V, typename T_E>
degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::in_degree ( int64_t  vertex_id) const
inline

Definition at line 510 of file pgr_base_graph.hpp.

510  {
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  }
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
degree_size_type in_degree(int64_t vertex_id) const
bool has_vertex(int64_t vid) const
True when vid is in the graph.
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
template<class G, typename T_V, typename T_E>
degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::in_degree ( V v) const
inline

in degree of a vertex

  • when its undirected there is no "concept" of in degree
    • out degree is returned
  • on directed in degree of vertex is returned

Definition at line 593 of file pgr_base_graph.hpp.

593  {
594  return is_directed()?
595  boost::in_degree(v, graph) :
596  boost::out_degree(v, graph);
597  }
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
template<class G, typename T_V, typename T_E>
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::insert_edges ( const T *  edges,
int64_t  count 
)
inline

Inserts count edges of type T into the graph.

Converts the edges to a std::vector<T> & calls the overloaded twin function.

Parameters
edges
count

Definition at line 398 of file pgr_base_graph.hpp.

Referenced by do_pgr_astarManyToMany(), do_pgr_bdAstar(), do_pgr_bdDijkstra(), do_pgr_dijkstraTRSP(), do_pgr_dijkstraVia(), do_pgr_driving_many_to_dist(), do_pgr_floydWarshall(), do_pgr_johnson(), do_pgr_ksp(), do_pgr_lineGraph(), do_pgr_many_to_many_dijkstra(), do_pgr_many_withPointsDD(), do_pgr_strongComponents(), do_pgr_test_c_edges(), do_pgr_testXYedges(), do_pgr_withPoints(), and do_pgr_withPointsKsp().

398  {
399  insert_edges(std::vector < T >(edges, edges + count));
400  }
static edge_t edges[22573]
void insert_edges(const T *edges, int64_t count)
Inserts count edges of type T into the graph.

Here is the caller graph for this function:

template<class G, typename T_V, typename T_E>
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::insert_edges ( T *  edges,
int64_t  count,
bool   
)
inline

Definition at line 403 of file pgr_base_graph.hpp.

References pgassert.

403  {
404  for (int64_t i = 0; i < count; ++i) {
408  }
409  }
void graph_add_edge_no_create_vertex(const T &edge)
Use this function when the vertices are already inserted in the graph.
static edge_t edges[22573]
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
bool has_vertex(int64_t vid) const
True when vid is in the graph.
template<class G, typename T_V, typename T_E>
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::insert_edges ( const std::vector< T > &  edges)
inline

Inserts count edges of type pgr_edge_t into the graph.

The set of edges should not have an illegal vertex defined

When the graph is empty calls:

  • extract_vertices and throws an exception if there are illegal vertices.

When developing:

  • if an illegal vertex is found an exception is thrown
  • That means that the set of vertices should be checked in the code that is being developed

No edge is inserted when there is an error on the vertices

Parameters
edges

Definition at line 431 of file pgr_base_graph.hpp.

References pgrouting::check_vertices(), pgrouting::extract_vertices(), and pgassert.

431  {
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  }
Definition: trsp.h:31
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)
void add_vertices(std::vector< T_V > vertices)
adds the vertices into the graph
size_t check_vertices(std::vector< Basic_vertex > vertices)

Here is the call graph for this function:

template<class G, typename T_V, typename T_E>
bool pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_directed ( ) const
inline

Definition at line 560 of file pgr_base_graph.hpp.

References DIRECTED.

560 {return m_gType == DIRECTED;}
graphType m_gType
type (DIRECTED or UNDIRECTED)
template<class G, typename T_V, typename T_E>
bool pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_source ( V  v_idx,
E  e_idx 
) const
inline

Definition at line 562 of file pgr_base_graph.hpp.

562 {return v_idx == source(e_idx);}
template<class G, typename T_V, typename T_E>
bool pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_target ( V  v_idx,
E  e_idx 
) const
inline

Definition at line 563 of file pgr_base_graph.hpp.

563 {return v_idx == target(e_idx);}
template<class G, typename T_V, typename T_E>
bool pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_undirected ( ) const
inline

Definition at line 561 of file pgr_base_graph.hpp.

References UNDIRECTED.

561 {return m_gType == UNDIRECTED;}
graphType m_gType
type (DIRECTED or UNDIRECTED)
template<class G, typename T_V, typename T_E>
size_t pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::num_vertices ( ) const
inline

Definition at line 696 of file pgr_base_graph.hpp.

696 { return boost::num_vertices(graph);}
template<class G, typename T_V, typename T_E>
T_E& pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::operator[] ( E  e_idx)
inline

Definition at line 571 of file pgr_base_graph.hpp.

571 {return graph[e_idx];}
template<class G, typename T_V, typename T_E>
const T_E& pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::operator[] ( E  e_idx) const
inline

Definition at line 572 of file pgr_base_graph.hpp.

572 {return graph[e_idx];}
template<class G, typename T_V, typename T_E>
T_V& pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::operator[] ( V  v_idx)
inline

Definition at line 574 of file pgr_base_graph.hpp.

574 {return graph[v_idx];}
template<class G, typename T_V, typename T_E>
const T_V& pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::operator[] ( V  v_idx) const
inline

Definition at line 575 of file pgr_base_graph.hpp.

575 {return graph[v_idx];}
template<class G, typename T_V, typename T_E>
degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::out_degree ( int64_t  vertex_id) const
inline

get the out-degree of a vertex

Returns
0: The out degree of a vertex that its not in the graph
Parameters
[in]vertex_idoriginal vertex id

Definition at line 504 of file pgr_base_graph.hpp.

504  {
505  if (!has_vertex(vertex_id)) {
506  return 0;
507  }
508  return out_degree(get_V(vertex_id));
509  }
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
template<class G, typename T_V, typename T_E>
degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::out_degree ( V v) const
inline

out degree of a vertex

regardles of undirected or directed graph

  • out degree is returned

Definition at line 604 of file pgr_base_graph.hpp.

604  {
605  return boost::out_degree(v, graph);
606  }
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::restore_graph ( )

Reconnects all edges that were removed.

Definition at line 849 of file pgr_base_graph.hpp.

849  {
850  while (removed_edges.size() != 0) {
852  removed_edges.pop_front();
853  }
854 }
std::deque< T_E > removed_edges
Used for storing the removed_edges.
void graph_add_edge(const T_E &edge)
template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::source ( E  e_idx) const
inline

Definition at line 577 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::create_edges().

577 {return boost::source(e_idx, graph);}

Here is the caller graph for this function:

template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::target ( E  e_idx) const
inline

Definition at line 578 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::create_edges().

578 {return boost::target(e_idx, graph);}

Here is the caller graph for this function:

Friends And Related Function Documentation

template<class G, typename T_V, typename T_E>
std::ostream& operator<< ( std::ostream &  log,
const Pgr_base_graph< G, T_V, T_E > &  g 
)
friend

Definition at line 670 of file pgr_base_graph.hpp.

671  {
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  }
boost::graph_traits< G >::out_edge_iterator EO_i

Member Data Documentation

template<class G, typename T_V, typename T_E>
G pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph

The graph.

Definition at line 307 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::create_edges().

template<class G, typename T_V, typename T_E>
graphType pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::m_gType

type (DIRECTED or UNDIRECTED)

Definition at line 309 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
size_t pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::m_num_vertices

local count.

Definition at line 308 of file pgr_base_graph.hpp.

Referenced by do_pgr_lineGraph().

template<class G, typename T_V, typename T_E>
IndexMap pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::mapIndex

Definition at line 320 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
boost::associative_property_map<IndexMap> pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::propmapIndex

Definition at line 321 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
std::deque< T_E > pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::removed_edges

Used for storing the removed_edges.

Definition at line 329 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
id_to_V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::vertices_map

id -> graph id

Definition at line 315 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
boost::property_map<G, boost::vertex_index_t>::type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::vertIndex

Definition at line 317 of file pgr_base_graph.hpp.


The documentation for this class was generated from the following file: