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             >
make_connected(Graph & g,VertexIndexMap vm,AddEdgeVisitor & vis)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>
make_connected(Graph & g,VertexIndexMap vm)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>
make_connected(Graph & g)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