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