PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E > Class Template Reference

#include "pgr_contractionGraph.hpp"

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

Public Types

typedef boost::graph_traits< G >
::degree_size_type 
degree_size_type
 
typedef boost::graph_traits< G >
::edge_descriptor 
E
 
typedef boost::graph_traits< G >
::edge_iterator 
E_i
 
typedef boost::graph_traits< G >
::in_edge_iterator 
EI_i
 
typedef boost::graph_traits< G >
::out_edge_iterator 
EO_i
 
typedef boost::graph_traits< G >
::vertex_descriptor 
V
 
typedef boost::graph_traits< G >
::vertex_iterator 
V_i
 
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 >
::vertices_size_type 
vertices_size_type
 
typedef boost::graph_traits< G >
::edges_size_type 
edges_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

 Pgr_contractionGraph (graphType gtype)
 Prepares the graph to be of type gtype More...
 
void add_contracted_edge_vertices (V v, T_E &e)
 add the contracted vertices of an edge e to the vertex v More...
 
void add_shortcut (const T_E &edge)
 add edges(shortuct) to the graph during contraction More...
 
Identifiers< Vfind_adjacent_vertices (V v) const
 get the vertex descriptors of adjacent vertices of v More...
 
Identifiers< int64_t > get_changed_vertices ()
 vertices with at least one contracted vertex More...
 
std::vector< int64_t > get_contracted_vertices (int64_t vid)
 get the contracted vertex ids of a given vertex in array format More...
 
int64_t get_edge_id (V from, V to, double &distance) const
 
std::vector< int64_t > get_ids (Identifiers< int64_t > boost_ids) const
 
E get_min_cost_edge (V source, V destination)
 get the edge with minimum cost between two vertices More...
 
void graph_add_edge (const T_E &edge)
 
void graph_add_edge (const T &edge)
 
void graph_add_edge_no_create_vertex (const T &edge)
 Use this function when the vertices are already inserted in the graph. More...
 
degree_size_type in_degree_from_vertex (V vertex, V neighbor)
 The number of edges from neighbor to vertex. More...
 
size_t num_vertices () const
 
degree_size_type out_degree_to_vertex (V vertex, V neighbor)
 The number of edges from vertex to neighbor. More...
 
void print_graph (std::ostringstream &log)
 print the graph with contracted vertices of all vertices and edges More...
 
Insert edges
void insert_edges (const T *edges, int64_t count)
 Inserts count edges of type T into the graph. More...
 
void insert_edges (T *edges, int64_t count, bool)
 
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...
 
boost wrappers with V
degree_size_type out_degree (V &v) const
 out degree of a vertex More...
 
degree_size_type in_degree (V &v) const
 in degree of a vertex More...
 
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
 
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
 
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...
 

Static Public Member Functions

static bool compareById (const T_E &edge1, const T_E &edge2)
 Binary function that accepts two elements , and returns a value convertible to bool. More...
 

Public Attributes

Identifiers< Vremoved_vertices
 
std::vector< T_E > shortcuts
 
The Graph
graph
 The graph. More...
 
size_t m_num_vertices
 local count. More...
 
graphType m_gType
 type (DIRECTED or UNDIRECTED) More...
 
Graph Modification
std::deque< T_E > removed_edges
 Used for storing the removed_edges. 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
< IndexMap
propmapIndex
 

Detailed Description

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

Definition at line 48 of file pgr_contractionGraph.hpp.

Member Typedef Documentation

typedef G pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::B_G
inherited

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_contractionGraph< G, T_V, T_E >::degree_size_type

Definition at line 75 of file pgr_contractionGraph.hpp.

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

Definition at line 69 of file pgr_contractionGraph.hpp.

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

Definition at line 71 of file pgr_contractionGraph.hpp.

typedef boost::graph_traits< G >::edges_size_type pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::edges_size_type
inherited

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_contractionGraph< G, T_V, T_E >::EI_i

Definition at line 73 of file pgr_contractionGraph.hpp.

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

Definition at line 72 of file pgr_contractionGraph.hpp.

typedef T_E pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::G_T_E
inherited

Definition at line 274 of file pgr_base_graph.hpp.

typedef T_V pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::G_T_V
inherited

Definition at line 275 of file pgr_base_graph.hpp.

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

Definition at line 300 of file pgr_base_graph.hpp.

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

Definition at line 319 of file pgr_base_graph.hpp.

typedef id_to_V::const_iterator pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::LI
inherited

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_contractionGraph< G, T_V, T_E >::V

Definition at line 68 of file pgr_contractionGraph.hpp.

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

Definition at line 70 of file pgr_contractionGraph.hpp.

typedef boost::graph_traits< G >::vertices_size_type pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::vertices_size_type
inherited

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_contractionGraph< G, T_V, T_E >::Pgr_contractionGraph ( graphType  gtype)
inlineexplicit

Prepares the graph to be of type gtype

Definition at line 90 of file pgr_contractionGraph.hpp.

91  : Pgr_base_graph< G , T_V, T_E >(gtype) {
92  }

Member Function Documentation

template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::add_contracted_edge_vertices ( V  v,
T_E &  e 
)
inline

add the contracted vertices of an edge e to the vertex v

Parameters
[in]vvertex_descriptor
[in]eEdge of type T_E

Definition at line 252 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph.

252  {
253  for (auto vid : e.contracted_vertices()) {
254  this->graph[v].add_vertex_id(vid);
255  }
256  e.clear_contracted_vertices();
257  }
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::add_shortcut ( const T_E &  edge)
inline

add edges(shortuct) to the graph during contraction

a -> b -> c

a -> c

edge (a, c) is a new edge e e.contracted_vertices = b + b.contracted vertices b is "removed" disconnected from the graph

  • by removing all edges to/from b
Parameters
[in]edgeof type T_E is to be added

Definition at line 275 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_V(), pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, pgassert, pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::shortcuts, and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::vertices_map.

275  {
276  std::ostringstream log;
277  bool inserted;
278  E e;
279  if (edge.cost < 0)
280  return;
281 
282  pgassert(this->vertices_map.find(edge.source)
283  != this->vertices_map.end());
284  pgassert(this->vertices_map.find(edge.target)
285  != this->vertices_map.end());
286 
287  auto vm_s = this->get_V(edge.source);
288  auto vm_t = this->get_V(edge.target);
289 
290  boost::tie(e, inserted) =
291  boost::add_edge(vm_s, vm_t, this->graph);
292 
293  this->graph[e].cp_members(edge);
294 
295  shortcuts.push_back(edge);
296  }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
boost::graph_traits< G >::edge_descriptor E
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
long target
Definition: trsp.h:34
long source
Definition: trsp.h:33

Here is the call graph for this function:

V pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::adjacent ( V  v_idx,
E  e_idx 
) const
inlineinherited
template<class G , typename T_V , typename T_E >
static bool pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::compareById ( const T_E &  edge1,
const T_E &  edge2 
)
inlinestatic

Binary function that accepts two elements , and returns a value convertible to bool.

Used as a compare function to sort the edges in increasing order of edge id

Definition at line 83 of file pgr_contractionGraph.hpp.

83  {
84  return edge1.id > edge2.id;
85  }
void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::disconnect_edge ( int64_t  p_from,
int64_t  p_to 
)
inherited

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
void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::disconnect_out_going_edge ( int64_t  vertex_id,
int64_t  edge_id 
)
inherited

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
void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::disconnect_vertex ( int64_t  p_vertex)
inherited

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
void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::disconnect_vertex ( V  vertex)
inherited
template<class G , typename T_V , typename T_E >
Identifiers<V> pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::find_adjacent_vertices ( V  v) const
inline

get the vertex descriptors of adjacent vertices of v

Parameters
[in]vvertex_descriptor
Returns
Identifiers<V>: The set of vertex descriptors adjacent to the given vertex v

Definition at line 98 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::adjacent(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph.

98  {
99  EO_i out, out_end;
100  EI_i in, in_end;
101  Identifiers<V> adjacent_vertices;
102 
103  for (boost::tie(out, out_end) = out_edges(v, this->graph);
104  out != out_end; ++out) {
105  adjacent_vertices += this->adjacent(v, *out);
106  }
107  for (boost::tie(in, in_end) = in_edges(v, this->graph);
108  in != in_end; ++in) {
109  adjacent_vertices += this->adjacent(v, *in);
110  }
111  return adjacent_vertices;
112  }
boost::graph_traits< G >::out_edge_iterator EO_i
boost::graph_traits< G >::in_edge_iterator EI_i

Here is the call graph for this function:

template<class G , typename T_V , typename T_E >
Identifiers<int64_t> pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::get_changed_vertices ( )
inline

vertices with at least one contracted vertex

Returns
The vids Identifiers with at least one contracted vertex

Definition at line 130 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, Identifiers< T >::has(), and pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::removed_vertices.

130  {
132  for (auto vi = vertices(this->graph).first;
133  vi != vertices(this->graph).second;
134  ++vi) {
135  if (!removed_vertices.has(*vi)
136  && this->graph[*vi].has_contracted_vertices()) {
137  vids += this->graph[*vi].id;
138  }
139  }
140  return vids;
141  }
bool has(const T other) const
true ids() has element
Definition: identifiers.hpp:97

Here is the call graph for this function:

template<class G , typename T_V , typename T_E >
std::vector<int64_t> pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::get_contracted_vertices ( int64_t  vid)
inline

get the contracted vertex ids of a given vertex in array format

Parameters
[in]vidvertex_id
Returns
ids of contracted_vertices

Definition at line 232 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_V(), pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::has_vertex().

232  {
233  if (!this->has_vertex(vid)) return std::vector<int64_t>();
234  auto v = this->get_V(vid);
235  std::vector<int64_t> ids(this->graph[v].contracted_vertices().size());
236 
237  size_t count = 0;
238  for (auto idx : this->graph[v].contracted_vertices()) {
239  ids[count++] = this->graph[idx].id;
240  }
241  return ids;
242  }
bool has_vertex(int64_t vid) const
True when vid is in the graph.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex

Here is the call graph for this function:

int64_t pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::get_edge_id ( V  from,
V  to,
double &  distance 
) const
inherited
template<class G , typename T_V , typename T_E >
std::vector<int64_t> pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::get_ids ( Identifiers< int64_t >  boost_ids) const
inline

Definition at line 115 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, and Identifiers< T >::size().

116  {
117  std::vector<int64_t> ids(boost_ids.size());
118  size_t count = 0;
119  for (auto id : boost_ids) {
120  ids[count++] = this->graph[id].id;
121  }
122  return ids;
123  }
size_t size() const
Definition: identifiers.hpp:77

Here is the call graph for this function:

template<class G , typename T_V , typename T_E >
E pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::get_min_cost_edge ( V  source,
V  destination 
)
inline

get the edge with minimum cost between two vertices

Parameters
[in]sourcevertex_descriptor of source vertex
[in]destinationvertex_descriptor of target vertex
Returns
E: The edge descriptor of the edge with minimum cost

Definition at line 149 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::target().

149  {
150  EO_i out_i, out_end;
151  E min_cost_edge;
152  double min_cost = (std::numeric_limits<double>::max)();
153  for (boost::tie(out_i, out_end) =
154  boost::out_edges(source, this->graph);
155  out_i != out_end; ++out_i) {
156  auto e = *out_i;
157  if (this->target(e) == destination) {
158  if (this->graph[e].cost < min_cost) {
159  min_cost = this->graph[e].cost;
160  min_cost_edge = e;
161  }
162  }
163  }
164  return min_cost_edge;
165  }
boost::graph_traits< G >::edge_descriptor E
boost::graph_traits< G >::out_edge_iterator EO_i

Here is the call graph for this function:

V pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::get_V ( const T_V &  vertex)
inlineinherited

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.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph, pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::m_num_vertices, pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::propmapIndex, and pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::vertices_map.

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::add_shortcut(), and pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::get_contracted_vertices().

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

Here is the caller graph for this function:

V pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::get_V ( int64_t  vid) const
inlineinherited

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 pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::has_vertex(), pgassert, and pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::vertices_map.

545  {
546  pgassert(has_vertex(vid));
547  return vertices_map.find(vid)->second;
548  }
bool has_vertex(int64_t vid) const
True when vid is in the graph.
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81

Here is the call graph for this function:

void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::graph_add_edge ( const T_E &  edge)
inherited
void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::graph_add_edge ( const T &  edge)
inherited
void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::graph_add_edge_no_create_vertex ( const T &  edge)
inlineinherited

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

Definition at line 707 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::get_V(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph, pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::has_vertex(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::is_directed(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::is_undirected(), pgassert, pgassertwm, and pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::vertices_map.

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

Here is the call graph for this function:

bool pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::has_vertex ( int64_t  vid) const
inlineinherited

True when vid is in the graph.

Definition at line 551 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::vertices_map.

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::get_contracted_vertices().

551  {
552  return vertices_map.find(vid) != vertices_map.end();
553  }

Here is the caller graph for this function:

degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::in_degree ( int64_t  vertex_id) const
inlineinherited

Definition at line 510 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::get_V(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::has_vertex(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::in_degree(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::is_directed(), and pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::out_degree().

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  }
bool has_vertex(int64_t vid) const
True when vid is in the graph.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
degree_size_type in_degree(int64_t vertex_id) const
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex

Here is the call graph for this function:

degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::in_degree ( V v) const
inlineinherited

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.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph, and pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::is_directed().

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

Here is the call graph for this function:

template<class G , typename T_V , typename T_E >
degree_size_type pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::in_degree_from_vertex ( V  vertex,
V  neighbor 
)
inline

The number of edges from neighbor to vertex.

Parameters
[in]vertexis the target of the edges
[in]neighboris the source of the edges
Returns
degree_size_type: The in-degree of vertex from neighbor

Definition at line 173 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::out_degree_to_vertex().

173  {
174  return out_degree_to_vertex(neighbor, vertex);
175  }
degree_size_type out_degree_to_vertex(V vertex, V neighbor)
The number of edges from vertex to neighbor.

Here is the call graph for this function:

void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::insert_edges ( const T *  edges,
int64_t  count 
)
inlineinherited

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.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::insert_edges().

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 call graph for this function:

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

Definition at line 403 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph_add_edge_no_create_vertex(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::has_vertex(), pgassert, pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::source(), and pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::target().

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

Here is the call graph for this function:

void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::insert_edges ( const std::vector< T > &  edges)
inlineinherited

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::graph::Pgr_base_graph< G, Vertex, Edge >::add_vertices(), pgrouting::check_vertices(), pgrouting::extract_vertices(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph_add_edge(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::num_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 add_vertices(std::vector< T_V > vertices)
adds the vertices into the graph
#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)
size_t check_vertices(std::vector< Basic_vertex > vertices)

Here is the call graph for this function:

bool pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::is_directed ( ) const
inlineinherited

Definition at line 560 of file pgr_base_graph.hpp.

References DIRECTED, and pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::m_gType.

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::out_degree_to_vertex().

560 {return m_gType == DIRECTED;}
graphType m_gType
type (DIRECTED or UNDIRECTED)

Here is the caller graph for this function:

bool pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::is_source ( V  v_idx,
E  e_idx 
) const
inlineinherited

Definition at line 562 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::source().

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::out_degree_to_vertex().

562 {return v_idx == source(e_idx);}

Here is the call graph for this function:

Here is the caller graph for this function:

bool pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::is_target ( V  v_idx,
E  e_idx 
) const
inlineinherited

Definition at line 563 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::target().

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::out_degree_to_vertex().

563 {return v_idx == target(e_idx);}

Here is the call graph for this function:

Here is the caller graph for this function:

bool pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::is_undirected ( ) const
inlineinherited

Definition at line 561 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::m_gType, and UNDIRECTED.

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::out_degree_to_vertex().

561 {return m_gType == UNDIRECTED;}
graphType m_gType
type (DIRECTED or UNDIRECTED)

Here is the caller graph for this function:

size_t pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::num_vertices ( ) const
inlineinherited

Definition at line 696 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph.

696 { return boost::num_vertices(graph);}
T_E& pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::operator[] ( E  e_idx)
inlineinherited
const T_E& pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::operator[] ( E  e_idx) const
inlineinherited
T_V& pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::operator[] ( V  v_idx)
inlineinherited
const T_V& pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::operator[] ( V  v_idx) const
inlineinherited
degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::out_degree ( int64_t  vertex_id) const
inlineinherited

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.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::get_V(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::has_vertex(), and pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::out_degree().

504  {
505  if (!has_vertex(vertex_id)) {
506  return 0;
507  }
508  return out_degree(get_V(vertex_id));
509  }
bool has_vertex(int64_t vid) const
True when vid is in the graph.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex

Here is the call graph for this function:

degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::out_degree ( V v) const
inlineinherited

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.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph.

604  {
605  return boost::out_degree(v, graph);
606  }
template<class G , typename T_V , typename T_E >
degree_size_type pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::out_degree_to_vertex ( V  vertex,
V  neighbor 
)
inline

The number of edges from vertex to neighbor.

Parameters
[in]vertexvertex_descriptor of the given vertex
[in]neighborvertex_descriptor of neighbor
Returns
degree_size_type: The out-degree of vertex to neighbor

Definition at line 183 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::adjacent(), pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_directed(), pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_source(), pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_target(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_undirected().

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::in_degree_from_vertex().

183  {
184  degree_size_type degree = 0;
185  EO_i out_i, out_end;
186  for (boost::tie(out_i, out_end) =
187  boost::out_edges(vertex, this->graph);
188  out_i != out_end; ++out_i) {
189  if (this->is_directed()
190  && (this->is_source(vertex, *out_i)
191  && this->is_target(neighbor, *out_i))) {
192  degree++;
193  } else if (this->is_undirected() &&
194  this->adjacent(vertex, *out_i) == neighbor) {
195  degree++;
196  }
197  }
198  return degree;
199  }
boost::graph_traits< G >::degree_size_type degree_size_type
boost::graph_traits< G >::out_edge_iterator EO_i

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::print_graph ( std::ostringstream &  log)
inline

print the graph with contracted vertices of all vertices and edges

Definition at line 205 of file pgr_contractionGraph.hpp.

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::m_num_vertices, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::source(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::target().

205  {
206  EO_i out, out_end;
207  for (auto vi = vertices(this->graph).first;
208  vi != vertices(this->graph).second;
209  ++vi) {
210  if ((*vi) >= this->m_num_vertices) break;
211  log << this->graph[*vi].id << "(" << (*vi) << ")"
212  << this->graph[*vi].contracted_vertices() << std::endl;
213  log << " out_edges_of(" << this->graph[*vi].id << "):";
214  for (boost::tie(out, out_end) = out_edges(*vi, this->graph);
215  out != out_end; ++out) {
216  log << ' ' << this->graph[*out].id
217  << "=(" << this->graph[this->source(*out)].id
218  << ", " << this->graph[this->target(*out)].id << ") = "
219  << this->graph[*out].cost <<"\t";
220  }
221  log << std::endl;
222  }
223  }
boost::graph_traits< G >::out_edge_iterator EO_i

Here is the call graph for this function:

void pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::restore_graph ( )
inherited

Reconnects all edges that were removed.

V pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::source ( E  e_idx) const
inlineinherited

Definition at line 577 of file pgr_base_graph.hpp.

References pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::graph.

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::print_graph().

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

Here is the caller graph for this function:

V pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::target ( E  e_idx) const
inlineinherited

Member Data Documentation

graphType pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::m_gType
inherited

type (DIRECTED or UNDIRECTED)

Definition at line 309 of file pgr_base_graph.hpp.

size_t pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::m_num_vertices
inherited

local count.

Definition at line 308 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::print_graph().

IndexMap pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::mapIndex
inherited

Definition at line 320 of file pgr_base_graph.hpp.

boost::associative_property_map<IndexMap> pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::propmapIndex
inherited

Definition at line 321 of file pgr_base_graph.hpp.

std::deque< T_E > pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::removed_edges
inherited

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 >
Identifiers<V> pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::removed_vertices
template<class G , typename T_V , typename T_E >
std::vector<T_E> pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::shortcuts
id_to_V pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::vertices_map
inherited

id -> graph id

Definition at line 315 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_contractionGraph< G, T_V, T_E >::add_shortcut().

boost::property_map<G, boost::vertex_index_t>::type pgrouting::graph::Pgr_base_graph< G, T_V , T_E >::vertIndex
inherited

Definition at line 317 of file pgr_base_graph.hpp.


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