boost/graph/make_biconnected_planar.hpp

0001 //=======================================================================
0002 // Copyright 2007 Aaron Windsor
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See
0005 // accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //=======================================================================
0008 #ifndef __MAKE_BICONNECTED_PLANAR_HPP__
0009 #define __MAKE_BICONNECTED_PLANAR_HPP__
0010
0011 #include <boost/config.hpp>
0012 #include <boost/tuple/tuple.hpp> //for tie
0013 #include <boost/graph/biconnected_components.hpp>
0014 #include <boost/property_map/property_map.hpp>
0015 #include <vector>
0016 #include <iterator>
0017 #include <algorithm>
0018
0019 #include <boost/graph/planar_detail/add_edge_visitors.hpp>
0020
0021 namespace boost
0022 {
0023
0024 template < typename Graph, typename PlanarEmbedding, typename EdgeIndexMap,
0025     typename AddEdgeVisitor >
0026 void make_biconnected_planar(
0027     Graph& g, PlanarEmbedding embedding, EdgeIndexMap em, AddEdgeVisitor& vis)
0028 {
0029     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0030     typedef typename graph_traits< Graph >::edge_descriptor edge_t;
0031     typedef typename graph_traits< Graph >::edges_size_type edge_size_t;
0032     typedef typename property_traits< PlanarEmbedding >::value_type
0033         embedding_value_t;
0034     typedef typename embedding_value_t::const_iterator embedding_iterator_t;
0035     typedef iterator_property_map< std::vector< std::size_t >::iterator,
0036         EdgeIndexMap >
0037         component_map_t;
0038
0039     edge_size_t n_edges(num_edges(g));
0040     std::vector< vertex_t > articulation_points;
0041     std::vector< edge_size_t > component_vector(n_edges);
0042     component_map_t component_map(component_vector.begin(), em);
0043
0044     biconnected_components(
0045         g, component_map, std::back_inserter(articulation_points));
0046
0047     typename std::vector< vertex_t >::iterator ap, ap_end;
0048     ap_end = articulation_points.end();
0049     for (ap = articulation_points.begin(); ap != ap_end; ++ap)
0050     {
0051         vertex_t v(*ap);
0052         embedding_iterator_t pi = embedding[v].begin();
0053         embedding_iterator_t pi_end = embedding[v].end();
0054         edge_size_t previous_component(n_edges + 1);
0055         vertex_t previous_vertex = graph_traits< Graph >::null_vertex();
0056
0057         for (; pi != pi_end; ++pi)
0058         {
0059             edge_t e(*pi);
0060             vertex_t e_source(source(e, g));
0061             vertex_t e_target(target(e, g));
0062
0063             // Skip self-loops and parallel edges
0064             if (e_source == e_target || previous_vertex == e_target)
0065                 continue;
0066
0067             vertex_t current_vertex = e_source == v ? e_target : e_source;
0068             edge_size_t current_component = component_map[e];
0069             if (previous_vertex != graph_traits< Graph >::null_vertex()
0070                 && current_component != previous_component)
0071             {
0072                 vis.visit_vertex_pair(current_vertex, previous_vertex, g);
0073             }
0074             previous_vertex = current_vertex;
0075             previous_component = current_component;
0076         }
0077     }
0078 }
0079
0080 template < typename Graph, typename PlanarEmbedding, typename EdgeIndexMap >
0081 inline void make_biconnected_planar(
0082     Graph& g, PlanarEmbedding embedding, EdgeIndexMap em)
0083 {
0084     default_add_edge_visitor vis;
0085     make_biconnected_planar(g, embedding, em, vis);
0086 }
0087
0088 template < typename Graph, typename PlanarEmbedding >
0089 inline void make_biconnected_planar(Graph& g, PlanarEmbedding embedding)
0090 {
0091     make_biconnected_planar(g, embedding, get(edge_index, g));
0092 }
0093
0094 } // namespace boost
0095
0096 #endif //__MAKE_BICONNECTED_PLANAR_HPP__