//======================================================================= // Copyright 2007 Aaron Windsor // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #ifndef __MAKE_CONNECTED_HPP__ #define __MAKE_CONNECTED_HPP__ #include #include #include //for tie #include #include #include #include #include namespace boost { template < typename Graph, typename VertexIndexMap, typename AddEdgeVisitor > void make_connected(Graph& g, VertexIndexMap vm, AddEdgeVisitor& vis) { typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; typedef typename graph_traits< Graph >::vertices_size_type v_size_t; typedef iterator_property_map< typename std::vector< v_size_t >::iterator, VertexIndexMap > vertex_to_v_size_map_t; std::vector< v_size_t > component_vector(num_vertices(g)); vertex_to_v_size_map_t component(component_vector.begin(), vm); std::vector< vertex_t > vertices_by_component(num_vertices(g)); v_size_t num_components = connected_components(g, component); if (num_components < 2) return; vertex_iterator_t vi, vi_end; boost::tie(vi, vi_end) = vertices(g); std::copy(vi, vi_end, vertices_by_component.begin()); bucket_sort(vertices_by_component.begin(), vertices_by_component.end(), component, num_components); typedef typename std::vector< vertex_t >::iterator vec_of_vertices_itr_t; vec_of_vertices_itr_t ci_end = vertices_by_component.end(); vec_of_vertices_itr_t ci_prev = vertices_by_component.begin(); if (ci_prev == ci_end) return; for (vec_of_vertices_itr_t ci = boost::next(ci_prev); ci != ci_end; ci_prev = ci, ++ci) { if (component[*ci_prev] != component[*ci]) vis.visit_vertex_pair(*ci_prev, *ci, g); } } template < typename Graph, typename VertexIndexMap > inline void make_connected(Graph& g, VertexIndexMap vm) { default_add_edge_visitor vis; make_connected(g, vm, vis); } template < typename Graph > inline void make_connected(Graph& g) { make_connected(g, get(vertex_index, g)); } } // namespace boost #endif //__MAKE_CONNECTED_HPP__