diff options
Diffstat (limited to 'boost/graph/make_connected.hpp')
-rw-r--r-- | boost/graph/make_connected.hpp | 99 |
1 files changed, 99 insertions, 0 deletions
diff --git a/boost/graph/make_connected.hpp b/boost/graph/make_connected.hpp new file mode 100644 index 0000000000..de6c861ddd --- /dev/null +++ b/boost/graph/make_connected.hpp @@ -0,0 +1,99 @@ +//======================================================================= +// 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__ |