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

#include "pgr_lineGraph.hpp"

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

Public Types

typedef boost::graph_traits< G >
::edge_descriptor 
E
 
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 >
::edge_iterator 
E_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

 Pgr_lineGraph (graphType gtype)
 
std::vector< Line_vertexextract_vertices ()
 
int64_t get_edge_id (V from, V to, double &distance) const
 
std::vector< Line_graph_rtget_postgres_results_directed ()
 
std::vector< Line_graph_rtget_postgres_results_undirected ()
 
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...
 
template<typename T >
void insert_vertices (const T *edges, int64_t count)
 
template<typename T >
void insert_vertices (const std::vector< T > &edges)
 
int64_t num_edges () const
 
size_t num_vertices () const
 
void transform (pgrouting::DirectedGraph &digraph)
 
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...
 

Public Attributes

std::ostringstream log
 
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...
 

Private Member Functions

void add_vertices (std::vector< T_V > vertices)
 
void create_edges (const pgrouting::DirectedGraph &digraph)
 
template<typename T >
void graph_add_edge (int64_t, const T &source, const T &target, int64_t, int64_t)
 

Private Attributes

std::map< int64_t, pgr_edge_tm_edges
 
int64_t m_num_edges
 
std::map< std::pair< int64_t,
int64_t >, int64_t > 
m_vertex_map
 

Friends

std::ostream & operator<< (std::ostream &log, const Pgr_lineGraph< G, T_V, T_E > &g)
 

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_lineGraph< G, T_V, T_E >

Definition at line 44 of file pgr_lineGraph.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.

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

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_lineGraph< G, T_V, T_E >::E

Definition at line 87 of file pgr_lineGraph.hpp.

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

Definition at line 279 of file pgr_base_graph.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_lineGraph< G, T_V, T_E >::EI_i

Definition at line 90 of file pgr_lineGraph.hpp.

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

Definition at line 89 of file pgr_lineGraph.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_lineGraph< G, T_V, T_E >::V

Definition at line 86 of file pgr_lineGraph.hpp.

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

Definition at line 88 of file pgr_lineGraph.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_lineGraph< G, T_V, T_E >::Pgr_lineGraph ( graphType  gtype)
inlineexplicit

Member Function Documentation

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

Definition at line 574 of file pgr_lineGraph.hpp.

References pgassert.

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

575  {
576 
577  for (const auto vertex : vertices) {
578  pgassert(this->vertices_map.find(vertex.id) == this->vertices_map.end());
579 
580  auto v = add_vertex(this->graph);
581  this->vertices_map[vertex.id] = v;
582  this->graph[v].cp_members(vertex);
583 
584  pgassert(boost::num_vertices(this->graph) == this->num_vertices());
585  }
586  return;
587  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81

Here is the caller 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 >
void pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::create_edges ( const pgrouting::DirectedGraph digraph)
private

Definition at line 514 of file pgr_lineGraph.hpp.

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

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

515  {
516 
517  V_i vertexIt, vertexEnd;
518  EO_i e_outIt, e_outEnd;
519  EI_i e_inIt, e_inEnd;
520 
521  /*
522  for (each vertex v in original graph) {
523  for( all incoming edges inn to vertex v) {
524  for( all outgoing edges outt from vertex v) {
525  create an edge in the line graph(inn, outt);
526  }
527  }
528  }
529  */
530 
531  for(boost::tie(vertexIt, vertexEnd) = boost::vertices(digraph.graph);
532  vertexIt != vertexEnd; vertexIt++) {
533  V vertex = *vertexIt;
534 
535  for (boost::tie(e_outIt, e_outEnd) = boost::out_edges(vertex, digraph.graph);
536  e_outIt != e_outEnd; e_outIt++) {
537  for (boost::tie(e_inIt, e_inEnd) = boost::in_edges(vertex, digraph.graph);
538  e_inIt != e_inEnd; e_inIt++) {
539 
540 #if 0
541  log << "\n";
542  log << digraph.graph[*inIt].id << " | " << digraph[digraph.source(*inIt)].id << " | " << digraph[digraph.target(*inIt)].id << " | " << digraph.graph[*inIt].cost << "\n";
543  log << digraph.graph[*outIt].id << " | " << digraph[digraph.source(*outIt)].id << " | " << digraph[digraph.target(*outIt)].id << " | " << digraph.graph[*outIt].cost << "\n\n";
544 #endif
545 
546  /*
547  Prevent self-edges from being created in the Line Graph
548  */
549  if (labs(digraph.graph[*e_inIt].id) == labs(digraph.graph[*e_outIt].id))
550  continue;
551 
552  auto source_in_edge = digraph.source(*e_inIt);
553 
554 #if 0
555  log << "source = " << digraph[source_in_edge] << " | mid = " << digraph[vertex] << "\n\n\n";
556 #endif
557 
558  ++m_num_edges;
559 
561  m_num_edges,
562  (digraph.graph[*e_inIt]).id,
563  (digraph.graph[*e_outIt]).id,
564  digraph[source_in_edge].id,
565  digraph[vertex].id
566  );
567  }
568  }
569  }
570 }
boost::graph_traits< G >::vertex_descriptor V
boost::graph_traits< G >::vertex_iterator V_i
void graph_add_edge(int64_t, const T &source, const T &target, int64_t, int64_t)
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:

Here is the caller graph for this function:

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 >
std::vector< Line_vertex > pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::extract_vertices ( )

Definition at line 380 of file pgr_lineGraph.hpp.

References edge::cost, pgrouting::Line_vertex::cost, edge::id, pgrouting::Line_vertex::id, edge::reverse_cost, edge::source, pgrouting::Line_vertex::source, edge::target, pgrouting::Line_vertex::target, UNDIRECTED, and pgrouting::Line_vertex::vertex_id.

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

380  {
381  /*
382  m_vertex_map stores a unique id assigned to each vertex of Line Graph.
383 
384  In case of a directed edge, either 1 or 2 vertices are to be created in
385  the Line Graph for each of the edges.
386  Consider the following edge in directed graph:-
387  ID = 1 | source = 2 | target = 3 | cost = 10 | reverse_cost = 20
388  This creates 2 vertices in Line Graph:-
389  1. ID = 1 | source = 2 | target = 3 | cost = 10
390  2. ID = 1 | source = 3 | target = 2 | cost = 25
391  So, the values stored in m_vertex_map would be:-
392  1. {1, 2} = 1(Denoting the edge from 2 - > 3 of cost 10).
393  2. {1, 3} = 2(Denoting the edge from 3 - > 2 of cost 25).
394  where {key} = value in m_vertex_map.
395 
396  In case of undirected edge, either 2 or 4 vertices are to be created in
397  the Line Graph for each of the edges.
398  Consider the following edge in an undirected graph:-
399  ID = 1 | source = 2 | target = 3 | cost = 10 | reverse_cost = 25
400  This creates the following 4 vertices in Line Graph:-
401  1. ID = 1 | source = 2 | target = 3 | cost = 10
402  2. ID = 1 | source = 3 | target = 2 | cost = 10
403  3. ID = 1 | source = 3 | target = 2 | cost = 25
404  4. ID = 1 | source = 2 | target = 3 | cost = 25
405  so, the values stored in m_vertex_map would be:-
406  1. {1, 2} = 1(Denoting the edge from 2 - > 3 of cost 10).
407  2. {-1, 3} = 2(Denoting the edge from 3 - > 2 of cost 10).
408  3. {1, 3} = 3(Deonting the edge from 3 - > 2 of cost 25).
409  4. {-1, 2} = 4(Denoting the edge from 2 - > 3 of cost 25).
410  where {key} = value in m_vertex_map.
411  */
412  if (m_edges.empty()) return std::vector< Line_vertex >();
413 
414  std::vector< Line_vertex > vertices;
415 
416 #if 0
417  log << "\nEdges of original graph\n";
418 #endif
419 
420  for (const auto &it : m_edges) {
421  auto edge = it.second;
422  Line_vertex vertex(edge);
423 
424 #if 1
425  log << "ID: " << edge.id;
426  log << "| source: " << edge.source;
427  log << "| target: " << edge.target;
428  log << "| cost: " << edge.cost;
429  log << "| reverse_cost: " << edge.reverse_cost << "\n\n";
430 #endif
431 
432  if (edge.cost > 0) {
433  vertex.id = (++(this->m_num_vertices));
434  vertices.push_back(vertex);
435  m_vertex_map[ std::pair<int64_t,int64_t>(edge.id, edge.source) ] = this->m_num_vertices;
436 
437  if (this->m_gType == UNDIRECTED) {
438  vertex.id = (++(this->m_num_vertices));
439  std::swap(vertex.source, vertex.target);
440  vertices.push_back(vertex);
441  m_vertex_map[std::pair<int64_t,int64_t>(-1*edge.id, edge.target)] = this->m_num_vertices;
442  std::swap(vertex.source, vertex.target);
443  }
444  }
445 
446  if (edge.reverse_cost > 0) {
447  vertex.id = (++(this->m_num_vertices));
448  vertex.cost = edge.reverse_cost;
449  vertex.vertex_id *= -1;
450  std::swap(vertex.source, vertex.target);
451  vertices.push_back(vertex);
452  m_vertex_map[ std::pair<int64_t,int64_t>(edge.id, edge.target) ] = this->m_num_vertices;
453 
454  if (this->m_gType == UNDIRECTED) {
455  vertex.id = (++(this->m_num_vertices));
456  std::swap(vertex.source, vertex.target);
457  vertices.push_back(vertex);
458  m_vertex_map[std::pair<int64_t,int64_t>(-1*edge.id, edge.source)] = this->m_num_vertices;
459  }
460  }
461  }
462 #if 0
463  for (auto it: m_vertex_map) {
464  log << it.first.first << " | " << it.first.second << " | " << it.second << "\n";
465  }
466 #endif
467  return vertices;
468 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
long id
Definition: trsp.h:32
graphType m_gType
type (DIRECTED or UNDIRECTED)
std::map< std::pair< int64_t, int64_t >, int64_t > m_vertex_map
std::map< int64_t, pgr_edge_t > m_edges
long target
Definition: trsp.h:34
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33

Here is the caller 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< Line_graph_rt > pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::get_postgres_results_directed ( )

Definition at line 205 of file pgr_lineGraph.hpp.

References edges.

Referenced by do_pgr_lineGraph().

205  {
206  std::vector< Line_graph_rt > results;
207 
208  typename boost::graph_traits < G >::edge_iterator edgeIt, edgeEnd;
209  std::map < std::pair<int64_t,int64_t >, Line_graph_rt > unique;
210  int64_t count = 0;
211 
212  log << "\nPostgres results\n";
213  for (boost::tie(edgeIt, edgeEnd) = boost::edges(this->graph);
214  edgeIt != edgeEnd; edgeIt++) {
215  E e = *edgeIt;
216  auto e_source = this->graph[this->source(e)].vertex_id;
217  auto e_target = this->graph[this->target(e)].vertex_id;
218 
219  log << "e_source = " << e_source << " | e_target = " << e_target << "\n";
220 
221  if(unique.find( {e_target, e_source} ) != unique.end()) {
222  unique[ std::pair<int64_t,int64_t>(e_target, e_source) ].reverse_cost = 1.0;
223  continue;
224  }
225  e_source *= -1;
226  e_target *= -1;
227  if(unique.find( {e_target, e_source} ) != unique.end()) {
228  unique[ std::pair<int64_t,int64_t>(e_target, e_source) ].reverse_cost = 1.0;
229  continue;
230  }
231  e_source *= -1;
232  e_target *= -1;
233 
234  Line_graph_rt edge = {
235  ++count,
236  e_source,
237  e_target,
238  1.0,
239  -1.0
240  };
241  unique[ std::pair<int64_t,int64_t>(e_source, e_target)] = edge;
242  }
243  for (const auto &edge: unique) {
244  results.push_back(edge.second);
245  }
246  return results;
247 }
static edge_t edges[22573]
boost::graph_traits< G >::edge_descriptor E
Definition: trsp.h:31

Here is the caller graph for this function:

template<class G , typename T_V , typename T_E >
std::vector< Line_graph_rt > pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::get_postgres_results_undirected ( )

Definition at line 175 of file pgr_lineGraph.hpp.

References edges.

Referenced by do_pgr_lineGraph().

175  {
176  std::vector< Line_graph_rt > results;
177 
178  typename boost::graph_traits < G >::edge_iterator edgeIt, edgeEnd;
179  int64_t count = 0;
180 
181  log << "\nPostgres results\n";
182  for (boost::tie(edgeIt, edgeEnd) = boost::edges(this->graph);
183  edgeIt != edgeEnd; edgeIt++) {
184  E e = *edgeIt;
185  auto e_source = this->graph[this->source(e)].vertex_id;
186  auto e_target = this->graph[this->target(e)].vertex_id;
187 
188  log << "e_source = " << e_source << " | e_target = " << e_target << "\n";
189 
190  Line_graph_rt edge = {
191  ++count,
192  e_source,
193  e_target,
194  1.0,
195  -1.0
196  };
197  results.push_back(edge);
198  }
199 
200  return results;
201 }
static edge_t edges[22573]
boost::graph_traits< G >::edge_descriptor E
Definition: trsp.h:31

Here is the caller 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:

template<class G , typename T_V , typename T_E >
template<typename T >
void pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::graph_add_edge ( int64_t  _id,
const T &  source,
const T &  target,
int64_t  source_in_edge,
int64_t  source_out_edge 
)
private

Definition at line 473 of file pgr_lineGraph.hpp.

References pgassert.

478  {
479 
480  bool inserted;
482 
483  pgassert(m_vertex_map.find( {source, source_in_edge} ) !=
484  m_vertex_map.end());
485  pgassert(m_vertex_map.find( {target, source_out_edge} ) !=
486  m_vertex_map.end());
487 
488  auto index_source_edge = m_vertex_map[ std::pair<int64_t,int64_t>(source, source_in_edge) ];
489  auto index_target_edge = m_vertex_map[ std::pair<int64_t,int64_t>(target, source_out_edge) ];
490 
491 #if 0
492  log << "\nsource_in_edge = " << source_in_edge << " | "
493  << "source_out_edge = " << source_out_edge << " | "
494  << "index_source_edge = " << index_source_edge << " | "
495  << "index_target_edge = " << index_target_edge << " | "
496  << "edge.source = " << source << " | "
497  << "edge.target = " << target << "\n";
498 #endif
499 
500  auto vm_s = this->get_V(index_source_edge);
501  auto vm_t = this->get_V(index_target_edge);
502 
503  pgassert(this->vertices_map.find(index_source_edge) != this->vertices_map.end());
504  pgassert(this->vertices_map.find(index_target_edge) != this->vertices_map.end());
505 
506  boost::tie(e, inserted) =
507  boost::add_edge(vm_s, vm_t, this->graph);
508 
509  this->graph[e].id = _id;
510 }
boost::graph_traits< G >::edge_descriptor E
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
std::map< std::pair< int64_t, int64_t >, int64_t > m_vertex_map
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
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:

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:

template<class G , typename T_V , typename T_E >
template<typename T >
void pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::insert_vertices ( const T *  edges,
int64_t  count 
)
inline

Definition at line 100 of file pgr_lineGraph.hpp.

Referenced by Pgr_dijkstraTRSP< G >::dijkstraTRSP(), and do_pgr_lineGraph().

100  {
101  insert_vertices(std::vector < T >(edges, edges + count));
102  }
static edge_t edges[22573]
void insert_vertices(const T *edges, int64_t count)

Here is the caller graph for this function:

template<class G , typename T_V , typename T_E >
template<typename T >
void pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::insert_vertices ( const std::vector< T > &  edges)
inline

Definition at line 105 of file pgr_lineGraph.hpp.

References pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::add_vertices(), pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::extract_vertices(), pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::log, and pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::m_edges.

105  {
106 
107  for (auto &it: edges)
108  m_edges[it.id] = it;
109  std::vector < Line_vertex > vertices = extract_vertices();
110 
111 #if 1
112  log << "\nVertices of line graph: \n";
113  for (auto vertex: vertices) {
114  log << vertex.id << "(" << vertex.source << " - > ";
115  log << vertex.target << ")" << vertex.cost << "\n";
116  }
117 #endif
118 
119  add_vertices(vertices);
120  }
std::vector< Line_vertex > extract_vertices()
std::map< int64_t, pgr_edge_t > m_edges
void add_vertices(std::vector< T_V > 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:

template<class G , typename T_V , typename T_E >
int64_t pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::num_edges ( ) const
inline
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  }
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
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::transform ( pgrouting::DirectedGraph digraph)
inline

Definition at line 140 of file pgr_lineGraph.hpp.

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

Referenced by Pgr_dijkstraTRSP< G >::dijkstraTRSP(), and do_pgr_lineGraph().

140  {
141  create_edges(digraph);
142  }
void create_edges(const pgrouting::DirectedGraph &digraph)

Here is the call graph for this function:

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_lineGraph< G, T_V, T_E > &  g 
)
friend

Definition at line 152 of file pgr_lineGraph.hpp.

153  {
154  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
155 
156  for (auto vi = vertices(g.graph).first;
157  vi != vertices(g.graph).second; ++vi) {
158  if ((*vi) >= g.m_num_vertices) break;
159  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
160  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
161  out != out_end; ++out) {
162  log << ' '
163  << g.graph[*out].id << "=("
164  << g[g.source(*out)].id << ", "
165  << g[g.target(*out)].id << ")\t";
166  }
167  log << std::endl;
168  }
169  return log;
170  }
boost::graph_traits< G >::out_edge_iterator EO_i

Member Data Documentation

template<class G , typename T_V , typename T_E >
std::ostringstream pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::log
template<class G , typename T_V , typename T_E >
std::map< int64_t, pgr_edge_t > pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::m_edges
private
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.

template<class G , typename T_V , typename T_E >
int64_t pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::m_num_edges
private
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().

template<class G , typename T_V , typename T_E >
std::map< std::pair< int64_t, int64_t >, int64_t > pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::m_vertex_map
private

Definition at line 60 of file pgr_lineGraph.hpp.

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.

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: