pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgrouting::graph::Pgr_base_graph< G, Vertex, Edge > Class Template Reference

#include "pgr_base_graph.hpp"

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 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)
 
size_t num_vertices () const
 
T_V operator[] (V v) const
 
Insert data
template<typename T >
void graph_insert_data (const T *edges, int64_t count)
 Inserts count edges of type T into the graph. More...
 
template<typename T >
void graph_insert_data (const std::vector< T > &edges)
 Inserts count edges of type pgr_edge_t into the graph. More...
 
boost wrappers
degree_size_type out_degree (int64_t vertex_id) const
 get the out-degree of a vertex More...
 
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...
 
degree_size_type in_degree (V &v) const
 True when vid is in the graph. More...
 
degree_size_type out_degree (V &v) const
 True when vid is in the graph. 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

Id mapping handling
id_to_V vertices_map
 id -> graph id More...
 
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...
 

Detailed Description

template<class G, typename Vertex, typename Edge>
class pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >

Definition at line 223 of file pgr_base_graph.hpp.

Member Typedef Documentation

template<class G, typename Vertex, typename Edge>
typedef G pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::B_G

Definition at line 295 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
typedef boost::graph_traits< G >::degree_size_type pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::degree_size_type

Definition at line 308 of file pgr_base_graph.hpp.

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

Definition at line 297 of file pgr_base_graph.hpp.

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

Definition at line 299 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
typedef boost::graph_traits< G >::edges_size_type pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::edges_size_type

Definition at line 306 of file pgr_base_graph.hpp.

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

Definition at line 301 of file pgr_base_graph.hpp.

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

Definition at line 300 of file pgr_base_graph.hpp.

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

Definition at line 320 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
typedef id_to_V::const_iterator pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::LI

Definition at line 321 of file pgr_base_graph.hpp.

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

Definition at line 296 of file pgr_base_graph.hpp.

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

Definition at line 298 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
typedef boost::graph_traits< G >::vertices_size_type pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::vertices_size_type

Definition at line 304 of file pgr_base_graph.hpp.

Constructor & Destructor Documentation

template<class G, typename Vertex, typename Edge>
pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::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 357 of file pgr_base_graph.hpp.

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

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

Definition at line 379 of file pgr_base_graph.hpp.

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)
private

adds the vertices into the graph

PRECONDITIONS:

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)
precondition(has_vertex(vertex.id));

Definition at line 827 of file pgr_base_graph.hpp.

References pgassert.

Referenced by pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph_insert_data().

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 621 of file pgr_base_graph.hpp.

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 650 of file pgr_base_graph.hpp.

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 682 of file pgr_base_graph.hpp.

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 689 of file pgr_base_graph.hpp.

References DIRECTED.

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 732 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
V pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::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 478 of file pgr_base_graph.hpp.

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

template<class G, typename Vertex, typename Edge>
V pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::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 495 of file pgr_base_graph.hpp.

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)
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 790 of file pgr_base_graph.hpp.

References pgassert.

template<class G, typename Vertex, typename Edge>
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph_insert_data ( 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 419 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
bool pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::has_vertex ( int64_t  vid) const
inline
template<class G, typename Vertex, typename Edge>
degree_size_type pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::in_degree ( V v) const
inline

True when vid is in the graph.

Definition at line 506 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
size_t pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::num_vertices ( ) const
inline
template<class G, typename Vertex, typename Edge>
T_V pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::operator[] ( V  v) const
inline

Definition at line 605 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
degree_size_type pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::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 463 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::out_degree().

template<class G, typename Vertex, typename Edge>
degree_size_type pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::out_degree ( V v) const
inline

True when vid is in the graph.

Definition at line 511 of file pgr_base_graph.hpp.

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 722 of file pgr_base_graph.hpp.

Friends And Related Function Documentation

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

Definition at line 577 of file pgr_base_graph.hpp.

Member Data Documentation

template<class G, typename Vertex, typename Edge>
graphType pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::m_gType

type (DIRECTED or UNDIRECTED)

Definition at line 329 of file pgr_base_graph.hpp.

template<class G, typename Vertex, typename Edge>
size_t pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::m_num_vertices

local count.

Definition at line 328 of file pgr_base_graph.hpp.

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

Used for storing the removed_edges.

Definition at line 343 of file pgr_base_graph.hpp.


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