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