PGROUTING  3.2
pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E > Class Template Reference

#include "pgr_lineGraphFull.hpp"

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

Public Types

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
 
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
 
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
 
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
 
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_lineGraphFull (const graphType &gtype)
 
 Pgr_lineGraphFull (const pgrouting::DirectedGraph &digraph)
 
std::vector< Line_graph_full_rtget_postgres_results_directed ()
 
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 When the vertex does not exist More...
 
V get_V (int64_t vid) const
 get the vertex descriptor of the vid Call has_vertex(vid) before calling this function More...
 
bool has_vertex (int64_t vid) const
 True when vid is in the graph. More...
 
to be or not to be
bool is_directed () const
 
bool is_undirected () const
 
bool is_source (V v_idx, E e_idx) const
 
bool is_target (V v_idx, E e_idx) const
 
boost wrappers with V
T_E & operator[] (E e_idx)
 
const T_E & operator[] (E e_idx) const
 
T_V & operator[] (V v_idx)
 
const T_V & operator[] (V v_idx) const
 
V source (E e_idx) const
 
V target (E e_idx) const
 
V adjacent (V v_idx, E e_idx) const
 
degree_size_type in_degree (V &v) const
 in degree of a vertex More...
 
degree_size_type out_degree (V &v) const
 out degree of a vertex More...
 
edge disconection/reconnection
void disconnect_edge (int64_t p_from, int64_t p_to)
 Disconnects all edges from p_from to p_to. More...
 
void disconnect_out_going_edge (int64_t vertex_id, int64_t edge_id)
 Disconnects the outgoing edges of a vertex. More...
 
void disconnect_vertex (int64_t p_vertex)
 Disconnects all incoming and outgoing edges from the vertex. More...
 
void disconnect_vertex (V vertex)
 
void restore_graph ()
 Reconnects all edges that were removed. More...
 
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 When the vertex does not exist More...
 
V get_V (int64_t vid) const
 get the vertex descriptor of the vid Call has_vertex(vid) before calling this function 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...
 
only for stand by program
int64_t get_edge_id (V from, V to, double &distance) const
 
E get_edge (V from, V to, double &distance) const
 
size_t num_vertices () const
 
size_t num_edges () const
 
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_min_edge_no_parallel (const T &edge)
 
template<typename T >
void graph_add_neg_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...
 
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 When the vertex does not exist More...
 
V get_V (int64_t vid) const
 get the vertex descriptor of the vid Call has_vertex(vid) before calling this function 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...
 
only for stand by program
int64_t get_edge_id (V from, V to, double &distance) const
 
E get_edge (V from, V to, double &distance) const
 
size_t num_vertices () const
 
size_t num_edges () const
 
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_min_edge_no_parallel (const T &edge)
 
template<typename T >
void graph_add_neg_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...
 

Public Attributes

std::ostringstream log
 
Graph Modification
std::deque< T_E > removed_edges
 Used for storing the removed_edges. More...
 
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...
 
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

void apply_transformation (const pgrouting::DirectedGraph &digraph)
 
template<typename T >
void graph_add_edge (int64_t _id, const T &source, const T &target, int64_t source_in_edge, int64_t source_out_edge)
 
void insert_vertex (int64_t original_vertex_id, int64_t original_edge_id)
 
void store_edge_costs (const pgrouting::DirectedGraph &digraph)
 

Private Attributes

std::map< int64_t, double > m_edge_costs
 
int64_t m_num_edges
 
std::map< int64_t, std::pair< int64_t, int64_t > > m_transformation_map
 
std::map< std::pair< int64_t, int64_t >, int64_t > m_vertex_map
 

Friends

std::ostream & operator<< (std::ostream &log, const Pgr_lineGraphFull< 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
 

Insert edges

template<typename T >
void insert_edges (const T *edges, size_t count)
 Inserts count edges of type T into the graph. More...
 
template<typename T >
void insert_edges (T *edges, size_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 The set of edges should not have an illegal vertex defined When the graph is empty calls: More...
 
template<typename T >
void insert_edges_neg (const T *edges, size_t count)
 
template<typename T >
void insert_negative_edges (const T *edges, int64_t count)
 
template<typename T >
void insert_negative_edges (const std::vector< T > &edges, bool normal=true)
 
template<typename T >
void insert_min_edges_no_parallel (const T *edges, size_t count)
 
template<typename T >
void insert_min_edges_no_parallel (const std::vector< T > &edges)
 
void add_vertices (std::vector< T_V > vertices)
 adds the vertices into the graph More...
 

Detailed Description

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

Definition at line 47 of file pgr_lineGraphFull.hpp.

Member Typedef Documentation

◆ B_G

template<typename 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 226 of file pgr_base_graph.hpp.

◆ degree_size_type

template<typename 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 241 of file pgr_base_graph.hpp.

◆ E

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

Definition at line 50 of file pgr_lineGraphFull.hpp.

◆ E_i

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

Definition at line 52 of file pgr_lineGraphFull.hpp.

◆ edges_size_type

template<typename 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 239 of file pgr_base_graph.hpp.

◆ EI_i

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

Definition at line 54 of file pgr_lineGraphFull.hpp.

◆ EO_i

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

Definition at line 53 of file pgr_lineGraphFull.hpp.

◆ G_T_E

template<typename 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 227 of file pgr_base_graph.hpp.

◆ G_T_V

template<typename 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 228 of file pgr_base_graph.hpp.

◆ id_to_V

template<typename 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 253 of file pgr_base_graph.hpp.

◆ IndexMap

template<typename 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 271 of file pgr_base_graph.hpp.

◆ LI

template<typename 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 254 of file pgr_base_graph.hpp.

◆ V

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

Definition at line 49 of file pgr_lineGraphFull.hpp.

◆ V_i

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

Definition at line 51 of file pgr_lineGraphFull.hpp.

◆ vertices_size_type

template<typename 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 237 of file pgr_base_graph.hpp.

Constructor & Destructor Documentation

◆ Pgr_lineGraphFull() [1/2]

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

Definition at line 57 of file pgr_lineGraphFull.hpp.

58  : Pgr_base_graph< G, T_V, T_E >(gtype),
59  m_num_edges(0) {
60  }

◆ Pgr_lineGraphFull() [2/2]

template<class G , typename T_V , typename T_E >
pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::Pgr_lineGraphFull ( const pgrouting::DirectedGraph digraph)
inlineexplicit

Member Function Documentation

◆ add_vertices()

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

adds the vertices into the graph

PRECONDITIONS:

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

POSTCONDITIONS:

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

Example use:

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

Definition at line 462 of file pgr_base_graph.hpp.

463  {
464  pgassert(num_vertices() == 0);
465  for (const auto vertex : vertices) {
466  pgassert(!has_vertex(vertex.id));
467 
468  auto v = add_vertex(graph);
469  vertices_map[vertex.id] = v;
470  graph[v].cp_members(vertex);
471  // put(propmapIndex, v, num_vertices());
472 
473  pgassert(has_vertex(vertex.id));
474  }
475  // pgassert(mapIndex.size() == vertices.size());
476  pgassert(num_vertices() == vertices.size());
477  }

Referenced by pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_edges().

◆ adjacent()

template<typename 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 562 of file pgr_base_graph.hpp.

562  {
563  pgassert(is_source(v_idx, e_idx) || is_target(v_idx, e_idx));
564  return is_source(v_idx, e_idx)?
565  target(e_idx) :
566  source(e_idx);
567  }

Referenced by pgrouting::alphashape::Pgr_alphaShape::make_triangles().

◆ apply_transformation()

template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::apply_transformation ( const pgrouting::DirectedGraph digraph)
inlineprivate

Definition at line 229 of file pgr_lineGraphFull.hpp.

230  {
231  V_i vertexIt, vertexEnd;
232  EO_i e_outIt, e_outEnd;
233  EI_i e_inIt, e_inEnd;
234 
235  // For every vertex in the original graph, create a line graph
236  // using the edges connected to that vertex
237  for (boost::tie(vertexIt, vertexEnd) = boost::vertices(digraph.graph);
238  vertexIt != vertexEnd; vertexIt++) {
239  V vertex = *vertexIt;
240  auto vertex_id = digraph[vertex].id;
241  for (boost::tie(e_outIt, e_outEnd) =
242  boost::out_edges(vertex, digraph.graph);
243  e_outIt != e_outEnd; e_outIt++) {
244  auto out_edge_id = digraph.graph[*e_outIt].id;
245  insert_vertex(vertex_id, out_edge_id);
246  }
247 
248  for (boost::tie(e_inIt, e_inEnd) =
249  boost::in_edges(vertex, digraph.graph);
250  e_inIt != e_inEnd; e_inIt++) {
251  auto in_edge_id = digraph.graph[*e_inIt].id;
252  insert_vertex(vertex_id, in_edge_id);
253 
254  for (boost::tie(e_outIt, e_outEnd) =
255  boost::out_edges(vertex, digraph.graph);
256  e_outIt != e_outEnd; e_outIt++) {
257  auto out_edge_id = digraph.graph[*e_outIt].id;
258 
259  ++m_num_edges;
260 
262  m_num_edges,
263  vertex_id,
264  vertex_id,
265  in_edge_id,
266  out_edge_id);
267  }
268  }
269  }
270 
271  // Connect all of the line graphs that were just created using the
272  // edges from the original graph
273  for (boost::tie(vertexIt, vertexEnd) =
274  boost::vertices(digraph.graph);
275  vertexIt != vertexEnd; vertexIt++) {
276  V vertex = *vertexIt;
277  auto vertex_id = digraph[vertex].id;
278 
279  for (boost::tie(e_inIt, e_inEnd) =
280  boost::in_edges(vertex, digraph.graph);
281  e_inIt != e_inEnd; e_inIt++) {
282  auto source_vertex_id = digraph[digraph.source(*e_inIt)].id;
283  auto in_edge_id = digraph.graph[*e_inIt].id;
284 
285  ++m_num_edges;
286 
288  m_num_edges,
289  source_vertex_id,
290  vertex_id,
291  in_edge_id,
292  in_edge_id);
293  }
294  }
295  }

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::graph_add_edge(), pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::insert_vertex(), pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::m_num_edges, and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::source().

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

◆ disconnect_edge()

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)
    disconnect_edge(2,3) on an UNDIRECTED graph
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 765 of file pgr_base_graph.hpp.

765  {
766  T_E d_edge;
767 
768  // nothing to do, the vertex doesn't exist
769  if (!has_vertex(p_from) || !has_vertex(p_to)) return;
770 
771  EO_i out, out_end;
772  V g_from(get_V(p_from));
773  V g_to(get_V(p_to));
774 
775  // store the edges that are going to be removed
776  for (boost::tie(out, out_end) = out_edges(g_from, graph);
777  out != out_end; ++out) {
778  if (target(*out) == g_to) {
779  d_edge.id = graph[*out].id;
780  d_edge.source = graph[source(*out)].id;
781  d_edge.target = graph[target(*out)].id;
782  d_edge.cost = graph[*out].cost;
783  removed_edges.push_back(d_edge);
784  }
785  }
786  // the actual removal
787  boost::remove_edge(g_from, g_to, graph);
788 }

◆ disconnect_out_going_edge()

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

795  {
796  T_E d_edge;
797 
798  // nothing to do, the vertex doesn't exist
799  if (!has_vertex(vertex_id)) return;
800  auto v_from(get_V(vertex_id));
801 
802  EO_i out, out_end;
803  bool change = true;
804  // store the edge that are going to be removed
805  while (change) {
806  change = false;
807  for (boost::tie(out, out_end) = out_edges(v_from, graph);
808  out != out_end; ++out) {
809  if (graph[*out].id == edge_id) {
810  d_edge.id = graph[*out].id;
811  d_edge.source = graph[source(*out)].id;
812  d_edge.target = graph[target(*out)].id;
813  d_edge.cost = graph[*out].cost;
814  removed_edges.push_back(d_edge);
815  boost::remove_edge((*out), graph);
816  change = true;
817  break;
818  }
819  }
820  }
821 }

◆ disconnect_vertex() [1/2]

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)
    disconnect_vertex(2) on an UNDIRECTED graph
disconnect_vertex(2) on a DIRECTED graph
Parameters
[in]p_vertexoriginal vertex id of the starting point of the edge

Definition at line 826 of file pgr_base_graph.hpp.

826  {
827  if (!has_vertex(vertex)) return;
828  disconnect_vertex(get_V(vertex));
829 }

◆ disconnect_vertex() [2/2]

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

833  {
834  T_E d_edge;
835 
836  EO_i out, out_end;
837  // store the edges that are going to be removed
838  for (boost::tie(out, out_end) = out_edges(vertex, graph);
839  out != out_end; ++out) {
840  d_edge.id = graph[*out].id;
841  d_edge.source = graph[source(*out)].id;
842  d_edge.target = graph[target(*out)].id;
843  d_edge.cost = graph[*out].cost;
844  removed_edges.push_back(d_edge);
845  }
846 
847  // special case
848  if (m_gType == DIRECTED) {
849  EI_i in, in_end;
850  for (boost::tie(in, in_end) = in_edges(vertex, graph);
851  in != in_end; ++in) {
852  d_edge.id = graph[*in].id;
853  d_edge.source = graph[source(*in)].id;
854  d_edge.target = graph[target(*in)].id;
855  d_edge.cost = graph[*in].cost;
856  removed_edges.push_back(d_edge);
857  }
858  }
859 
860  // delete incoming and outgoing edges from the vertex
861  boost::clear_vertex(vertex, graph);
862 }

◆ get_edge()

template<typename G , typename T_V , typename T_E >
E pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_edge ( V  from,
V  to,
double &  distance 
) const
inlineinherited

Definition at line 671 of file pgr_base_graph.hpp.

674  {
675  E e;
676  EO_i out_i, out_end;
677  V v_source, v_target;
678  double minCost = (std::numeric_limits<double>::max)();
679  E minEdge;
680  bool valid = false;
681  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
682  out_i != out_end; ++out_i) {
683  e = *out_i;
684  if (!valid) {
685  minEdge = e;
686  valid = true;
687  }
688  v_target = target(e);
689  v_source = source(e);
690  if ((from == v_source) && (to == v_target)
691  && (distance == graph[e].cost)) {
692  return e;
693  }
694  if ((from == v_source) && (to == v_target)
695  && (minCost > graph[e].cost)) {
696  minCost = graph[e].cost;
697  minEdge = e;
698  }
699  }
700  return minEdge;
701  }

◆ get_edge_id()

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

881  {
882  E e;
883  EO_i out_i, out_end;
884  V v_source, v_target;
885  double minCost = (std::numeric_limits<double>::max)();
886  int64_t minEdge = -1;
887  for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
888  out_i != out_end; ++out_i) {
889  e = *out_i;
890  v_target = target(e);
891  v_source = source(e);
892  if ((from == v_source) && (to == v_target)
893  && (distance == graph[e].cost))
894  return graph[e].id;
895  if ((from == v_source) && (to == v_target)
896  && (minCost > graph[e].cost)) {
897  minCost = graph[e].cost;
898  minEdge = graph[e].id;
899  }
900  }
901  distance = minEdge == -1? 0: minCost;
902  return minEdge;
903 }

◆ get_postgres_results_directed()

template<class G , typename T_V , typename T_E >
std::vector< Line_graph_full_rt > pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::get_postgres_results_directed ( )
inline

Definition at line 89 of file pgr_lineGraphFull.hpp.

89  {
90  std::vector< Line_graph_full_rt > results;
91 
92  typename boost::graph_traits < G >::edge_iterator edgeIt, edgeEnd;
93  std::map <
94  std::pair<int64_t, int64_t >,
95  Line_graph_full_rt > unique;
96  auto count = 0;
97  auto vertex_count = 0;
98  std::map < int64_t, int64_t > vertex_id_map;
99  std::map < int64_t, int64_t > vertex_id_reverse_map;
100 
101  log << "\nPostgres results\n";
102  for (boost::tie(edgeIt, edgeEnd) = boost::edges(this->graph);
103  edgeIt != edgeEnd; edgeIt++) {
104  E e = *edgeIt;
105  auto e_source = this->graph[this->source(e)].vertex_id;
106  auto e_target = this->graph[this->target(e)].vertex_id;
107 
108  auto target_vertex_edge_pair = m_transformation_map[e_target];
109  auto target_vertex_id = target_vertex_edge_pair.first;
110  auto target_edge_id = target_vertex_edge_pair.second;
111  auto source_vertex_edge_pair = m_transformation_map[e_source];
112  auto source_vertex_id = source_vertex_edge_pair.first;
113  auto source_edge_id = source_vertex_edge_pair.second;
114 
115  int64_t edge_id = 0;
116  auto e_cost = 0.0;
117  if (source_edge_id == target_edge_id) {
118  e_cost = m_edge_costs[source_edge_id];
119  edge_id = source_edge_id;
120  }
121 
122  if (vertex_id_map.find(e_source) == vertex_id_map.end()) {
123  if (vertex_id_reverse_map.find(source_vertex_id) ==
124  vertex_id_reverse_map.end()) {
125  vertex_id_map[e_source] = source_vertex_id;
126  vertex_id_reverse_map[source_vertex_id] = e_source;
127  } else {
128  --vertex_count;
129  vertex_id_map[e_source] = vertex_count;
130  vertex_id_reverse_map[vertex_count] = e_source;
131  }
132  }
133 
134  if (vertex_id_map.find(e_target) == vertex_id_map.end()) {
135  if (vertex_id_reverse_map.find(target_vertex_id) ==
136  vertex_id_reverse_map.end()) {
137  vertex_id_map[e_target] = target_vertex_id;
138  vertex_id_reverse_map[target_vertex_id] = e_target;
139  } else {
140  --vertex_count;
141  vertex_id_map[e_target] = vertex_count;
142  vertex_id_reverse_map[vertex_count] = e_target;
143  }
144  }
145 
146 #if 0
147  log << "e_source = " << e_source
148  << " e_target = " << e_target
149  << "\n";
150 #endif
152  ++count,
153  vertex_id_map[e_source],
154  vertex_id_map[e_target],
155  e_cost,
156  edge_id
157  };
158 
159  unique[ std::pair<int64_t, int64_t>(e_source, e_target) ] =
160  edge;
161  }
162  for (const auto &edge : unique) {
163  results.push_back(edge.second);
164  }
165  return results;
166  }

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

◆ get_V() [1/2]

template<typename 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 512 of file pgr_base_graph.hpp.

512  {
513  auto vm_s(vertices_map.find(vertex.id));
514  if (vm_s == vertices_map.end()) {
515  auto v = add_vertex(graph);
516  graph[v].cp_members(vertex);
517  vertices_map[vertex.id] = v;
518  put(propmapIndex, v, num_vertices());
519  return v;
520  }
521  return vm_s->second;
522  }

Referenced by pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::graph_add_edge(), pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::graph_add_edge(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::graph_add_edge_no_create_vertex(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::in_degree(), and pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::out_degree().

◆ get_V() [2/2]

template<typename 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 528 of file pgr_base_graph.hpp.

528  {
529  pgassert(has_vertex(vid));
530  return vertices_map.find(vid)->second;
531  }

◆ graph_add_edge() [1/3]

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

936  {
937  bool inserted;
939  if ((edge.cost < 0) && (edge.reverse_cost < 0))
940  return;
941 
942  /*
943  * true: for source
944  * false: for target
945  */
946  auto vm_s = get_V(T_V(edge, true));
947  auto vm_t = get_V(T_V(edge, false));
948 
949  pgassert(vertices_map.find(edge.source) != vertices_map.end());
950  pgassert(vertices_map.find(edge.target) != vertices_map.end());
951  if (edge.cost >= 0) {
952  boost::tie(e, inserted) =
953  boost::add_edge(vm_s, vm_t, graph);
954  graph[e].cost = edge.cost;
955  graph[e].id = edge.id;
956  }
957 
958  if (edge.reverse_cost >= 0
959  && (m_gType == DIRECTED
960  || (m_gType == UNDIRECTED && edge.cost != edge.reverse_cost))) {
961  boost::tie(e, inserted) =
962  boost::add_edge(vm_t, vm_s, graph);
963 
964  graph[e].cost = edge.reverse_cost;
965  graph[e].id = normal? edge.id : -edge.id;
966  }
967 }

◆ graph_add_edge() [2/3]

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

908  {
909  typename Pgr_base_graph< G, T_V, T_E >::LI vm_s, vm_t;
911 
912  vm_s = vertices_map.find(edge.source);
913  if (vm_s == vertices_map.end()) {
915  vm_s = vertices_map.find(edge.source);
916  }
917 
918  vm_t = vertices_map.find(edge.target);
919  if (vm_t == vertices_map.end()) {
921  vm_t = vertices_map.find(edge.target);
922  }
923 
924  if (edge.cost >= 0) {
925  bool inserted;
926  boost::tie(e, inserted) =
927  boost::add_edge(vm_s->second, vm_t->second, graph);
928  graph[e].cp_members(edge);
929  }
930 }

Referenced by pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_edges().

◆ graph_add_edge() [3/3]

template<class G , typename T_V , typename T_E >
template<typename T >
void pgrouting::graph::Pgr_lineGraphFull< 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 
)
inlineprivate

Definition at line 194 of file pgr_lineGraphFull.hpp.

199  {
200  bool inserted;
201  E e;
202 
203  pgassert(m_vertex_map.find({source, source_in_edge}) !=
204  m_vertex_map.end());
205  pgassert(m_vertex_map.find({target, source_out_edge}) !=
206  m_vertex_map.end());
207 
208  auto index_source_edge =
209  m_vertex_map[ std::pair<int64_t, int64_t>(source,
210  source_in_edge) ];
211  auto index_target_edge =
212  m_vertex_map[ std::pair<int64_t, int64_t>(target,
213  source_out_edge) ];
214 
215  auto vm_s = this->get_V(index_source_edge);
216  auto vm_t = this->get_V(index_target_edge);
217 
218  pgassert(this->vertices_map.find(index_source_edge) !=
219  this->vertices_map.end());
220  pgassert(this->vertices_map.find(index_target_edge) !=
221  this->vertices_map.end());
222 
223  boost::tie(e, inserted) =
224  boost::add_edge(vm_s, vm_t, this->graph);
225 
226  this->graph[e].id = _id;
227  }

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::get_V(), pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::m_vertex_map, pgassert, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::source(), pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::target(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::vertices_map.

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

◆ graph_add_edge_no_create_vertex()

template<typename 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.

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 
750  if (edge.reverse_cost >= 0 && (is_directed()
751  || (is_undirected() && edge.cost != edge.reverse_cost))) {
752  boost::tie(e, inserted) =
753  boost::add_edge(vm_t, vm_s, graph);
754  graph[e].cost = edge.reverse_cost;
755  graph[e].id = edge.id;
756  }
757  }

Referenced by pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_edges().

◆ graph_add_min_edge_no_parallel()

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_min_edge_no_parallel ( const T &  edge)
inherited

Definition at line 972 of file pgr_base_graph.hpp.

972  {
973  bool inserted;
975  if ((edge.cost < 0) && (edge.reverse_cost < 0))
976  return;
977 
978  /*
979  * true: for source
980  * false: for target
981  */
982  auto vm_s = get_V(T_V(edge, true));
983  auto vm_t = get_V(T_V(edge, false));
984 
985  pgassert(vertices_map.find(edge.source) != vertices_map.end());
986  pgassert(vertices_map.find(edge.target) != vertices_map.end());
987  if (edge.cost >= 0) {
988  E e1;
989  bool found;
990  boost::tie(e1, found) = edge(vm_s, vm_t, graph);
991  if (found) {
992  if (edge.cost < graph[e1].cost) {
993  graph[e1].cost = edge.cost;
994  graph[e1].id = edge.id;
995  }
996  } else {
997  boost::tie(e, inserted) =
998  boost::add_edge(vm_s, vm_t, graph);
999  graph[e].cost = edge.cost;
1000  graph[e].id = edge.id;
1001  }
1002  }
1003 
1004  if (edge.reverse_cost >= 0
1005  && (m_gType == DIRECTED
1006  || (m_gType == UNDIRECTED && edge.cost != edge.reverse_cost))) {
1007  E e1;
1008  bool found;
1009  boost::tie(e1, found) = edge(vm_t, vm_s, graph);
1010  if (found) {
1011  if (edge.reverse_cost < graph[e1].cost) {
1012  graph[e1].cost = edge.reverse_cost;
1013  graph[e1].id = edge.id;
1014  }
1015  } else {
1016  boost::tie(e, inserted) =
1017  boost::add_edge(vm_t, vm_s, graph);
1018 
1019  graph[e].cost = edge.reverse_cost;
1020  graph[e].id = edge.id;
1021  }
1022  }
1023 }

Referenced by pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_min_edges_no_parallel().

◆ graph_add_neg_edge()

template<class G , typename T_V , typename T_E >
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph_add_neg_edge ( const T &  edge,
bool  normal = true 
)
inherited

Definition at line 1035 of file pgr_base_graph.hpp.

1035  {
1036  bool inserted;
1038 
1039  auto vm_s = get_V(T_V(edge, true));
1040  auto vm_t = get_V(T_V(edge, false));
1041 
1042  pgassert(vertices_map.find(edge.source) != vertices_map.end());
1043  pgassert(vertices_map.find(edge.target) != vertices_map.end());
1044 
1045  boost::tie(e, inserted) =
1046  boost::add_edge(vm_s, vm_t, graph);
1047  if (edge.cost < 0) {
1048  // reading negative edges as positive
1049  graph[e].cost = (-0.5)*edge.cost;
1050  } else {
1051  graph[e].cost = edge.cost;
1052  }
1053  graph[e].id = edge.id;
1054 
1055  if (m_gType == DIRECTED
1056  || (m_gType == UNDIRECTED && edge.cost > edge.reverse_cost)) {
1057  boost::tie(e, inserted) =
1058  boost::add_edge(vm_t, vm_s, graph);
1059  if (edge.reverse_cost < 0) {
1060  // reading negative edges as positive
1061  graph[e].cost = (-0.5)*edge.reverse_cost;
1062  } else {
1063  graph[e].cost = edge.reverse_cost;
1064  }
1065 
1066  graph[e].id = normal? edge.id : -edge.id;
1067  }
1068 }

Referenced by pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_negative_edges().

◆ has_vertex()

◆ in_degree() [1/2]

template<typename 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 497 of file pgr_base_graph.hpp.

497  {
498  if (!has_vertex(vertex_id)) {
499  return 0;
500  }
501  return is_directed()?
502  in_degree(get_V(vertex_id))
503  : out_degree(get_V(vertex_id));
504  }

Referenced by pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::in_degree().

◆ in_degree() [2/2]

template<typename 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 576 of file pgr_base_graph.hpp.

576  {
577  return is_directed()?
578  boost::in_degree(v, graph) :
579  boost::out_degree(v, graph);
580  }

◆ insert_edges() [1/3]

template<typename 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
      normal

Definition at line 395 of file pgr_base_graph.hpp.

395  {
396 #if 0
397  // This code does not work with contraction
398  if (num_vertices() == 0) {
399  auto vertices = pgrouting::extract_vertices(edges);
400  pgassert(pgrouting::check_vertices(vertices) == 0);
401  add_vertices(vertices);
402  }
403 #endif
404  for (const auto edge : edges) {
405  graph_add_edge(edge, normal);
406  }
407  }

◆ insert_edges() [2/3]

template<typename 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,
size_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 357 of file pgr_base_graph.hpp.

357  {
358  insert_edges(std::vector < T >(edges, edges + count));
359  }

Referenced by do_pgr_articulationPoints(), do_pgr_astarManyToMany(), do_pgr_bdAstar(), do_pgr_bdDijkstra(), do_pgr_bellman_ford(), do_pgr_bellman_ford_neg(), do_pgr_biconnectedComponents(), do_pgr_binaryBreadthFirstSearch(), do_pgr_bipartite(), do_pgr_boyerMyrvold(), do_pgr_breadthFirstSearch(), do_pgr_bridges(), do_pgr_combinations_dijkstra(), do_pgr_connectedComponents(), do_pgr_dagShortestPath(), do_pgr_depthFirstSearch(), do_pgr_dijkstraVia(), do_pgr_driving_many_to_dist(), do_pgr_edwardMoore(), do_pgr_floydWarshall(), do_pgr_isPlanar(), do_pgr_johnson(), do_pgr_kruskal(), do_pgr_ksp(), do_pgr_LTDTree(), do_pgr_makeConnected(), do_pgr_many_to_many_dijkstra(), do_pgr_many_withPointsDD(), do_pgr_randomSpanningTree(), do_pgr_sequentialVertexColoring(), do_pgr_stoerWagner(), do_pgr_strongComponents(), do_pgr_topologicalSort(), do_pgr_transitiveClosure(), do_pgr_turnRestrictedPath(), do_pgr_withPoints(), do_pgr_withPointsKsp(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_edges(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_edges_neg(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_min_edges_no_parallel(), and pgrouting::alphashape::Pgr_alphaShape::Pgr_alphaShape().

◆ insert_edges() [3/3]

template<typename 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,
size_t  count,
bool   
)
inlineinherited

Definition at line 367 of file pgr_base_graph.hpp.

367  {
368  for (size_t i = 0; i < count; ++i) {
369  pgassert(has_vertex(edges[i].source));
370  pgassert(has_vertex(edges[i].target));
372  }
373  }

◆ insert_edges_neg()

template<typename 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,
size_t  count 
)
inlineinherited

Definition at line 362 of file pgr_base_graph.hpp.

362  {
363  insert_edges(std::vector < T >(edges, edges + count), false);
364  }

Referenced by do_pgr_lineGraph(), and do_pgr_lineGraphFull().

◆ insert_min_edges_no_parallel() [1/2]

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

Definition at line 416 of file pgr_base_graph.hpp.

416  {
417  for (const auto edge : edges) {
419  }
420  }

◆ insert_min_edges_no_parallel() [2/2]

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

Definition at line 410 of file pgr_base_graph.hpp.

410  {
411  insert_edges(std::vector<T>(edges, edges + count));
412  }

Referenced by do_pgr_prim().

◆ insert_negative_edges() [1/2]

template<typename G , typename T_V , typename T_E >
template<typename T >
void pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::insert_negative_edges ( const std::vector< T > &  edges,
bool  normal = true 
)
inlineinherited

Definition at line 423 of file pgr_base_graph.hpp.

425  {
426  for (const auto edge : edges) {
427  graph_add_neg_edge(edge, normal);
428  }
429  }

◆ insert_negative_edges() [2/2]

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

Definition at line 376 of file pgr_base_graph.hpp.

376  {
377  insert_negative_edges(std::vector < T >(edges, edges + count));
378  }

Referenced by do_pgr_bellman_ford_neg(), and pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::insert_negative_edges().

◆ insert_vertex()

template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::insert_vertex ( int64_t  original_vertex_id,
int64_t  original_edge_id 
)
inlineprivate

Definition at line 169 of file pgr_lineGraphFull.hpp.

171  {
172  auto new_id = static_cast<int64_t>(this->num_vertices() + 1);
173  m_transformation_map[new_id] =
174  std::pair<int64_t, int64_t>(original_vertex_id, original_edge_id);
175  m_vertex_map[std::pair<int64_t, int64_t>(original_vertex_id,
176  original_edge_id)] =
177  new_id;
178  auto v = add_vertex(this->graph);
179  this->graph[v].cp_members(original_vertex_id, original_edge_id);
180  this->graph[v].vertex_id = new_id;
181  this->vertices_map[new_id] = v;
182  }

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

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

◆ is_directed()

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

◆ is_source()

template<typename 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 545 of file pgr_base_graph.hpp.

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

Referenced by pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::adjacent().

◆ is_target()

template<typename 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 546 of file pgr_base_graph.hpp.

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

Referenced by pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::adjacent().

◆ is_undirected()

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

◆ num_edges()

template<typename 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 704 of file pgr_base_graph.hpp.

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

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

◆ num_vertices()

◆ operator[]() [1/4]

template<typename 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 554 of file pgr_base_graph.hpp.

554 {return graph[e_idx];}

◆ operator[]() [2/4]

template<typename 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 555 of file pgr_base_graph.hpp.

555 {return graph[e_idx];}

◆ operator[]() [3/4]

template<typename 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 557 of file pgr_base_graph.hpp.

557 {return graph[v_idx];}

◆ operator[]() [4/4]

template<typename 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 558 of file pgr_base_graph.hpp.

558 {return graph[v_idx];}

◆ out_degree() [1/2]

template<typename 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 489 of file pgr_base_graph.hpp.

489  {
490  if (!has_vertex(vertex_id)) {
491  return 0;
492  }
493  auto v = get_V(vertex_id);
494  auto d = out_degree(v);
495  return d;
496  }

Referenced by pgrouting::algorithms::bridges(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::in_degree(), and pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::out_degree().

◆ out_degree() [2/2]

template<typename 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 587 of file pgr_base_graph.hpp.

587  {
588  return boost::out_degree(v, graph);
589  }

◆ restore_graph()

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

866  {
867  while (removed_edges.size() != 0) {
869  removed_edges.pop_front();
870  }
871 }

◆ source()

◆ store_edge_costs()

template<class G , typename T_V , typename T_E >
void pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::store_edge_costs ( const pgrouting::DirectedGraph digraph)
inlineprivate

Definition at line 184 of file pgr_lineGraphFull.hpp.

185  {
186  E_i e_It, e_End;
187  for (boost::tie(e_It, e_End) = boost::edges(digraph.graph);
188  e_It != e_End; e_It++) {
189  m_edge_costs[digraph.graph[*e_It].id] = digraph.graph[*e_It].cost;
190  }
191  }

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

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

◆ target()

Friends And Related Function Documentation

◆ operator<<

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

Definition at line 68 of file pgr_lineGraphFull.hpp.

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

Member Data Documentation

◆ graph

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

The graph.

Definition at line 260 of file pgr_base_graph.hpp.

Referenced by pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::add_one_vertex(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::add_vertices(), pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::apply_transformation(), pgrouting::algorithms::articulationPoints(), pgrouting::algorithms::biconnectedComponents(), pgrouting::algorithms::bridges(), pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::create_edges(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::get_edge(), pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::get_postgres_results_directed(), pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::get_postgres_results_directed(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::get_V(), pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::graph_add_edge(), pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::graph_add_edge(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::graph_add_edge_no_create_vertex(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::in_degree(), pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::insert_vertex(), pgrouting::graph::Pgr_lineGraph< G, T_V, T_E >::insert_vertices(), pgrouting::alphashape::Pgr_alphaShape::make_triangles(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::num_edges(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::num_vertices(), pgrouting::alphashape::Pgr_alphaShape::operator()(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::operator[](), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::out_degree(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::Pgr_base_graph(), pgrouting::algorithms::pgr_connectedComponents(), pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::source(), pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::store_edge_costs(), pgrouting::algorithms::strongComponents(), and pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >::target().

◆ log

template<class G , typename T_V , typename T_E >
std::ostringstream pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::log

◆ m_edge_costs

template<class G , typename T_V , typename T_E >
std::map< int64_t, double > pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::m_edge_costs
private

◆ m_gType

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

◆ m_num_edges

template<class G , typename T_V , typename T_E >
int64_t pgrouting::graph::Pgr_lineGraphFull< G, T_V, T_E >::m_num_edges
private

◆ m_transformation_map

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

◆ m_vertex_map

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

◆ mapIndex

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

Definition at line 272 of file pgr_base_graph.hpp.

◆ propmapIndex

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

◆ removed_edges

template<typename 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 281 of file pgr_base_graph.hpp.

◆ vertices_map

◆ vertIndex

template<typename 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

The documentation for this class was generated from the following file:
pgrouting::graph::Pgr_base_graph::graph_add_edge_no_create_vertex
void graph_add_edge_no_create_vertex(const T &edge)
Use this function when the vertices are already inserted in the graph.
Definition: pgr_base_graph.hpp:721
pgrouting::graph::Pgr_base_graph::propmapIndex
boost::associative_property_map< IndexMap > propmapIndex
Definition: pgr_base_graph.hpp:273
pgrouting::graph::Pgr_lineGraphFull::log
std::ostringstream log
Definition: pgr_lineGraphFull.hpp:304
pgrouting::graph::Pgr_lineGraphFull::m_num_edges
int64_t m_num_edges
Definition: pgr_lineGraphFull.hpp:298
pgrouting::graph::Pgr_lineGraphFull::insert_vertex
void insert_vertex(int64_t original_vertex_id, int64_t original_edge_id)
Definition: pgr_lineGraphFull.hpp:169
pgrouting::graph::Pgr_base_graph::graph
G graph
The graph.
Definition: pgr_base_graph.hpp:260
edge::reverse_cost
float8 reverse_cost
Definition: trsp.h:46
pgrouting::graph::Pgr_base_graph::insert_negative_edges
void insert_negative_edges(const T *edges, int64_t count)
Definition: pgr_base_graph.hpp:376
pgrouting::graph::Pgr_lineGraphFull::V_i
boost::graph_traits< G >::vertex_iterator V_i
Definition: pgr_lineGraphFull.hpp:51
pgrouting::graph::Pgr_base_graph::out_degree
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
Definition: pgr_base_graph.hpp:489
edge::cost
float8 cost
Definition: trsp.h:45
edge::target
int64 target
Definition: trsp.h:44
pgrouting::graph::Pgr_base_graph::m_gType
graphType m_gType
type (DIRECTED or UNDIRECTED)
Definition: pgr_base_graph.hpp:261
pgrouting::graph::Pgr_base_graph::LI
id_to_V::const_iterator LI
Definition: pgr_base_graph.hpp:254
pgrouting::graph::Pgr_base_graph::is_source
bool is_source(V v_idx, E e_idx) const
Definition: pgr_base_graph.hpp:545
pgrouting::graph::Pgr_base_graph::target
V target(E e_idx) const
Definition: pgr_base_graph.hpp:561
pgrouting::graph::Pgr_base_graph::EI_i
boost::graph_traits< G >::in_edge_iterator EI_i
Definition: pgr_base_graph.hpp:234
pgrouting::check_vertices
size_t check_vertices(std::vector< Basic_vertex > vertices)
Definition: basic_vertex.cpp:42
pgassertwm
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:117
pgrouting::graph::Pgr_lineGraphFull::store_edge_costs
void store_edge_costs(const pgrouting::DirectedGraph &digraph)
Definition: pgr_lineGraphFull.hpp:184
pgrouting::graph::Pgr_lineGraphFull::m_edge_costs
std::map< int64_t, double > m_edge_costs
Definition: pgr_lineGraphFull.hpp:299
pgrouting::graph::Pgr_base_graph::has_vertex
bool has_vertex(int64_t vid) const
True when vid is in the graph.
Definition: pgr_base_graph.hpp:534
edge
Definition: trsp.h:41
pgrouting::graph::Pgr_lineGraphFull::apply_transformation
void apply_transformation(const pgrouting::DirectedGraph &digraph)
Definition: pgr_lineGraphFull.hpp:229
pgassert
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
pgrouting::graph::Pgr_lineGraphFull::m_transformation_map
std::map< int64_t, std::pair< int64_t, int64_t > > m_transformation_map
Definition: pgr_lineGraphFull.hpp:300
UNDIRECTED
@ UNDIRECTED
Definition: graph_enum.h:30
pgrouting::graph::Pgr_base_graph::insert_edges
void insert_edges(const T *edges, size_t count)
Inserts count edges of type T into the graph.
Definition: pgr_base_graph.hpp:357
pgrouting::graph::Pgr_base_graph::get_V
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex When the vertex does not exist
Definition: pgr_base_graph.hpp:512
pgrouting::graph::Pgr_base_graph::is_target
bool is_target(V v_idx, E e_idx) const
Definition: pgr_base_graph.hpp:546
pgrouting::graph::Pgr_base_graph::graph_add_neg_edge
void graph_add_neg_edge(const T &edge, bool normal=true)
Definition: pgr_base_graph.hpp:1035
pgrouting::graph::Pgr_base_graph::source
V source(E e_idx) const
Definition: pgr_base_graph.hpp:560
pgrouting::graph::Pgr_base_graph::E
boost::graph_traits< G >::edge_descriptor E
Definition: pgr_base_graph.hpp:230
pgrouting::graph::Pgr_base_graph::is_directed
bool is_directed() const
Definition: pgr_base_graph.hpp:543
pgrouting::graph::Pgr_lineGraphFull::E
boost::graph_traits< G >::edge_descriptor E
Definition: pgr_lineGraphFull.hpp:50
edge::source
int64 source
Definition: trsp.h:43
pgrouting::graph::Pgr_base_graph::num_vertices
size_t num_vertices() const
Definition: pgr_base_graph.hpp:703
pgrouting::graph::Pgr_base_graph::removed_edges
std::deque< T_E > removed_edges
Used for storing the removed_edges.
Definition: pgr_base_graph.hpp:281
pgrouting::graph::Pgr_base_graph::add_vertices
void add_vertices(std::vector< T_V > vertices)
adds the vertices into the graph
Definition: pgr_base_graph.hpp:462
pgrouting::graph::Pgr_base_graph::EO_i
boost::graph_traits< G >::out_edge_iterator EO_i
Definition: pgr_base_graph.hpp:233
DIRECTED
@ DIRECTED
Definition: graph_enum.h:30
pgrouting::graph::Pgr_base_graph::is_undirected
bool is_undirected() const
Definition: pgr_base_graph.hpp:544
pgrouting::graph::Pgr_lineGraphFull::EI_i
boost::graph_traits< G >::in_edge_iterator EI_i
Definition: pgr_lineGraphFull.hpp:54
pgrouting::graph::Pgr_base_graph::graph_add_min_edge_no_parallel
void graph_add_min_edge_no_parallel(const T &edge)
Definition: pgr_base_graph.hpp:972
edge::id
int64 id
Definition: trsp.h:42
pgrouting::graph::Pgr_base_graph::V
boost::graph_traits< G >::vertex_descriptor V
Definition: pgr_base_graph.hpp:229
pgrouting::graph::Pgr_lineGraphFull::V
boost::graph_traits< G >::vertex_descriptor V
Definition: pgr_lineGraphFull.hpp:49
pgrouting::graph::Pgr_base_graph
Definition: pgr_base_graph.hpp:168
pgrouting::graph::Pgr_base_graph::graph_add_edge
void graph_add_edge(const T_E &edge)
Definition: pgr_base_graph.hpp:908
pgrouting::graph::Pgr_lineGraphFull::E_i
boost::graph_traits< G >::edge_iterator E_i
Definition: pgr_lineGraphFull.hpp:52
pgrouting::graph::Pgr_base_graph::disconnect_vertex
void disconnect_vertex(int64_t p_vertex)
Disconnects all incoming and outgoing edges from the vertex.
Definition: pgr_base_graph.hpp:826
pgrouting::extract_vertices
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
Definition: basic_vertex.cpp:59
pgrouting::graph::Pgr_lineGraphFull::EO_i
boost::graph_traits< G >::out_edge_iterator EO_i
Definition: pgr_lineGraphFull.hpp:53
pgrouting::graph::Pgr_base_graph::in_degree
degree_size_type in_degree(int64_t vertex_id) const
Definition: pgr_base_graph.hpp:497
pgrouting::graph::Pgr_lineGraphFull::m_vertex_map
std::map< std::pair< int64_t, int64_t >, int64_t > m_vertex_map
Definition: pgr_lineGraphFull.hpp:301
pgrouting::graph::Pgr_lineGraphFull::graph_add_edge
void graph_add_edge(int64_t _id, const T &source, const T &target, int64_t source_in_edge, int64_t source_out_edge)
Definition: pgr_lineGraphFull.hpp:194
Line_graph_full_rt
Definition: line_graph_full_rt.h:42
pgrouting::graph::Pgr_base_graph::vertices_map
id_to_V vertices_map
id -> graph id
Definition: pgr_base_graph.hpp:267