123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121 |
- //=======================================================================
- // 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__
|