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