boost/graph/make_maximal_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_MAXIMAL_PLANAR_HPP__
0009 #define __MAKE_MAXIMAL_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_face_traversal.hpp>
0020 #include <boost/graph/planar_detail/add_edge_visitors.hpp>
0021
0022 namespace boost
0023 {
0024
0025 template < typename Graph, typename VertexIndexMap, typename AddEdgeVisitor >
0026 struct triangulation_visitor : public planar_face_traversal_visitor
0027 {
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 >::vertices_size_type v_size_t;
0032     typedef typename graph_traits< Graph >::degree_size_type degree_size_t;
0033     typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
0034     typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
0035     typedef
0036         typename graph_traits< Graph >::adjacency_iterator adjacency_iterator_t;
0037     typedef typename std::vector< vertex_t > vertex_vector_t;
0038     typedef typename std::vector< v_size_t > v_size_vector_t;
0039     typedef typename std::vector< degree_size_t > degree_size_vector_t;
0040     typedef iterator_property_map< typename v_size_vector_t::iterator,
0041         VertexIndexMap >
0042         vertex_to_v_size_map_t;
0043     typedef iterator_property_map< typename degree_size_vector_t::iterator,
0044         VertexIndexMap >
0045         vertex_to_degree_size_map_t;
0046     typedef typename vertex_vector_t::iterator face_iterator;
0047
0048     triangulation_visitor(Graph& arg_g, VertexIndexMap arg_vm,
0049         AddEdgeVisitor arg_add_edge_visitor)
0050     : g(arg_g)
0051     , vm(arg_vm)
0052     , add_edge_visitor(arg_add_edge_visitor)
0053     , timestamp(0)
0054     , marked_vector(num_vertices(g), timestamp)
0055     , degree_vector(num_vertices(g), 0)
0056     , marked(marked_vector.begin(), vm)
0057     , degree(degree_vector.begin(), vm)
0058     {
0059         vertex_iterator_t vi, vi_end;
0060         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0061             put(degree, *vi, out_degree(*vi, g));
0062     }
0063
0064     template < typename Vertex > void next_vertex(Vertex v)
0065     {
0066         // Self-loops will appear as consecutive vertices in the list of
0067         // vertices on a face. We want to skip these.
0068         if (!vertices_on_face.empty()
0069             && (vertices_on_face.back() == v || vertices_on_face.front() == v))
0070             return;
0071
0072         vertices_on_face.push_back(v);
0073     }
0074
0075     void end_face()
0076     {
0077         ++timestamp;
0078
0079         if (vertices_on_face.size() <= 3)
0080         {
0081             // At most three vertices on this face - don't need to triangulate
0082             vertices_on_face.clear();
0083             return;
0084         }
0085
0086         // Find vertex on face of minimum degree
0087         degree_size_t min_degree = num_vertices(g);
0088         typename vertex_vector_t::iterator min_degree_vertex_itr;
0089         face_iterator fi_end = vertices_on_face.end();
0090         for (face_iterator fi = vertices_on_face.begin(); fi != fi_end; ++fi)
0091         {
0092             degree_size_t deg = get(degree, *fi);
0093             if (deg < min_degree)
0094             {
0095                 min_degree_vertex_itr = fi;
0096                 min_degree = deg;
0097             }
0098         }
0099
0100         // To simplify some of the manipulations, we'll re-arrange
0101         // vertices_on_face so that it still contains the same
0102         // (counter-clockwise) order of the vertices on this face, but now the
0103         // min_degree_vertex is the first element in vertices_on_face.
0104         vertex_vector_t temp_vector;
0105         std::copy(min_degree_vertex_itr, vertices_on_face.end(),
0106             std::back_inserter(temp_vector));
0107         std::copy(vertices_on_face.begin(), min_degree_vertex_itr,
0108             std::back_inserter(temp_vector));
0109         vertices_on_face.swap(temp_vector);
0110
0111         // Mark all of the min degree vertex's neighbors
0112         adjacency_iterator_t ai, ai_end;
0113         for (boost::tie(ai, ai_end)
0114              = adjacent_vertices(vertices_on_face.front(), g);
0115              ai != ai_end; ++ai)
0116         {
0117             put(marked, *ai, timestamp);
0118         }
0119
0120         typename vertex_vector_t::iterator marked_neighbor
0121             = vertices_on_face.end();
0122
0123         // The iterator manipulations on the next two lines are safe because
0124         // vertices_on_face.size() > 3 (from the first test in this function)
0125         fi_end = prior(vertices_on_face.end());
0126         for (face_iterator fi
0127              = boost::next(boost::next(vertices_on_face.begin()));
0128              fi != fi_end; ++fi)
0129         {
0130             if (get(marked, *fi) == timestamp)
0131             {
0132                 marked_neighbor = fi;
0133                 break;
0134             }
0135         }
0136
0137         if (marked_neighbor == vertices_on_face.end())
0138         {
0139             add_edge_range(vertices_on_face[0],
0140                 boost::next(boost::next(vertices_on_face.begin())),
0141                 prior(vertices_on_face.end()));
0142         }
0143         else
0144         {
0145             add_edge_range(vertices_on_face[1], boost::next(marked_neighbor),
0146                 vertices_on_face.end());
0147
0148             add_edge_range(*boost::next(marked_neighbor),
0149                 boost::next(boost::next(vertices_on_face.begin())),
0150                 marked_neighbor);
0151         }
0152
0153         // reset for the next face
0154         vertices_on_face.clear();
0155     }
0156
0157 private:
0158     void add_edge_range(vertex_t anchor, face_iterator fi, face_iterator fi_end)
0159     {
0160         for (; fi != fi_end; ++fi)
0161         {
0162             vertex_t v(*fi);
0163             add_edge_visitor.visit_vertex_pair(anchor, v, g);
0164             put(degree, anchor, get(degree, anchor) + 1);
0165             put(degree, v, get(degree, v) + 1);
0166         }
0167     }
0168
0169     Graph& g;
0170     VertexIndexMap vm;
0171     AddEdgeVisitor add_edge_visitor;
0172     v_size_t timestamp;
0173     vertex_vector_t vertices_on_face;
0174     v_size_vector_t marked_vector;
0175     degree_size_vector_t degree_vector;
0176     vertex_to_v_size_map_t marked;
0177     vertex_to_degree_size_map_t degree;
0178 };
0179
0180 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap,
0181     typename EdgeIndexMap, typename AddEdgeVisitor >
0182 void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm,
0183     EdgeIndexMap em, AddEdgeVisitor& vis)
0184 {
0185     triangulation_visitor< Graph, VertexIndexMap, AddEdgeVisitor > visitor(
0186         g, vm, vis);
0187     planar_face_traversal(g, embedding, visitor, em);
0188 }
0189
0190 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap,
0191     typename EdgeIndexMap >
0192 void make_maximal_planar(
0193     Graph& g, PlanarEmbedding embedding, VertexIndexMap vm, EdgeIndexMap em)
0194 {
0195     default_add_edge_visitor vis;
0196     make_maximal_planar(g, embedding, vm, em, vis);
0197 }
0198
0199 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap >
0200 void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm)
0201 {
0202     make_maximal_planar(g, embedding, vm, get(edge_index, g));
0203 }
0204
0205 template < typename Graph, typename PlanarEmbedding >
0206 void make_maximal_planar(Graph& g, PlanarEmbedding embedding)
0207 {
0208     make_maximal_planar(g, embedding, get(vertex_index, g));
0209 }
0210
0211 } // namespace boost
0212
0213 #endif //__MAKE_MAXIMAL_PLANAR_HPP__