]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | > | |
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> | |
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> | |
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__ |