PGROUTING  2.6-dev
pgr_components.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 Copyright (c) 2017 Maoguang Wang
7 Mail: xjtumg1007@gmail.com
8 
9 ------
10 
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15 
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20 
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 
25 ********************************************************************PGR-GNU*/
26 
27 #ifndef INCLUDE_COMPONENTS_PGR_COMPONENTS_HPP_
28 #define INCLUDE_COMPONENTS_PGR_COMPONENTS_HPP_
29 #pragma once
30 
31 #include <boost/config.hpp>
32 #include <boost/graph/adjacency_list.hpp>
33 #include <boost/graph/connected_components.hpp>
34 #include <boost/graph/strong_components.hpp>
35 #include <boost/graph/biconnected_components.hpp>
36 
37 #include <vector>
38 #include <map>
39 #include <utility>
40 #include <algorithm>
41 
42 #include "pgr_componentsGraph.hpp"
43 
44 template < class G > class Pgr_components;
45 // user's functions
46 // for development
47 
48 //******************************************
49 
50 template < class G >
51 class Pgr_components {
52  public:
53  typedef typename G::V V;
54  typedef typename G::E E;
55  typedef typename G::E_i E_i;
56 
58  std::vector<pgr_components_rt> connectedComponents(
59  G &graph);
60 
62  std::vector<pgr_components_rt> strongComponents(
63  G &graph);
64 
66  std::vector<pgr_components_rt> biconnectedComponents(
67  G &graph);
68 
70  std::vector<pgr_components_rt> articulationPoints(
71  G &graph);
72 
74  std::vector<pgr_components_rt> bridges(
75  G &graph);
76 
77  private:
79  std::vector<pgr_components_rt> generate_results(
80  std::vector< std::vector< int64_t > >);
81 };
82 
83 
84 /******************** IMPLEMENTTION ******************/
85 
87 template < class G >
88 std::vector<pgr_components_rt>
90  std::vector< std::vector< int64_t > > components) {
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 }
113 
115 template < class G >
116 std::vector<pgr_components_rt>
118  G &graph) {
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 }
133 
135 template < class G >
136 std::vector<pgr_components_rt>
138  G &graph) {
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 }
156 
158 template < class G >
159 std::vector<pgr_components_rt>
161  G &graph) {
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 }
182 
184 template < class G >
185 std::vector<pgr_components_rt>
187  G &graph) {
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 }
206 
208 template < class G >
209 std::vector<pgr_components_rt>
211  G &graph) {
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 }
248 
249 #endif // INCLUDE_COMPONENTS_PGR_COMPONENTS_HPP_
std::vector< pgr_components_rt > strongComponents(G &graph)
Strongly Connected Components Vertex Version.
std::vector< pgr_components_rt > biconnectedComponents(G &graph)
Biconnected Components.
Definition: trsp.h:31
std::vector< pgr_components_rt > bridges(G &graph)
Bridges.
std::vector< pgr_components_rt > articulationPoints(G &graph)
Articulation Points.
std::vector< pgr_components_rt > generate_results(std::vector< std::vector< int64_t > >)
Generate Results, Vertex Version.
std::vector< pgr_components_rt > connectedComponents(G &graph)
Connected Components Vertex Version.