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