1 | //======================================================================= |
2 | // Copyright 2007 Aaron Windsor |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See |
5 | // accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | //======================================================================= |
8 | #ifndef __MAKE_CONNECTED_HPP__ |
9 | #define __MAKE_CONNECTED_HPP__ |
10 | |
11 | #include <boost/config.hpp> |
12 | #include <boost/next_prior.hpp> |
13 | #include <boost/tuple/tuple.hpp> //for tie |
14 | #include <boost/graph/connected_components.hpp> |
15 | #include <boost/property_map/property_map.hpp> |
16 | #include <vector> |
17 | |
18 | #include <boost/graph/planar_detail/add_edge_visitors.hpp> |
19 | #include <boost/graph/planar_detail/bucket_sort.hpp> |
20 | |
21 | |
22 | namespace boost |
23 | { |
24 | |
25 | |
26 | template <typename Graph, |
27 | typename VertexIndexMap, |
28 | typename AddEdgeVisitor |
29 | > |
30 | void make_connected(Graph& g, VertexIndexMap vm, AddEdgeVisitor& vis) |
31 | { |
32 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; |
33 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
34 | typedef typename graph_traits<Graph>::vertices_size_type v_size_t; |
35 | typedef iterator_property_map< typename std::vector<v_size_t>::iterator, |
36 | VertexIndexMap |
37 | > vertex_to_v_size_map_t; |
38 | |
39 | std::vector<v_size_t> component_vector(num_vertices(g)); |
40 | vertex_to_v_size_map_t component(component_vector.begin(), vm); |
41 | std::vector<vertex_t> vertices_by_component(num_vertices(g)); |
42 | |
43 | v_size_t num_components = connected_components(g, component); |
44 | |
45 | if (num_components < 2) |
46 | return; |
47 | |
48 | vertex_iterator_t vi, vi_end; |
49 | boost::tie(vi,vi_end) = vertices(g); |
50 | std::copy(vi, vi_end, vertices_by_component.begin()); |
51 | |
52 | bucket_sort(vertices_by_component.begin(), |
53 | vertices_by_component.end(), |
54 | component, |
55 | num_components |
56 | ); |
57 | |
58 | typedef typename std::vector<vertex_t>::iterator vec_of_vertices_itr_t; |
59 | |
60 | vec_of_vertices_itr_t ci_end = vertices_by_component.end(); |
61 | vec_of_vertices_itr_t ci_prev = vertices_by_component.begin(); |
62 | if (ci_prev == ci_end) |
63 | return; |
64 | |
65 | for(vec_of_vertices_itr_t ci = boost::next(ci_prev); |
66 | ci != ci_end; ci_prev = ci, ++ci |
67 | ) |
68 | { |
69 | if (component[*ci_prev] != component[*ci]) |
70 | vis.visit_vertex_pair(*ci_prev, *ci, g); |
71 | } |
72 | |
73 | } |
74 | |
75 | |
76 | |
77 | |
78 | template <typename Graph, typename VertexIndexMap> |
79 | inline void make_connected(Graph& g, VertexIndexMap vm) |
80 | { |
81 | default_add_edge_visitor vis; |
82 | make_connected(g, vm, vis); |
83 | } |
84 | |
85 | |
86 | |
87 | |
88 | template <typename Graph> |
89 | inline void make_connected(Graph& g) |
90 | { |
91 | make_connected(g, get(vertex_index,g)); |
92 | } |
93 | |
94 | |
95 | |
96 | |
97 | } // namespace boost |
98 | |
99 | #endif //__MAKE_CONNECTED_HPP__ |
100 | |