| //======================================================================= |
| // Copyright 2007 Aaron Windsor |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| #ifndef __MAKE_BICONNECTED_PLANAR_HPP__ |
| #define __MAKE_BICONNECTED_PLANAR_HPP__ |
| |
| #include <boost/config.hpp> |
| #include <boost/tuple/tuple.hpp> //for tie |
| #include <boost/graph/biconnected_components.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <vector> |
| #include <iterator> |
| #include <algorithm> |
| |
| #include <boost/graph/planar_detail/add_edge_visitors.hpp> |
| |
| |
| namespace boost |
| { |
| |
| |
| |
| template <typename Graph, |
| typename PlanarEmbedding, |
| typename EdgeIndexMap, |
| typename AddEdgeVisitor |
| > |
| void make_biconnected_planar(Graph& g, |
| PlanarEmbedding embedding, |
| EdgeIndexMap em, |
| AddEdgeVisitor& vis |
| ) |
| { |
| typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
| typedef typename graph_traits<Graph>::edge_descriptor edge_t; |
| typedef typename graph_traits<Graph>::edges_size_type edge_size_t; |
| typedef typename |
| property_traits<PlanarEmbedding>::value_type embedding_value_t; |
| typedef typename embedding_value_t::const_iterator embedding_iterator_t; |
| typedef iterator_property_map |
| <std::vector<std::size_t>::iterator, EdgeIndexMap> component_map_t; |
| |
| edge_size_t n_edges(num_edges(g)); |
| std::vector<vertex_t> articulation_points; |
| std::vector<edge_size_t> component_vector(n_edges); |
| component_map_t component_map(component_vector.begin(), em); |
| |
| biconnected_components(g, component_map, |
| std::back_inserter(articulation_points)); |
| |
| typename std::vector<vertex_t>::iterator ap, ap_end; |
| ap_end = articulation_points.end(); |
| for(ap = articulation_points.begin(); ap != ap_end; ++ap) |
| { |
| vertex_t v(*ap); |
| embedding_iterator_t pi = embedding[v].begin(); |
| embedding_iterator_t pi_end = embedding[v].end(); |
| edge_size_t previous_component(n_edges + 1); |
| vertex_t previous_vertex = graph_traits<Graph>::null_vertex(); |
| |
| for(; pi != pi_end; ++pi) |
| { |
| edge_t e(*pi); |
| vertex_t e_source(source(e,g)); |
| vertex_t e_target(target(e,g)); |
| |
| //Skip self-loops and parallel edges |
| if (e_source == e_target || previous_vertex == e_target) |
| continue; |
| |
| vertex_t current_vertex = e_source == v ? e_target : e_source; |
| edge_size_t current_component = component_map[e]; |
| if (previous_vertex != graph_traits<Graph>::null_vertex() && |
| current_component != previous_component) |
| { |
| vis.visit_vertex_pair(current_vertex, previous_vertex, g); |
| } |
| previous_vertex = current_vertex; |
| previous_component = current_component; |
| } |
| } |
| |
| } |
| |
| |
| |
| |
| template <typename Graph, |
| typename PlanarEmbedding, |
| typename EdgeIndexMap |
| > |
| inline void make_biconnected_planar(Graph& g, |
| PlanarEmbedding embedding, |
| EdgeIndexMap em |
| ) |
| { |
| default_add_edge_visitor vis; |
| make_biconnected_planar(g, embedding, em, vis); |
| } |
| |
| |
| |
| |
| template <typename Graph, |
| typename PlanarEmbedding |
| > |
| inline void make_biconnected_planar(Graph& g, PlanarEmbedding embedding) |
| { |
| make_biconnected_planar(g, embedding, get(edge_index,g)); |
| } |
| |
| |
| } // namespace boost |
| |
| |
| |
| #endif //__MAKE_BICONNECTED_PLANAR_HPP__ |