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             >
make_biconnected_planar(Graph & g,PlanarEmbedding embedding,EdgeIndexMap em,AddEdgeVisitor & vis)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             >
make_biconnected_planar(Graph & g,PlanarEmbedding embedding,EdgeIndexMap em)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             >
make_biconnected_planar(Graph & g,PlanarEmbedding embedding)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