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_BICONNECTED_PLANAR_HPP__ |
9 | #define __MAKE_BICONNECTED_PLANAR_HPP__ |
10 | |
11 | #include <boost/config.hpp> |
12 | #include <boost/tuple/tuple.hpp> //for tie |
13 | #include <boost/graph/biconnected_components.hpp> |
14 | #include <boost/property_map/property_map.hpp> |
15 | #include <vector> |
16 | #include <iterator> |
17 | #include <algorithm> |
18 | |
19 | #include <boost/graph/planar_detail/add_edge_visitors.hpp> |
20 | |
21 | |
22 | namespace boost |
23 | { |
24 | |
25 | |
26 | |
27 | template <typename Graph, |
28 | typename PlanarEmbedding, |
29 | typename EdgeIndexMap, |
30 | typename AddEdgeVisitor |
31 | > |
32 | void make_biconnected_planar(Graph& g, |
33 | PlanarEmbedding embedding, |
34 | EdgeIndexMap em, |
35 | AddEdgeVisitor& vis |
36 | ) |
37 | { |
38 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
39 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; |
40 | typedef typename graph_traits<Graph>::edges_size_type edge_size_t; |
41 | typedef typename |
42 | property_traits<PlanarEmbedding>::value_type embedding_value_t; |
43 | typedef typename embedding_value_t::const_iterator embedding_iterator_t; |
44 | typedef iterator_property_map |
45 | <std::vector<std::size_t>::iterator, EdgeIndexMap> component_map_t; |
46 | |
47 | edge_size_t n_edges(num_edges(g)); |
48 | std::vector<vertex_t> articulation_points; |
49 | std::vector<edge_size_t> component_vector(n_edges); |
50 | component_map_t component_map(component_vector.begin(), em); |
51 | |
52 | biconnected_components(g, component_map, |
53 | std::back_inserter(articulation_points)); |
54 | |
55 | typename std::vector<vertex_t>::iterator ap, ap_end; |
56 | ap_end = articulation_points.end(); |
57 | for(ap = articulation_points.begin(); ap != ap_end; ++ap) |
58 | { |
59 | vertex_t v(*ap); |
60 | embedding_iterator_t pi = embedding[v].begin(); |
61 | embedding_iterator_t pi_end = embedding[v].end(); |
62 | edge_size_t previous_component(n_edges + 1); |
63 | vertex_t previous_vertex = graph_traits<Graph>::null_vertex(); |
64 | |
65 | for(; pi != pi_end; ++pi) |
66 | { |
67 | edge_t e(*pi); |
68 | vertex_t e_source(source(e,g)); |
69 | vertex_t e_target(target(e,g)); |
70 | |
71 | //Skip self-loops and parallel edges |
72 | if (e_source == e_target || previous_vertex == e_target) |
73 | continue; |
74 | |
75 | vertex_t current_vertex = e_source == v ? e_target : e_source; |
76 | edge_size_t current_component = component_map[e]; |
77 | if (previous_vertex != graph_traits<Graph>::null_vertex() && |
78 | current_component != previous_component) |
79 | { |
80 | vis.visit_vertex_pair(current_vertex, previous_vertex, g); |
81 | } |
82 | previous_vertex = current_vertex; |
83 | previous_component = current_component; |
84 | } |
85 | } |
86 | |
87 | } |
88 | |
89 | |
90 | |
91 | |
92 | template <typename Graph, |
93 | typename PlanarEmbedding, |
94 | typename EdgeIndexMap |
95 | > |
96 | inline void make_biconnected_planar(Graph& g, |
97 | PlanarEmbedding embedding, |
98 | EdgeIndexMap em |
99 | ) |
100 | { |
101 | default_add_edge_visitor vis; |
102 | make_biconnected_planar(g, embedding, em, vis); |
103 | } |
104 | |
105 | |
106 | |
107 | |
108 | template <typename Graph, |
109 | typename PlanarEmbedding |
110 | > |
111 | inline void make_biconnected_planar(Graph& g, PlanarEmbedding embedding) |
112 | { |
113 | make_biconnected_planar(g, embedding, get(edge_index,g)); |
114 | } |
115 | |
116 | |
117 | } // namespace boost |
118 | |
119 | |
120 | |
121 | #endif //__MAKE_BICONNECTED_PLANAR_HPP__ |
122 | |