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 namespace boost
22 {
23
24 template < typename Graph, typename PlanarEmbedding, typename EdgeIndexMap,
25 typename AddEdgeVisitor >
make_biconnected_planar(Graph & g,PlanarEmbedding embedding,EdgeIndexMap em,AddEdgeVisitor & vis)26 void make_biconnected_planar(
27 Graph& g, PlanarEmbedding embedding, EdgeIndexMap em, AddEdgeVisitor& vis)
28 {
29 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
30 typedef typename graph_traits< Graph >::edge_descriptor edge_t;
31 typedef typename graph_traits< Graph >::edges_size_type edge_size_t;
32 typedef typename property_traits< PlanarEmbedding >::value_type
33 embedding_value_t;
34 typedef typename embedding_value_t::const_iterator embedding_iterator_t;
35 typedef iterator_property_map< std::vector< std::size_t >::iterator,
36 EdgeIndexMap >
37 component_map_t;
38
39 edge_size_t n_edges(num_edges(g));
40 std::vector< vertex_t > articulation_points;
41 std::vector< edge_size_t > component_vector(n_edges);
42 component_map_t component_map(component_vector.begin(), em);
43
44 biconnected_components(
45 g, component_map, std::back_inserter(articulation_points));
46
47 typename std::vector< vertex_t >::iterator ap, ap_end;
48 ap_end = articulation_points.end();
49 for (ap = articulation_points.begin(); ap != ap_end; ++ap)
50 {
51 vertex_t v(*ap);
52 embedding_iterator_t pi = embedding[v].begin();
53 embedding_iterator_t pi_end = embedding[v].end();
54 edge_size_t previous_component(n_edges + 1);
55 vertex_t previous_vertex = graph_traits< Graph >::null_vertex();
56
57 for (; pi != pi_end; ++pi)
58 {
59 edge_t e(*pi);
60 vertex_t e_source(source(e, g));
61 vertex_t e_target(target(e, g));
62
63 // Skip self-loops and parallel edges
64 if (e_source == e_target || previous_vertex == e_target)
65 continue;
66
67 vertex_t current_vertex = e_source == v ? e_target : e_source;
68 edge_size_t current_component = component_map[e];
69 if (previous_vertex != graph_traits< Graph >::null_vertex()
70 && current_component != previous_component)
71 {
72 vis.visit_vertex_pair(current_vertex, previous_vertex, g);
73 }
74 previous_vertex = current_vertex;
75 previous_component = current_component;
76 }
77 }
78 }
79
80 template < typename Graph, typename PlanarEmbedding, typename EdgeIndexMap >
make_biconnected_planar(Graph & g,PlanarEmbedding embedding,EdgeIndexMap em)81 inline void make_biconnected_planar(
82 Graph& g, PlanarEmbedding embedding, EdgeIndexMap em)
83 {
84 default_add_edge_visitor vis;
85 make_biconnected_planar(g, embedding, em, vis);
86 }
87
88 template < typename Graph, typename PlanarEmbedding >
make_biconnected_planar(Graph & g,PlanarEmbedding embedding)89 inline void make_biconnected_planar(Graph& g, PlanarEmbedding embedding)
90 {
91 make_biconnected_planar(g, embedding, get(edge_index, g));
92 }
93
94 } // namespace boost
95
96 #endif //__MAKE_BICONNECTED_PLANAR_HPP__
97