boost/graph/planar_face_traversal.hpp

0001 //=======================================================================
0002 // Copyright (c) Aaron Windsor 2007
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
0009 #ifndef __PLANAR_FACE_TRAVERSAL_HPP__
0010 #define __PLANAR_FACE_TRAVERSAL_HPP__
0011
0012 #include <vector>
0013 #include <set>
0014 #include <map>
0015 #include <boost/next_prior.hpp>
0016 #include <boost/graph/graph_traits.hpp>
0017 #include <boost/graph/properties.hpp>
0018
0019 namespace boost
0020 {
0021
0022 struct planar_face_traversal_visitor
0023 {
0024     void begin_traversal() {}
0025
0026     void begin_face() {}
0027
0028     template < typename Edge > void next_edge(Edge) {}
0029
0030     template < typename Vertex > void next_vertex(Vertex) {}
0031
0032     void end_face() {}
0033
0034     void end_traversal() {}
0035 };
0036
0037 template < typename Graph, typename PlanarEmbedding, typename Visitor,
0038     typename EdgeIndexMap >
0039 void planar_face_traversal(const Graph& g, PlanarEmbedding embedding,
0040     Visitor& visitor, EdgeIndexMap em)
0041 {
0042     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0043     typedef typename graph_traits< Graph >::edge_descriptor edge_t;
0044     typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
0045     typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
0046     typedef typename property_traits< PlanarEmbedding >::value_type
0047         embedding_value_t;
0048     typedef typename embedding_value_t::const_iterator embedding_iterator_t;
0049
0050     typedef typename std::vector< std::set< vertex_t > >
0051         distinguished_edge_storage_t;
0052     typedef typename std::vector< std::map< vertex_t, edge_t > >
0053         distinguished_edge_to_edge_storage_t;
0054
0055     typedef typename boost::iterator_property_map<
0056         typename distinguished_edge_storage_t::iterator, EdgeIndexMap >
0057         distinguished_edge_map_t;
0058
0059     typedef typename boost::iterator_property_map<
0060         typename distinguished_edge_to_edge_storage_t::iterator, EdgeIndexMap >
0061         distinguished_edge_to_edge_map_t;
0062
0063     distinguished_edge_storage_t visited_vector(num_edges(g));
0064     distinguished_edge_to_edge_storage_t next_edge_vector(num_edges(g));
0065
0066     distinguished_edge_map_t visited(visited_vector.begin(), em);
0067     distinguished_edge_to_edge_map_t next_edge(next_edge_vector.begin(), em);
0068
0069     vertex_iterator_t vi, vi_end;
0070     typename std::vector< edge_t >::iterator ei, ei_end;
0071     edge_iterator_t fi, fi_end;
0072     embedding_iterator_t pi, pi_begin, pi_end;
0073
0074     visitor.begin_traversal();
0075
0076     // Initialize the next_edge property map. This map is initialized from the
0077     // PlanarEmbedding so that get(next_edge, e)[v] is the edge that comes
0078     // after e in the clockwise embedding around vertex v.
0079
0080     for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0081     {
0082         vertex_t v(*vi);
0083         pi_begin = embedding[v].begin();
0084         pi_end = embedding[v].end();
0085         for (pi = pi_begin; pi != pi_end; ++pi)
0086         {
0087             edge_t e(*pi);
0088             std::map< vertex_t, edge_t > m = get(next_edge, e);
0089             m[v] = boost::next(pi) == pi_end ? *pi_begin : *boost::next(pi);
0090             put(next_edge, e, m);
0091         }
0092     }
0093
0094     // Take a copy of the edges in the graph here, since we want to accomodate
0095     // face traversals that add edges to the graph (for triangulation, in
0096     // particular) and don't want to use invalidated edge iterators.
0097     // Also, while iterating over all edges in the graph, we single out
0098     // any self-loops, which need some special treatment in the face traversal.
0099
0100     std::vector< edge_t > self_loops;
0101     std::vector< edge_t > edges_cache;
0102     std::vector< vertex_t > vertices_in_edge;
0103
0104     for (boost::tie(fi, fi_end) = edges(g); fi != fi_end; ++fi)
0105     {
0106         edge_t e(*fi);
0107         edges_cache.push_back(e);
0108         if (source(e, g) == target(e, g))
0109             self_loops.push_back(e);
0110     }
0111
0112     // Iterate over all edges in the graph
0113     ei_end = edges_cache.end();
0114     for (ei = edges_cache.begin(); ei != ei_end; ++ei)
0115     {
0116
0117         edge_t e(*ei);
0118         vertices_in_edge.clear();
0119         vertices_in_edge.push_back(source(e, g));
0120         vertices_in_edge.push_back(target(e, g));
0121
0122         typename std::vector< vertex_t >::iterator vi, vi_end;
0123         vi_end = vertices_in_edge.end();
0124
0125         // Iterate over both vertices in the current edge
0126         for (vi = vertices_in_edge.begin(); vi != vi_end; ++vi)
0127         {
0128
0129             vertex_t v(*vi);
0130             std::set< vertex_t > e_visited = get(visited, e);
0131             typename std::set< vertex_t >::iterator e_visited_found
0132                 = e_visited.find(v);
0133
0134             if (e_visited_found == e_visited.end())
0135                 visitor.begin_face();
0136
0137             while (e_visited.find(v) == e_visited.end())
0138             {
0139                 visitor.next_vertex(v);
0140                 visitor.next_edge(e);
0141                 e_visited.insert(v);
0142                 put(visited, e, e_visited);
0143                 v = source(e, g) == v ? target(e, g) : source(e, g);
0144                 e = get(next_edge, e)[v];
0145                 e_visited = get(visited, e);
0146             }
0147
0148             if (e_visited_found == e_visited.end())
0149                 visitor.end_face();
0150         }
0151     }
0152
0153     // Iterate over all self-loops, visiting them once separately
0154     // (they've already been visited once, this visitation is for
0155     // the "inside" of the self-loop)
0156
0157     ei_end = self_loops.end();
0158     for (ei = self_loops.begin(); ei != ei_end; ++ei)
0159     {
0160         visitor.begin_face();
0161         visitor.next_edge(*ei);
0162         visitor.next_vertex(source(*ei, g));
0163         visitor.end_face();
0164     }
0165
0166     visitor.end_traversal();
0167 }
0168
0169 template < typename Graph, typename PlanarEmbedding, typename Visitor >
0170 inline void planar_face_traversal(
0171     const Graph& g, PlanarEmbedding embedding, Visitor& visitor)
0172 {
0173     planar_face_traversal(g, embedding, visitor, get(edge_index, g));
0174 }
0175
0176 } // namespace boost
0177
0178 #endif //__PLANAR_FACE_TRAVERSAL_HPP__