| //======================================================================= |
| // 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 <boost/config.hpp> |
| #include <boost/utility.hpp> //for next |
| #include <boost/tuple/tuple.hpp> //for tie |
| #include <boost/graph/connected_components.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <vector> |
| |
| #include <boost/graph/planar_detail/add_edge_visitors.hpp> |
| #include <boost/graph/planar_detail/bucket_sort.hpp> |
| |
| |
| 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__ |