ceph/src/boost/boost/graph/make_maximal_planar.hpp

   1 //=======================================================================
   2 // Copyright 2007 Aaron Windsor
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See
   5 // accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //=======================================================================
   8 #ifndef __MAKE_MAXIMAL_PLANAR_HPP__
   9 #define __MAKE_MAXIMAL_PLANAR_HPP__
  10
  11 #include <boost/config.hpp>
  12 #include <boost/tuple/tuple.hpp> //for tie
  13 #include <boost/graph/biconnected_components.hpp>
  14 #include <boost/property_map/property_map.hpp>
  15 #include <vector>
  16 #include <iterator>
  17 #include <algorithm>
  18
  19 #include <boost/graph/planar_face_traversal.hpp>
  20 #include <boost/graph/planar_detail/add_edge_visitors.hpp>
  21
  22 namespace boost
  23 {
  24
  25 template < typename Graph, typename VertexIndexMap, typename AddEdgeVisitor >
  26 struct triangulation_visitor : public planar_face_traversal_visitor
  27 {
  28
  29     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
  30     typedef typename graph_traits< Graph >::edge_descriptor edge_t;
  31     typedef typename graph_traits< Graph >::vertices_size_type v_size_t;
  32     typedef typename graph_traits< Graph >::degree_size_type degree_size_t;
  33     typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
  34     typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
  35     typedef
  36         typename graph_traits< Graph >::adjacency_iterator adjacency_iterator_t;
  37     typedef typename std::vector< vertex_t > vertex_vector_t;
  38     typedef typename std::vector< v_size_t > v_size_vector_t;
  39     typedef typename std::vector< degree_size_t > degree_size_vector_t;
  40     typedef iterator_property_map< typename v_size_vector_t::iterator,
  41         VertexIndexMap >
  42         vertex_to_v_size_map_t;
  43     typedef iterator_property_map< typename degree_size_vector_t::iterator,
  44         VertexIndexMap >
  45         vertex_to_degree_size_map_t;
  46     typedef typename vertex_vector_t::iterator face_iterator;
  47
  48     triangulation_visitor(Graph& arg_g, VertexIndexMap arg_vm,
  49         AddEdgeVisitor arg_add_edge_visitor)
  50     : g(arg_g)
  51     , vm(arg_vm)
  52     , add_edge_visitor(arg_add_edge_visitor)
  53     , timestamp(0)
  54     , marked_vector(num_vertices(g), timestamp)
  55     , degree_vector(num_vertices(g), 0)
  56     , marked(marked_vector.begin(), vm)
  57     , degree(degree_vector.begin(), vm)
  58     {
  59         vertex_iterator_t vi, vi_end;
  60         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
  61             put(degree, *vi, out_degree(*vi, g));
  62     }
  63
  64     template < typename Vertex > void next_vertex(Vertex v)
  65     {
  66         // Self-loops will appear as consecutive vertices in the list of
  67         // vertices on a face. We want to skip these.
  68         if (!vertices_on_face.empty()
  69             && (vertices_on_face.back() == v || vertices_on_face.front() == v))
  70             return;
  71
  72         vertices_on_face.push_back(v);
  73     }
  74
  75     void end_face()
  76     {
  77         ++timestamp;
  78
  79         if (vertices_on_face.size() <= 3)
  80         {
  81             // At most three vertices on this face - don't need to triangulate
  82             vertices_on_face.clear();
  83             return;
  84         }
  85
  86         // Find vertex on face of minimum degree
  87         degree_size_t min_degree = num_vertices(g);
  88         typename vertex_vector_t::iterator min_degree_vertex_itr;
  89         face_iterator fi_end = vertices_on_face.end();
  90         for (face_iterator fi = vertices_on_face.begin(); fi != fi_end; ++fi)
  91         {
  92             degree_size_t deg = get(degree, *fi);
  93             if (deg < min_degree)
  94             {
  95                 min_degree_vertex_itr = fi;
  96                 min_degree = deg;
  97             }
  98         }
  99
 100         // To simplify some of the manipulations, we'll re-arrange
 101         // vertices_on_face so that it still contains the same
 102         // (counter-clockwise) order of the vertices on this face, but now the
 103         // min_degree_vertex is the first element in vertices_on_face.
 104         vertex_vector_t temp_vector;
 105         std::copy(min_degree_vertex_itr, vertices_on_face.end(),
 106             std::back_inserter(temp_vector));
 107         std::copy(vertices_on_face.begin(), min_degree_vertex_itr,
 108             std::back_inserter(temp_vector));
 109         vertices_on_face.swap(temp_vector);
 110
 111         // Mark all of the min degree vertex's neighbors
 112         adjacency_iterator_t ai, ai_end;
 113         for (boost::tie(ai, ai_end)
 114              = adjacent_vertices(vertices_on_face.front(), g);
 115              ai != ai_end; ++ai)
 116         {
 117             put(marked, *ai, timestamp);
 118         }
 119
 120         typename vertex_vector_t::iterator marked_neighbor
 121             = vertices_on_face.end();
 122
 123         // The iterator manipulations on the next two lines are safe because
 124         // vertices_on_face.size() > 3 (from the first test in this function)
 125         fi_end = prior(vertices_on_face.end());
 126         for (face_iterator fi
 127              = boost::next(boost::next(vertices_on_face.begin()));
 128              fi != fi_end; ++fi)
 129         {
 130             if (get(marked, *fi) == timestamp)
 131             {
 132                 marked_neighbor = fi;
 133                 break;
 134             }
 135         }
 136
 137         if (marked_neighbor == vertices_on_face.end())
 138         {
 139             add_edge_range(vertices_on_face[0],
 140                 boost::next(boost::next(vertices_on_face.begin())),
 141                 prior(vertices_on_face.end()));
 142         }
 143         else
 144         {
 145             add_edge_range(vertices_on_face[1], boost::next(marked_neighbor),
 146                 vertices_on_face.end());
 147
 148             add_edge_range(*boost::next(marked_neighbor),
 149                 boost::next(boost::next(vertices_on_face.begin())),
 150                 marked_neighbor);
 151         }
 152
 153         // reset for the next face
 154         vertices_on_face.clear();
 155     }
 156
 157 private:
 158     void add_edge_range(vertex_t anchor, face_iterator fi, face_iterator fi_end)
 159     {
 160         for (; fi != fi_end; ++fi)
 161         {
 162             vertex_t v(*fi);
 163             add_edge_visitor.visit_vertex_pair(anchor, v, g);
 164             put(degree, anchor, get(degree, anchor) + 1);
 165             put(degree, v, get(degree, v) + 1);
 166         }
 167     }
 168
 169     Graph& g;
 170     VertexIndexMap vm;
 171     AddEdgeVisitor add_edge_visitor;
 172     v_size_t timestamp;
 173     vertex_vector_t vertices_on_face;
 174     v_size_vector_t marked_vector;
 175     degree_size_vector_t degree_vector;
 176     vertex_to_v_size_map_t marked;
 177     vertex_to_degree_size_map_t degree;
 178 };
 179
 180 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap,
 181     typename EdgeIndexMap, typename AddEdgeVisitor >
 182 void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm,
 183     EdgeIndexMap em, AddEdgeVisitor& vis)
 184 {
 185     triangulation_visitor< Graph, VertexIndexMap, AddEdgeVisitor > visitor(
 186         g, vm, vis);
 187     planar_face_traversal(g, embedding, visitor, em);
 188 }
 189
 190 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap,
 191     typename EdgeIndexMap >
 192 void make_maximal_planar(
 193     Graph& g, PlanarEmbedding embedding, VertexIndexMap vm, EdgeIndexMap em)
 194 {
 195     default_add_edge_visitor vis;
 196     make_maximal_planar(g, embedding, vm, em, vis);
 197 }
 198
 199 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap >
 200 void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm)
 201 {
 202     make_maximal_planar(g, embedding, vm, get(edge_index, g));
 203 }
 204
 205 template < typename Graph, typename PlanarEmbedding >
 206 void make_maximal_planar(Graph& g, PlanarEmbedding embedding)
 207 {
 208     make_maximal_planar(g, embedding, get(vertex_index, g));
 209 }
 210
 211 } // namespace boost
 212
 213 #endif //__MAKE_MAXIMAL_PLANAR_HPP__