PGROUTING  2.6
Pgr_components< G > Class Template Reference

#include "pgr_components.hpp"

Public Types

typedef G::E E
 
typedef G::E_i E_i
 
typedef G::V V
 

Public Member Functions

std::vector< pgr_components_rtarticulationPoints (G &graph)
 Articulation Points. More...
 
std::vector< pgr_components_rtbiconnectedComponents (G &graph)
 Biconnected Components. More...
 
std::vector< pgr_components_rtbridges (G &graph)
 Bridges. More...
 
std::vector< pgr_components_rtconnectedComponents (G &graph)
 Connected Components Vertex Version. More...
 
std::vector< pgr_components_rtstrongComponents (G &graph)
 Strongly Connected Components Vertex Version. More...
 

Private Member Functions

std::vector< pgr_components_rtgenerate_results (std::vector< std::vector< int64_t > >)
 Generate Results, Vertex Version. More...
 

Detailed Description

template<class G>
class Pgr_components< G >

Definition at line 44 of file pgr_components.hpp.

Member Typedef Documentation

template<class G>
typedef G::E Pgr_components< G >::E

Definition at line 54 of file pgr_components.hpp.

template<class G>
typedef G::E_i Pgr_components< G >::E_i

Definition at line 55 of file pgr_components.hpp.

template<class G>
typedef G::V Pgr_components< G >::V

Definition at line 53 of file pgr_components.hpp.

Member Function Documentation

template<class G >
std::vector< pgr_components_rt > Pgr_components< G >::articulationPoints ( G &  graph)

Articulation Points.

Definition at line 186 of file pgr_components.hpp.

References pgr_components_rt::identifier.

Referenced by pgr_articulationPoints().

187  {
188  // perform the algorithm
189  std::vector <size_t> art_points;
190  boost::articulation_points(graph.graph, std::back_inserter(art_points));
191 
192  // get the results
193  std::vector <pgr_components_rt> results;
194  size_t totalArtp = art_points.size();
195  results.resize(totalArtp);
196  for (size_t i = 0; i < totalArtp; i++)
197  results[i].identifier = graph[art_points[i]].id;
198 
199  // sort identifier
200  std::sort(results.begin(), results.end(),
201  [](const pgr_components_rt &left, const pgr_components_rt &right) {
202  return left.identifier < right.identifier; });
203 
204  return results;
205 }

Here is the caller graph for this function:

template<class G >
std::vector< pgr_components_rt > Pgr_components< G >::biconnectedComponents ( G &  graph)

Biconnected Components.

Definition at line 160 of file pgr_components.hpp.

References Pgr_components< G >::generate_results().

Referenced by pgr_biconnectedComponents().

161  {
162  // perform the algorithm
163  struct order_edges {
164  bool operator() (const E &left, const E &right) const {
165  return left.get_property() < right.get_property();
166  }
167  };
168  typedef std::map< E, size_t > edge_map;
169  edge_map bicmp_map;
170 
171  boost::associative_property_map< edge_map > bimap(bicmp_map);
172  size_t num_comps = biconnected_components(graph.graph, bimap);
173 
174  // get the results
175  E_i ei, ei_end;
176  std::vector< std::vector< int64_t > > components(num_comps);
177  for (boost::tie(ei, ei_end) = edges(graph.graph); ei != ei_end; ei++)
178  components[bimap[*ei]].push_back(graph[*ei].id);
179 
180  return generate_results(components);
181 }
std::vector< pgr_components_rt > generate_results(std::vector< std::vector< int64_t > >)
Generate Results, Vertex Version.

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G >
std::vector< pgr_components_rt > Pgr_components< G >::bridges ( G &  graph)

Bridges.

Definition at line 210 of file pgr_components.hpp.

References pgr_components_rt::identifier.

Referenced by pgr_bridges().

211  {
212  size_t totalNodes = num_vertices(graph.graph);
213  std::vector< int > tmp_comp(totalNodes);
214  std::vector <pgr_components_rt> results;
215  int ini_comps = boost::connected_components(graph.graph, &tmp_comp[0]);
216 
217  // perform the algorithm
218  E_i ei, ei_end;
219  std::vector< std::pair<E, int64_t> > stored_edges;
220  for (boost::tie(ei, ei_end) = edges(graph.graph); ei != ei_end; ++ei) {
221  stored_edges.push_back(std::make_pair(*ei, graph[*ei].id));
222  }
223 
224  for (const auto pair_edge : stored_edges) {
225  E edge = pair_edge.first;
226 
227  boost::remove_edge(edge, graph.graph);
228 
229  int now_comps = boost::connected_components(graph.graph, &tmp_comp[0]);
230  if (now_comps > ini_comps) {
231  pgr_components_rt temp;
232  temp.identifier = pair_edge.second;
233  results.push_back(temp);
234  }
235 
236  boost::add_edge(boost::source(edge, graph.graph),
237  boost::target(edge, graph.graph),
238  graph.graph);
239  }
240 
241  // sort identifier
242  std::sort(results.begin(), results.end(),
243  [](const pgr_components_rt &left, const pgr_components_rt &right) {
244  return left.identifier < right.identifier; });
245 
246  return results;
247 }
Definition: trsp.h:31

Here is the caller graph for this function:

template<class G >
std::vector< pgr_components_rt > Pgr_components< G >::connectedComponents ( G &  graph)

Connected Components Vertex Version.

Definition at line 117 of file pgr_components.hpp.

References Pgr_components< G >::generate_results().

Referenced by pgr_connectedComponents().

118  {
119  size_t totalNodes = num_vertices(graph.graph);
120 
121  // perform the algorithm
122  std::vector< int > components(totalNodes);
123  int num_comps = boost::connected_components(graph.graph, &components[0]);
124 
125  // get the results
126  std::vector< std::vector< int64_t > > results;
127  results.resize(num_comps);
128  for (size_t i = 0; i < totalNodes; i++)
129  results[components[i]].push_back(graph[i].id);
130 
131  return generate_results(results);
132 }
std::vector< pgr_components_rt > generate_results(std::vector< std::vector< int64_t > >)
Generate Results, Vertex Version.

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G >
std::vector< pgr_components_rt > Pgr_components< G >::generate_results ( std::vector< std::vector< int64_t > >  components)
private

Generate Results, Vertex Version.

Definition at line 89 of file pgr_components.hpp.

References pgr_components_rt::component, pgr_components_rt::identifier, and pgr_components_rt::n_seq.

Referenced by Pgr_components< G >::biconnectedComponents(), Pgr_components< G >::connectedComponents(), and Pgr_components< G >::strongComponents().

90  {
91  // sort identifier
92  size_t num_comps = components.size();
93  for (size_t i = 0; i < num_comps; i++) {
94  std::sort(components[i].begin(), components[i].end());
95  }
96  sort(components.begin(), components.end());
97 
98  // generate results
99  std::vector< pgr_components_rt > results;
100  for (size_t i = 0; i < num_comps; i++) {
101  int64_t tempComp = components[i][0];
102  size_t sizeCompi = components[i].size();
103  for (size_t j = 0; j < sizeCompi; j++) {
104  pgr_components_rt tmp;
105  tmp.identifier = components[i][j];
106  tmp.n_seq = static_cast< int > (j + 1);
107  tmp.component = tempComp;
108  results.push_back(tmp);
109  }
110  }
111  return results;
112 }

Here is the caller graph for this function:

template<class G >
std::vector< pgr_components_rt > Pgr_components< G >::strongComponents ( G &  graph)

Strongly Connected Components Vertex Version.

Definition at line 137 of file pgr_components.hpp.

References Pgr_components< G >::generate_results().

Referenced by pgr_strongComponents().

138  {
139  size_t totalNodes = num_vertices(graph.graph);
140 
141  // perform the algorithm
142  std::vector< int > components(totalNodes);
143  int num_comps = boost::strong_components(graph.graph,
144  boost::make_iterator_property_map(components.begin(),
145  get(boost::vertex_index,
146  graph.graph)));
147 
148  // get the results
149  std::vector< std::vector< int64_t > > results;
150  results.resize(num_comps);
151  for (size_t i = 0; i < totalNodes; i++)
152  results[components[i]].push_back(graph[i].id);
153 
154  return generate_results(results);
155 }
std::vector< pgr_components_rt > generate_results(std::vector< std::vector< int64_t > >)
Generate Results, Vertex Version.

Here is the call graph for this function:

Here is the caller graph for this function:


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