PGROUTING  3.1
pgrouting::algorithms Namespace Reference

Namespaces

 detail
 

Classes

class  Pgr_astar
 

Functions

Identifiers< int64_t > articulationPoints (pgrouting::UndirectedGraph &graph)
 Articulation Points. More...
 
std::vector< pgr_components_rtbiconnectedComponents (pgrouting::UndirectedGraph &graph)
 Biconnected Components. More...
 
Identifiers< int64_t > bridges (pgrouting::UndirectedGraph &graph)
 Bridges Bridges are closely related to the concept of articulation vertices, vertices that belong to every path between some pair of other vertices. More...
 
std::vector< pgr_components_rtpgr_connectedComponents (pgrouting::UndirectedGraph &graph)
 works for undirected graph More...
 
std::vector< pgr_components_rtstrongComponents (pgrouting::DirectedGraph &graph)
 Strongly Connected Components Vertex Version. More...
 

Function Documentation

◆ articulationPoints()

Identifiers< int64_t > pgrouting::algorithms::articulationPoints ( pgrouting::UndirectedGraph graph)

Articulation Points.

Definition at line 126 of file pgr_components.cpp.

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

Referenced by do_pgr_articulationPoints().

127  {
129  using V = G::V;
130  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
131  CHECK_FOR_INTERRUPTS();
132 
133  // perform the algorithm
134  std::vector<V> art_points;
135  try {
136  boost::articulation_points(graph.graph, std::back_inserter(art_points));
137  } catch (...) {
138  throw;
139  }
140 
141  // get the results
142  Identifiers<int64_t> results;
143  for (const auto v : art_points) {
144  results += graph[v].id;
145  }
146 
147  return results;
148 }
boost::graph_traits< BG >::vertex_descriptor V
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
graph::Pgr_base_graph< boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Basic_vertex, Basic_edge >, Basic_vertex, Basic_edge > UndirectedGraph

◆ biconnectedComponents()

std::vector< pgr_components_rt > pgrouting::algorithms::biconnectedComponents ( pgrouting::UndirectedGraph graph)

Biconnected Components.

Biconnected Components (for undirected)

Definition at line 101 of file pgr_components.cpp.

References pgrouting::algorithms::detail::componentsResult(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph.

Referenced by do_pgr_biconnectedComponents().

102  {
104  using E = G::E;
105  using Edge_map = std::map< E, size_t >;
106 
107  // perform the algorithm
108  Edge_map bicmp_map;
109  boost::associative_property_map<Edge_map> bimap(bicmp_map);
110  size_t num_comps;
111  try {
112  num_comps = biconnected_components(graph.graph, bimap);
113  } catch (...) {
114  throw;
115  }
116 
117  std::vector< std::vector< int64_t > > results(num_comps);
118  for (auto ed : boost::make_iterator_range(edges(graph.graph))) {
119  results[bimap[ed]].push_back(graph[ed].id);
120  }
121 
122  return detail::componentsResult(results);
123 }
boost::graph_traits< BG >::edge_descriptor E
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
std::vector< pgr_components_rt > componentsResult(std::vector< std::vector< int64_t > > &components)
graph::Pgr_base_graph< boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Basic_vertex, Basic_edge >, Basic_vertex, Basic_edge > UndirectedGraph

◆ bridges()

Identifiers< int64_t > pgrouting::algorithms::bridges ( pgrouting::UndirectedGraph graph)

Bridges Bridges are closely related to the concept of articulation vertices, vertices that belong to every path between some pair of other vertices.

Bridges.

The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints.

Analogously to bridgeless graphs being 2-edge-connected, graphs without articulation vertices are 2-vertex-connected.

Definition at line 162 of file pgr_components.cpp.

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

Referenced by do_pgr_bridges().

162  {
164  using V = G::V;
165  using EO_i = G::EO_i;
166 
167  Identifiers<int64_t> bridge_edges;
168  Identifiers<int64_t> processed_edges;
169  std::vector<V> components(num_vertices(graph.graph));
170  size_t ini_comps;
171  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
172  CHECK_FOR_INTERRUPTS();
173  try {
174  ini_comps = boost::connected_components(graph.graph, &components[0]);
175  } catch (...) {
176  throw;
177  }
178  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
179  CHECK_FOR_INTERRUPTS();
180  std::vector<V> art_points;
181  try {
182  boost::articulation_points(graph.graph, std::back_inserter(art_points));
183  } catch (...) {
184  throw;
185  }
186 
187  for (auto v : boost::make_iterator_range(vertices(graph.graph))) {
188  if (graph.out_degree(v) == 1) {
189  art_points.push_back(v);
190  }
191  }
192 
193  for (const auto u : art_points) {
194  for (const auto v : art_points) {
195  /*
196  * skip when the vertices are the same and do half the work
197  */
198  if (u < v) continue;
199  auto p = boost::edge(u, v, graph.graph);
200 
201  /*
202  * skip when there is no edge (u, v) on the graph
203  */
204  if (!p.second) continue;
205  auto edge = p.first;
206  auto id = graph[edge].id;
207 
208  /*
209  * Skip when the edge has already being processed
210  */
211  if (processed_edges.has(id)) continue;
212 
213  /*
214  * Processing edge
215  */
216  processed_edges += id;
217 
218 
219  /*
220  * At least one edge between articulation points u & v
221  */
222  int parallel_count = 0;
223  EO_i ei, ei_end;
224  boost::tie(ei, ei_end) = out_edges(u, graph.graph);
225 
226  for ( ; ei != ei_end; ++ei) {
227  if (target(*ei, graph.graph) == v) ++parallel_count;
228  }
229 
230  if (parallel_count == 1) {
231  // TODO(vicky) filter graph instead of removing edges
232  size_t now_comps;
233  try {
234  boost::remove_edge(edge, graph.graph);
235 
236  now_comps = boost::connected_components(graph.graph, &components[0]);
237 
238  boost::add_edge(boost::source(edge, graph.graph),
239  boost::target(edge, graph.graph),
240  graph.graph);
241  } catch (...) {
242  throw;
243  }
244 
245  if (now_comps > ini_comps) {
246  bridge_edges += id;
247  }
248  }
249  }
250  }
251 
252  return bridge_edges;
253 }
Definition: trsp.h:41
boost::graph_traits< BG >::vertex_descriptor V
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
bool has(const T other) const
true ids() has element
Definition: identifiers.hpp:98
degree_size_type out_degree(int64_t vertex_id) const
get the out-degree of a vertex
graph::Pgr_base_graph< boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Basic_vertex, Basic_edge >, Basic_vertex, Basic_edge > UndirectedGraph

◆ pgr_connectedComponents()

std::vector< pgr_components_rt > pgrouting::algorithms::pgr_connectedComponents ( pgrouting::UndirectedGraph graph)

works for undirected graph

Definition at line 47 of file pgr_components.cpp.

References pgrouting::algorithms::detail::componentsResult(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph.

Referenced by do_pgr_connectedComponents().

47  {
49  // perform the algorithm
50  std::vector<V> components(num_vertices(graph.graph));
51  size_t num_comps;
52  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
53  CHECK_FOR_INTERRUPTS();
54  try {
55  num_comps = boost::connected_components(graph.graph, &components[0]);
56  } catch (...) {
57  throw;
58  }
59 
60  // get the results
61  std::vector< std::vector< int64_t > > results(num_comps);
62  for (auto vd : boost::make_iterator_range(vertices(graph.graph))) {
63  results[components[vd]].push_back(graph[vd].id);
64  }
65 
66  return detail::componentsResult(results);
67 }
boost::graph_traits< BG >::vertex_descriptor V
std::vector< pgr_components_rt > componentsResult(std::vector< std::vector< int64_t > > &components)
boost::graph_traits< G >::vertex_descriptor V

◆ strongComponents()

std::vector< pgr_components_rt > pgrouting::algorithms::strongComponents ( pgrouting::DirectedGraph graph)

Strongly Connected Components Vertex Version.

Definition at line 71 of file pgr_components.cpp.

References pgrouting::algorithms::detail::componentsResult(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph.

Referenced by do_pgr_strongComponents().

72  {
74  // perform the algorithm
75  std::vector<V> components(num_vertices(graph.graph));
76  size_t num_comps;
77  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
78  CHECK_FOR_INTERRUPTS();
79  try {
80  num_comps = boost::strong_components(
81  graph.graph,
82  boost::make_iterator_property_map(components.begin(),
83  get(boost::vertex_index, graph.graph)));
84  } catch (...) {
85  throw;
86  }
87 
88  // get the results
89  std::vector< std::vector< int64_t > > results(num_comps);
90  for (auto vd : boost::make_iterator_range(vertices(graph.graph))) {
91  results[components[vd]].push_back(graph[vd].id);
92  }
93 
94  return detail::componentsResult(results);
95 }
boost::graph_traits< BG >::vertex_descriptor V
std::vector< pgr_components_rt > componentsResult(std::vector< std::vector< int64_t > > &components)
boost::graph_traits< G >::vertex_descriptor V