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_MAXIMAL_PLANAR_HPP__
Chris@16: #define __MAKE_MAXIMAL_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_face_traversal.hpp>
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:   template <typename Graph, typename VertexIndexMap, typename AddEdgeVisitor>
Chris@16:   struct triangulation_visitor : public planar_face_traversal_visitor
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>::vertices_size_type v_size_t;
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type degree_size_t;
Chris@16:     typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
Chris@16:     typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
Chris@16:     typedef typename graph_traits<Graph>::adjacency_iterator 
Chris@16:       adjacency_iterator_t;
Chris@16:     typedef typename std::vector<vertex_t> vertex_vector_t;
Chris@16:     typedef typename std::vector<v_size_t> v_size_vector_t;
Chris@16:     typedef typename std::vector<degree_size_t> degree_size_vector_t;
Chris@16:     typedef iterator_property_map
Chris@16:       < typename v_size_vector_t::iterator, VertexIndexMap > 
Chris@16:       vertex_to_v_size_map_t;
Chris@16:     typedef iterator_property_map
Chris@16:       < typename degree_size_vector_t::iterator, VertexIndexMap > 
Chris@16:       vertex_to_degree_size_map_t;
Chris@16:     typedef typename vertex_vector_t::iterator face_iterator;
Chris@16: 
Chris@16: 
Chris@16:     triangulation_visitor(Graph& arg_g, 
Chris@16:                           VertexIndexMap arg_vm, 
Chris@16:                           AddEdgeVisitor arg_add_edge_visitor
Chris@16:                           ) : 
Chris@16:       g(arg_g),
Chris@16:       vm(arg_vm),
Chris@16:       add_edge_visitor(arg_add_edge_visitor),
Chris@16:       timestamp(0),
Chris@16:       marked_vector(num_vertices(g), timestamp),
Chris@16:       degree_vector(num_vertices(g), 0),
Chris@16:       marked(marked_vector.begin(), vm),
Chris@16:       degree(degree_vector.begin(), vm)
Chris@16:     {
Chris@16:       vertex_iterator_t vi, vi_end;
Chris@16:       for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
Chris@16:         put(degree, *vi, out_degree(*vi, g));
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Vertex>
Chris@16:     void next_vertex(Vertex v)
Chris@16:     {
Chris@16:       // Self-loops will appear as consecutive vertices in the list of
Chris@16:       // vertices on a face. We want to skip these.
Chris@16:       if (!vertices_on_face.empty() && 
Chris@16:           (vertices_on_face.back() == v || vertices_on_face.front() == v)
Chris@16:           )
Chris@16:         return;
Chris@16: 
Chris@16:       vertices_on_face.push_back(v);
Chris@16:     }
Chris@16: 
Chris@16:     void end_face()
Chris@16:     {
Chris@16:       ++timestamp;
Chris@16: 
Chris@16:       if (vertices_on_face.size() <= 3)
Chris@16:         {
Chris@16:           // At most three vertices on this face - don't need to triangulate
Chris@16:           vertices_on_face.clear();
Chris@16:           return;
Chris@16:         }
Chris@16:       
Chris@16:       // Find vertex on face of minimum degree
Chris@16:       degree_size_t min_degree = num_vertices(g);
Chris@16:       typename vertex_vector_t::iterator min_degree_vertex_itr;
Chris@16:       face_iterator fi_end = vertices_on_face.end();
Chris@16:       for(face_iterator fi = vertices_on_face.begin(); fi != fi_end; ++fi)
Chris@16:         {
Chris@16:           degree_size_t deg = get(degree,*fi);
Chris@16:           if (deg < min_degree)
Chris@16:             {
Chris@16:               min_degree_vertex_itr = fi;
Chris@16:               min_degree = deg;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:       // To simplify some of the manipulations, we'll re-arrange 
Chris@16:       // vertices_on_face so that it still contains the same 
Chris@16:       // (counter-clockwise) order of the vertices on this face, but now the 
Chris@16:       // min_degree_vertex is the first element in vertices_on_face.
Chris@16:       vertex_vector_t temp_vector;
Chris@16:       std::copy(min_degree_vertex_itr, vertices_on_face.end(), 
Chris@16:                 std::back_inserter(temp_vector));
Chris@16:       std::copy(vertices_on_face.begin(), min_degree_vertex_itr, 
Chris@16:                 std::back_inserter(temp_vector));
Chris@16:       vertices_on_face.swap(temp_vector);
Chris@16: 
Chris@16:       // Mark all of the min degree vertex's neighbors
Chris@16:       adjacency_iterator_t ai, ai_end;
Chris@16:       for(boost::tie(ai,ai_end) = adjacent_vertices(vertices_on_face.front(),g); 
Chris@16:           ai != ai_end; ++ai
Chris@16:           )
Chris@16:         {
Chris@16:           put(marked, *ai, timestamp);
Chris@16:         }
Chris@16: 
Chris@16:       typename vertex_vector_t::iterator marked_neighbor 
Chris@16:         = vertices_on_face.end();
Chris@16:      
Chris@16:       // The iterator manipulations on the next two lines are safe because 
Chris@16:       // vertices_on_face.size() > 3 (from the first test in this function)
Chris@16:       fi_end = prior(vertices_on_face.end());
Chris@16:       for(face_iterator fi = boost::next(boost::next(vertices_on_face.begin())); 
Chris@16:           fi != fi_end; ++fi
Chris@16:           )
Chris@16:         {
Chris@16:           if (get(marked, *fi) == timestamp)
Chris@16:             {
Chris@16:               marked_neighbor = fi;
Chris@16:               break;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:       if (marked_neighbor == vertices_on_face.end())
Chris@16:         {
Chris@16:           add_edge_range(
Chris@16:                          vertices_on_face[0],
Chris@16:                          boost::next(boost::next(vertices_on_face.begin())),
Chris@16:                          prior(vertices_on_face.end())
Chris@16:                          );
Chris@16:         }
Chris@16:       else
Chris@16:         {
Chris@16:           add_edge_range(
Chris@16:                          vertices_on_face[1],
Chris@16:                          boost::next(marked_neighbor),
Chris@16:                          vertices_on_face.end()
Chris@16:                          );
Chris@16: 
Chris@16:           add_edge_range(
Chris@16:                          *boost::next(marked_neighbor),
Chris@16:                          boost::next(boost::next(vertices_on_face.begin())),
Chris@16:                          marked_neighbor
Chris@16:                          );
Chris@16:         }
Chris@16: 
Chris@16:       //reset for the next face
Chris@16:       vertices_on_face.clear();
Chris@16:       
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     
Chris@16:     void add_edge_range(vertex_t anchor, 
Chris@16:                         face_iterator fi, 
Chris@16:                         face_iterator fi_end
Chris@16:                         )
Chris@16:     {
Chris@16:       for (; fi != fi_end; ++fi)
Chris@16:         {
Chris@16:           vertex_t v(*fi);
Chris@16:           add_edge_visitor.visit_vertex_pair(anchor, v, g);
Chris@16:           put(degree, anchor, get(degree, anchor) + 1);
Chris@16:           put(degree, v, get(degree, v) + 1);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     Graph& g;
Chris@16:     VertexIndexMap vm;
Chris@16:     AddEdgeVisitor add_edge_visitor;
Chris@16:     v_size_t timestamp;
Chris@16:     vertex_vector_t vertices_on_face;
Chris@16:     v_size_vector_t marked_vector;
Chris@16:     degree_size_vector_t degree_vector;
Chris@16:     vertex_to_v_size_map_t marked;
Chris@16:     vertex_to_degree_size_map_t degree;
Chris@16:     
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Graph,
Chris@16:             typename PlanarEmbedding,
Chris@16:             typename VertexIndexMap,
Chris@16:             typename EdgeIndexMap,
Chris@16:             typename AddEdgeVisitor
Chris@16:             >
Chris@16:   void make_maximal_planar(Graph& g, 
Chris@16:                            PlanarEmbedding embedding,
Chris@16:                            VertexIndexMap vm, 
Chris@16:                            EdgeIndexMap em,
Chris@16:                            AddEdgeVisitor& vis)
Chris@16:   {
Chris@16:     triangulation_visitor<Graph,VertexIndexMap,AddEdgeVisitor> 
Chris@16:       visitor(g, vm, vis);
Chris@16:     planar_face_traversal(g, embedding, visitor, em);
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Graph,
Chris@16:             typename PlanarEmbedding,
Chris@16:             typename VertexIndexMap,
Chris@16:             typename EdgeIndexMap
Chris@16:             >
Chris@16:   void make_maximal_planar(Graph& g,
Chris@16:                            PlanarEmbedding embedding,
Chris@16:                            VertexIndexMap vm,
Chris@16:                            EdgeIndexMap em
Chris@16:                            )
Chris@16:   {
Chris@16:     default_add_edge_visitor vis;
Chris@16:     make_maximal_planar(g, embedding, vm, em, vis);
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Graph,
Chris@16:             typename PlanarEmbedding,
Chris@16:             typename VertexIndexMap
Chris@16:             >
Chris@16:   void make_maximal_planar(Graph& g,
Chris@16:                            PlanarEmbedding embedding,
Chris@16:                            VertexIndexMap vm
Chris@16:                            )
Chris@16:   {
Chris@16:     make_maximal_planar(g, embedding, vm, get(edge_index,g));
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Graph,
Chris@16:             typename PlanarEmbedding
Chris@16:             >
Chris@16:   void make_maximal_planar(Graph& g,
Chris@16:                            PlanarEmbedding embedding
Chris@16:                            )
Chris@16:   {
Chris@16:     make_maximal_planar(g, embedding, get(vertex_index,g));
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: #endif //__MAKE_MAXIMAL_PLANAR_HPP__