PGROUTING  2.6
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)
 
 Pgr_lineGraph (const pgrouting::DirectedGraph &digraph)
 
int64_t get_edge_id (V from, V to, double &distance) const
 
std::vector< Line_graph_rtget_postgres_results_directed ()
 
void graph_add_edge (const T_E &edge)
 
template<typename T >
void graph_add_edge (const T &edge, bool normal=true)
 
template<typename T >
void graph_add_edge_no_create_vertex (const T &edge)
 Use this function when the vertices are already inserted in the graph. More...
 
void insert_vertices (const pgrouting::DirectedGraph &digraph)
 
size_t num_edges () const
 
size_t num_vertices () const
 
Insert edges
template<typename T >
void insert_edges (const T *edges, int64_t count)
 Inserts count edges of type T into the graph. More...
 
template<typename T >
void insert_edges (T *edges, int64_t count, bool)
 
template<typename T >
void insert_edges (const std::vector< T > &edges, bool normal=true)
 Inserts count edges of type pgr_edge_t into the graph. More...
 
template<typename T >
void insert_edges_neg (const T *edges, int64_t count)
 
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...
 
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

V add_one_vertex (T_V vertex)
 
void create_edges (const pgrouting::DirectedGraph &digraph)
 
template<typename T >
void graph_add_edge (const T &source, const T &target)
 

Private Attributes

std::map< int64_t, pgr_edge_tm_edges
 

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< IndexMappropmapIndex
 

Detailed Description

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

Definition at line 45 of file pgr_lineGraph.hpp.

Member Typedef Documentation

template<class G, typename T_V, typename T_E>
typedef G pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::B_G
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_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 48 of file pgr_lineGraph.hpp.

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

Definition at line 279 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::edges_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::edges_size_type
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 51 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 50 of file pgr_lineGraph.hpp.

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

Definition at line 274 of file pgr_base_graph.hpp.

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

Definition at line 275 of file pgr_base_graph.hpp.

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

Definition at line 300 of file pgr_base_graph.hpp.

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

Definition at line 318 of file pgr_base_graph.hpp.

template<class G, typename T_V, typename T_E>
typedef id_to_V::const_iterator pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::LI
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 47 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 49 of file pgr_lineGraph.hpp.

template<class G, typename T_V, typename T_E>
typedef boost::graph_traits< G >::vertices_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::vertices_size_type
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

Definition at line 54 of file pgr_lineGraph.hpp.

55  : Pgr_base_graph< G, T_V, T_E >(gtype) {
56  }
template<class G, typename T_V, typename T_E>
pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::Pgr_lineGraph ( const pgrouting::DirectedGraph digraph)
inline

Definition at line 58 of file pgr_lineGraph.hpp.

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

59  : Pgr_base_graph< G, T_V, T_E >(graphType::DIRECTED) {
60  insert_vertices(digraph);
61  create_edges(digraph);
62  }
void insert_vertices(const pgrouting::DirectedGraph &digraph)
void create_edges(const pgrouting::DirectedGraph &digraph)

Here is the call graph for this function:

Member Function Documentation

template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::add_one_vertex ( T_V  vertex)
inlineprivate

Definition at line 198 of file pgr_lineGraph.hpp.

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

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

199  {
200  auto v = add_vertex(this->graph);
201  this->vertices_map[vertex.id] = v;
202  this->graph[v].cp_members(vertex);
203 
204  pgassert(boost::num_vertices(this->graph) == this->num_vertices());
205  return v;
206  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id

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>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::adjacent ( V  v_idx,
E  e_idx 
) const
inlineinherited

Definition at line 590 of file pgr_base_graph.hpp.

References pgassert.

590  {
591  pgassert(is_source(v_idx, e_idx) || is_target(v_idx, e_idx));
592  return is_source(v_idx, e_idx)?
593  target(e_idx) :
594  source(e_idx);
595  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
bool is_source(V v_idx, E e_idx) const
bool is_target(V v_idx, E e_idx) const
template<class G, typename T_V, typename T_E>
void pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::create_edges ( const pgrouting::DirectedGraph digraph)
inlineprivate

Definition at line 165 of file pgr_lineGraph.hpp.

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

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

166  {
167  V_i vertexIt, vertexEnd;
168  EO_i e_outIt, e_outEnd;
169  EI_i e_inIt, e_inEnd;
170 
171 
172  /* for (each vertex v in original graph) */
173  for (boost::tie(vertexIt, vertexEnd) = boost::vertices(digraph.graph);
174  vertexIt != vertexEnd; vertexIt++) {
175  auto vertex = *vertexIt;
176 
177  /* for( all incoming edges in to vertex v) */
178  for (boost::tie(e_outIt, e_outEnd) =
179  boost::out_edges(vertex, digraph.graph);
180  e_outIt != e_outEnd;
181  e_outIt++) {
182  /* for( all outgoing edges out from vertex v) */
183  for (boost::tie(e_inIt, e_inEnd) =
184  boost::in_edges(vertex, digraph.graph);
185  e_inIt != e_inEnd; e_inIt++) {
186  /*
187  Prevent self-edges from being created in the Line Graph
188  */
189 
191  (digraph.graph[*e_inIt]).id,
192  (digraph.graph[*e_outIt]).id);
193  }
194  }
195  }
196  }
void graph_add_edge(const T &source, const T &target)
boost::graph_traits< G >::vertex_iterator V_i
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:

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

Definition at line 764 of file pgr_base_graph.hpp.

764  {
765  T_E d_edge;
766 
767  // nothing to do, the vertex doesn't exist
768  if (!has_vertex(p_from) || !has_vertex(p_to)) return;
769 
770  EO_i out, out_end;
771  V g_from(get_V(p_from));
772  V g_to(get_V(p_to));
773 
774  // store the edges that are going to be removed
775  for (boost::tie(out, out_end) = out_edges(g_from, graph);
776  out != out_end; ++out) {
777  if (target(*out) == g_to) {
778  d_edge.id = graph[*out].id;
779  d_edge.source = graph[source(*out)].id;
780  d_edge.target = graph[target(*out)].id;
781  d_edge.cost = graph[*out].cost;
782  removed_edges.push_back(d_edge);
783  }
784  }
785  // the actual removal
786  boost::remove_edge(g_from, g_to, graph);
787 }
boost::graph_traits< G >::out_edge_iterator EO_i
std::deque< T_E > removed_edges
Used for storing the removed_edges.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
boost::graph_traits< G >::vertex_descriptor V
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 
)
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

Definition at line 793 of file pgr_base_graph.hpp.

794  {
795  T_E d_edge;
796 
797  // nothing to do, the vertex doesn't exist
798  if (!has_vertex(vertex_id)) return;
799  auto v_from(get_V(vertex_id));
800 
801  EO_i out, out_end;
802  bool change = true;
803  // store the edge that are going to be removed
804  while (change) {
805  change = false;
806  for (boost::tie(out, out_end) = out_edges(v_from, graph);
807  out != out_end; ++out) {
808  if (graph[*out].id == edge_id) {
809  d_edge.id = graph[*out].id;
810  d_edge.source = graph[source(*out)].id;
811  d_edge.target = graph[target(*out)].id;
812  d_edge.cost = graph[*out].cost;
813  removed_edges.push_back(d_edge);
814  boost::remove_edge((*out), graph);
815  change = true;
816  break;
817  }
818  }
819  }
820 }
boost::graph_traits< G >::out_edge_iterator EO_i
std::deque< T_E > removed_edges
Used for storing the removed_edges.
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::disconnect_vertex ( int64_t  p_vertex)
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

Definition at line 825 of file pgr_base_graph.hpp.

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

Definition at line 832 of file pgr_base_graph.hpp.

References DIRECTED.

832  {
833  T_E d_edge;
834 
835  EO_i out, out_end;
836  // store the edges that are going to be removed
837  for (boost::tie(out, out_end) = out_edges(vertex, graph);
838  out != out_end; ++out) {
839  d_edge.id = graph[*out].id;
840  d_edge.source = graph[source(*out)].id;
841  d_edge.target = graph[target(*out)].id;
842  d_edge.cost = graph[*out].cost;
843  removed_edges.push_back(d_edge);
844  }
845 
846  // special case
847  if (m_gType == DIRECTED) {
848  EI_i in, in_end;
849  for (boost::tie(in, in_end) = in_edges(vertex, graph);
850  in != in_end; ++in) {
851  d_edge.id = graph[*in].id;
852  d_edge.source = graph[source(*in)].id;
853  d_edge.target = graph[target(*in)].id;
854  d_edge.cost = graph[*in].cost;
855  removed_edges.push_back(d_edge);
856  }
857  }
858 
859  // delete incoming and outgoing edges from the vertex
860  boost::clear_vertex(vertex, graph);
861 }
boost::graph_traits< G >::out_edge_iterator EO_i
std::deque< T_E > removed_edges
Used for storing the removed_edges.
graphType m_gType
type (DIRECTED or UNDIRECTED)
boost::graph_traits< G >::in_edge_iterator EI_i
template<class G , typename T_V , typename T_E >
int64_t pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_edge_id ( V  from,
V  to,
double &  distance 
) const
inherited

Definition at line 875 of file pgr_base_graph.hpp.

878  {
879  E e;
880  EO_i out_i, out_end;
881  V v_source, v_target;
882  double minCost = (std::numeric_limits<double>::max)();
883  int64_t minEdge = -1;
884  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
885  out_i != out_end; ++out_i) {
886  e = *out_i;
887  v_target = target(e);
888  v_source = source(e);
889  if ((from == v_source) && (to == v_target)
890  && (distance == graph[e].cost))
891  return graph[e].id;
892  if ((from == v_source) && (to == v_target)
893  && (minCost > graph[e].cost)) {
894  minCost = graph[e].cost;
895  minEdge = graph[e].id;
896  }
897  }
898  distance = minEdge == -1? 0: minCost;
899  return minEdge;
900 }
boost::graph_traits< G >::out_edge_iterator EO_i
boost::graph_traits< G >::vertex_descriptor V
boost::graph_traits< G >::edge_descriptor E
template<class G, typename T_V, typename T_E>
std::vector< Line_graph_rt > pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::get_postgres_results_directed ( )
inline

Definition at line 87 of file pgr_lineGraph.hpp.

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

87  {
88  std::vector< Line_graph_rt > results;
89 
90  typename boost::graph_traits < G >::edge_iterator edgeIt, edgeEnd;
91  std::map < std::pair<int64_t, int64_t >, Line_graph_rt > unique;
92  int64_t count = 0;
93 
94  for (boost::tie(edgeIt, edgeEnd) = boost::edges(this->graph);
95  edgeIt != edgeEnd; edgeIt++) {
96  E e = *edgeIt;
97  auto e_source = this->graph[this->source(e)].vertex_id;
98  auto e_target = this->graph[this->target(e)].vertex_id;
99 
100  if (unique.find({e_target, e_source}) != unique.end()) {
101  unique[std::pair<int64_t, int64_t>(e_target,
102  e_source)].reverse_cost = 1.0;
103  continue;
104  }
105  e_source *= -1;
106  e_target *= -1;
107  if (unique.find({e_target, e_source}) != unique.end()) {
108  unique[std::pair<int64_t, int64_t>(e_target,
109  e_source)].reverse_cost = 1.0;
110  continue;
111  }
112  e_source *= -1;
113  e_target *= -1;
114 
115  Line_graph_rt edge = {
116  ++count,
117  e_source,
118  e_target,
119  1.0,
120  -1.0
121  };
122  unique[std::pair<int64_t, int64_t>(e_source, e_target)] = edge;
123  }
124  for (const auto &edge : unique) {
125  results.push_back(edge.second);
126  }
127  return results;
128  }
boost::graph_traits< G >::edge_descriptor E
Definition: trsp.h:31

Here is the call graph for this function:

template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_V ( 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 538 of file pgr_base_graph.hpp.

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

538  {
539  auto vm_s(vertices_map.find(vertex.id));
540  if (vm_s == vertices_map.end()) {
541  auto v = add_vertex(graph);
542  graph[v].cp_members(vertex);
543  vertices_map[vertex.id] = v;
544  put(propmapIndex, v, num_vertices());
545  return v;
546  }
547  return vm_s->second;
548  }
boost::associative_property_map< IndexMap > propmapIndex
id_to_V vertices_map
id -> graph id

Here is the caller graph for this function:

template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_V ( int64_t  vid) const
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 556 of file pgr_base_graph.hpp.

References pgassert.

556  {
557  pgassert(has_vertex(vid));
558  return vertices_map.find(vid)->second;
559  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id
bool has_vertex(int64_t vid) const
True when vid is in the graph.
template<class G, typename T_V, typename T_E>
template<typename T >
void pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::graph_add_edge ( const T &  source,
const T &  target 
)
inlineprivate

Definition at line 150 of file pgr_lineGraph.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 >::num_edges().

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

152  {
153  bool inserted;
154  E e;
155 
156  auto vm_s = this->get_V(source);
157  auto vm_t = this->get_V(target);
158 
159  boost::tie(e, inserted) =
160  boost::add_edge(vm_s, vm_t, this->graph);
161 
162  this->graph[e].id = this->num_edges();
163  }
boost::graph_traits< G >::edge_descriptor E
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex

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_base_graph< G, T_V, T_E >::graph_add_edge ( const T_E &  edge)
inherited

Definition at line 905 of file pgr_base_graph.hpp.

905  {
906  bool inserted;
907  typename Pgr_base_graph< G, T_V, T_E >::LI vm_s, vm_t;
909 
910  vm_s = vertices_map.find(edge.source);
911  if (vm_s == vertices_map.end()) {
913  vm_s = vertices_map.find(edge.source);
914  }
915 
916  vm_t = vertices_map.find(edge.target);
917  if (vm_t == vertices_map.end()) {
919  vm_t = vertices_map.find(edge.target);
920  }
921 
922  if (edge.cost >= 0) {
923  boost::tie(e, inserted) =
924  boost::add_edge(vm_s->second, vm_t->second, graph);
925  graph[e].cp_members(edge);
926  }
927 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
id_to_V vertices_map
id -> graph id
long target
Definition: trsp.h:34
boost::graph_traits< G >::edge_descriptor E
long source
Definition: trsp.h:33
template<class G , typename T_V , typename T_E >
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph_add_edge ( const T &  edge,
bool  normal = true 
)
inherited

Definition at line 933 of file pgr_base_graph.hpp.

References DIRECTED, pgassert, and UNDIRECTED.

933  {
934  bool inserted;
936  if ((edge.cost < 0) && (edge.reverse_cost < 0))
937  return;
938 
939  /*
940  * true: for source
941  * false: for target
942  */
943  auto vm_s = get_V(T_V(edge, true));
944  auto vm_t = get_V(T_V(edge, false));
945 
946  pgassert(vertices_map.find(edge.source) != vertices_map.end());
947  pgassert(vertices_map.find(edge.target) != vertices_map.end());
948  if (edge.cost >= 0) {
949  boost::tie(e, inserted) =
950  boost::add_edge(vm_s, vm_t, graph);
951  graph[e].cost = edge.cost;
952  graph[e].id = edge.id;
953  }
954 
955  if (edge.reverse_cost >= 0
956  && (m_gType == DIRECTED
957  || (m_gType == UNDIRECTED && edge.cost != edge.reverse_cost))) {
958  boost::tie(e, inserted) =
959  boost::add_edge(vm_t, vm_s, graph);
960 
961  graph[e].cost = edge.reverse_cost;
962  graph[e].id = normal? edge.id : -edge.id;
963  }
964 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
long id
Definition: trsp.h:32
graphType m_gType
type (DIRECTED or UNDIRECTED)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id
long target
Definition: trsp.h:34
float8 reverse_cost
Definition: trsp.h:36
boost::graph_traits< G >::edge_descriptor E
long source
Definition: trsp.h:33
template<class G, typename T_V, typename T_E>
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph_add_edge_no_create_vertex ( const T &  edge)
inlineinherited

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

Definition at line 721 of file pgr_base_graph.hpp.

References pgassert, and pgassertwm.

721  {
722  bool inserted;
723  E e;
724  if ((edge.cost < 0) && (edge.reverse_cost < 0))
725  return;
726 
727 #if 0
728  std::ostringstream log;
729  for (auto iter = vertices_map.begin();
730  iter != vertices_map.end();
731  iter++) {
732  log << "Key: " << iter->first <<"\tValue:" << iter->second << "\n";
733  }
734  pgassertwm(has_vertex(edge.source), log.str().c_str());
736 #endif
737 
738  auto vm_s = get_V(edge.source);
739  auto vm_t = get_V(edge.target);
740 
741 
742  if (edge.cost >= 0) {
743  boost::tie(e, inserted) =
744  boost::add_edge(vm_s, vm_t, graph);
745  graph[e].cost = edge.cost;
746  graph[e].id = edge.id;
747  }
748 
749  if (edge.reverse_cost >= 0 && (is_directed()
750  || (is_undirected() && edge.cost != edge.reverse_cost))) {
751  boost::tie(e, inserted) =
752  boost::add_edge(vm_t, vm_s, graph);
753  graph[e].cost = edge.reverse_cost;
754  graph[e].id = edge.id;
755  }
756  }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
long id
Definition: trsp.h:32
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
id_to_V vertices_map
id -> graph id
long target
Definition: trsp.h:34
bool has_vertex(int64_t vid) const
True when vid is in the graph.
float8 reverse_cost
Definition: trsp.h:36
boost::graph_traits< G >::edge_descriptor E
long source
Definition: trsp.h:33
template<class G, typename T_V, typename T_E>
bool pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::has_vertex ( int64_t  vid) const
inlineinherited

True when vid is in the graph.

Definition at line 562 of file pgr_base_graph.hpp.

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

Definition at line 521 of file pgr_base_graph.hpp.

521  {
522  if (!has_vertex(vertex_id)) {
523  return 0;
524  }
525  return is_directed()?
526  in_degree(get_V(vertex_id))
527  : out_degree(get_V(vertex_id));
528  }
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
degree_size_type in_degree(int64_t vertex_id) const
bool has_vertex(int64_t vid) const
True when vid is in the graph.
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
template<class G, typename T_V, typename T_E>
degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::in_degree ( V v) const
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 604 of file pgr_base_graph.hpp.

604  {
605  return is_directed()?
606  boost::in_degree(v, graph) :
607  boost::out_degree(v, graph);
608  }
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
template<class G, typename T_V, typename T_E>
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::insert_edges ( const T *  edges,
int64_t  count 
)
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 404 of file pgr_base_graph.hpp.

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

404  {
405  insert_edges(std::vector < T >(edges, edges + count));
406  }
void insert_edges(const T *edges, int64_t count)
Inserts count edges of type T into the graph.

Here is the caller graph for this function:

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

Definition at line 414 of file pgr_base_graph.hpp.

References pgassert.

414  {
415  for (int64_t i = 0; i < count; ++i) {
416  pgassert(has_vertex(edges[i].source));
417  pgassert(has_vertex(edges[i].target));
419  }
420  }
void graph_add_edge_no_create_vertex(const T &edge)
Use this function when the vertices are already inserted in the graph.
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
bool has_vertex(int64_t vid) const
True when vid is in the graph.
template<class G, typename T_V, typename T_E>
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::insert_edges ( const std::vector< T > &  edges,
bool  normal = true 
)
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 442 of file pgr_base_graph.hpp.

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

442  {
443 #if 0
444  // This code does not work with contraction
445  if (num_vertices() == 0) {
446  auto vertices = pgrouting::extract_vertices(edges);
447  pgassert(pgrouting::check_vertices(vertices) == 0);
448  add_vertices(vertices);
449  }
450 #endif
451  for (const auto edge : edges) {
452  graph_add_edge(edge, normal);
453  }
454  }
Definition: trsp.h:31
void graph_add_edge(const T_E &edge)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
void add_vertices(std::vector< T_V > vertices)
adds the vertices into the graph
size_t check_vertices(std::vector< Basic_vertex > vertices)

Here is the call graph for this function:

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

Definition at line 409 of file pgr_base_graph.hpp.

Referenced by do_pgr_lineGraph(), and do_pgr_lineGraphFull().

409  {
410  insert_edges(std::vector < T >(edges, edges + count), false);
411  }
void insert_edges(const T *edges, int64_t count)
Inserts count edges of type T into the graph.

Here is the caller graph for this function:

template<class G, typename T_V, typename T_E>
void pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::insert_vertices ( const pgrouting::DirectedGraph digraph)
inline

Definition at line 130 of file pgr_lineGraph.hpp.

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

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

131  {
132  auto es = boost::edges(digraph.graph);
133  for (auto eit = es.first; eit != es.second; ++eit) {
134  auto edge = *eit;
135  Line_vertex vertex({
136  digraph[edge].id,
137  digraph[boost::source(edge, digraph.graph)].id,
138  digraph[boost::target(edge, digraph.graph)].id,
139  digraph[edge].cost,
140  -1});
142  }
143  }
Definition: trsp.h:31

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>
bool pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::is_directed ( ) const
inlineinherited

Definition at line 571 of file pgr_base_graph.hpp.

References DIRECTED.

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

Definition at line 573 of file pgr_base_graph.hpp.

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

Definition at line 574 of file pgr_base_graph.hpp.

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

Definition at line 572 of file pgr_base_graph.hpp.

References UNDIRECTED.

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

Definition at line 708 of file pgr_base_graph.hpp.

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

708 { return boost::num_edges(graph);}

Here is the caller graph for this function:

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

Definition at line 707 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::add_one_vertex(), and pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::insert_vertex().

707 { return boost::num_vertices(graph);}

Here is the caller graph for this function:

template<class G, typename T_V, typename T_E>
T_E& pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::operator[] ( E  e_idx)
inlineinherited

Definition at line 582 of file pgr_base_graph.hpp.

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

Definition at line 583 of file pgr_base_graph.hpp.

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

Definition at line 585 of file pgr_base_graph.hpp.

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

Definition at line 586 of file pgr_base_graph.hpp.

586 {return graph[v_idx];}
template<class G, typename T_V, typename T_E>
degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::out_degree ( int64_t  vertex_id) const
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 515 of file pgr_base_graph.hpp.

515  {
516  if (!has_vertex(vertex_id)) {
517  return 0;
518  }
519  return out_degree(get_V(vertex_id));
520  }
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
template<class G, typename T_V, typename T_E>
degree_size_type pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::out_degree ( V v) const
inlineinherited

out degree of a vertex

regardles of undirected or directed graph

  • out degree is returned

Definition at line 615 of file pgr_base_graph.hpp.

615  {
616  return boost::out_degree(v, graph);
617  }
template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::restore_graph ( )
inherited

Reconnects all edges that were removed.

Definition at line 865 of file pgr_base_graph.hpp.

865  {
866  while (removed_edges.size() != 0) {
868  removed_edges.pop_front();
869  }
870 }
std::deque< T_E > removed_edges
Used for storing the removed_edges.
void graph_add_edge(const T_E &edge)
template<class G, typename T_V, typename T_E>
V pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::target ( E  e_idx) const
inlineinherited

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 65 of file pgr_lineGraph.hpp.

66  {
67  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
68 
69  for (auto vi = vertices(g.graph).first;
70  vi != vertices(g.graph).second; ++vi) {
71  if ((*vi) >= g.num_vertices()) break;
72  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
73  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
74  out != out_end; ++out) {
75  log << ' '
76  << g.graph[*out].id << "=("
77  << g[g.source(*out)].id << ", "
78  << g[g.target(*out)].id << ")\t";
79  }
80  log << std::endl;
81  }
82  return log;
83  }
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

Definition at line 212 of file pgr_lineGraph.hpp.

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

Definition at line 209 of file pgr_lineGraph.hpp.

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

type (DIRECTED or UNDIRECTED)

Definition at line 308 of file pgr_base_graph.hpp.

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

Definition at line 319 of file pgr_base_graph.hpp.

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

Definition at line 320 of file pgr_base_graph.hpp.

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

Used for storing the removed_edges.

Definition at line 328 of file pgr_base_graph.hpp.

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

Definition at line 316 of file pgr_base_graph.hpp.


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