ceph/src/boost/boost/graph/planar_canonical_ordering.hpp

   1 //=======================================================================
   2 // Copyright (c) Aaron Windsor 2007
   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
   9 #ifndef __PLANAR_CANONICAL_ORDERING_HPP__
  10 #define __PLANAR_CANONICAL_ORDERING_HPP__
  11
  12 #include <vector>
  13 #include <list>
  14 #include <boost/config.hpp>
  15 #include <boost/next_prior.hpp>
  16 #include <boost/graph/graph_traits.hpp>
  17 #include <boost/property_map/property_map.hpp>
  18
  19 namespace boost
  20 {
  21
  22 namespace detail
  23 {
  24     enum planar_canonical_ordering_state
  25     {
  26         PCO_PROCESSED,
  27         PCO_UNPROCESSED,
  28         PCO_ONE_NEIGHBOR_PROCESSED,
  29         PCO_READY_TO_BE_PROCESSED
  30     };
  31 }
  32
  33 template < typename Graph, typename PlanarEmbedding, typename OutputIterator,
  34     typename VertexIndexMap >
  35 void planar_canonical_ordering(const Graph& g, PlanarEmbedding embedding,
  36     OutputIterator ordering, VertexIndexMap vm)
  37 {
  38
  39     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
  40     typedef typename graph_traits< Graph >::edge_descriptor edge_t;
  41     typedef
  42         typename graph_traits< Graph >::adjacency_iterator adjacency_iterator_t;
  43     typedef typename property_traits< PlanarEmbedding >::value_type
  44         embedding_value_t;
  45     typedef typename embedding_value_t::const_iterator embedding_iterator_t;
  46     typedef iterator_property_map< typename std::vector< vertex_t >::iterator,
  47         VertexIndexMap >
  48         vertex_to_vertex_map_t;
  49     typedef iterator_property_map<
  50         typename std::vector< std::size_t >::iterator, VertexIndexMap >
  51         vertex_to_size_t_map_t;
  52
  53     std::vector< vertex_t > processed_neighbor_vector(num_vertices(g));
  54     vertex_to_vertex_map_t processed_neighbor(
  55         processed_neighbor_vector.begin(), vm);
  56
  57     std::vector< std::size_t > status_vector(
  58         num_vertices(g), detail::PCO_UNPROCESSED);
  59     vertex_to_size_t_map_t status(status_vector.begin(), vm);
  60
  61     std::list< vertex_t > ready_to_be_processed;
  62
  63     vertex_t first_vertex = *vertices(g).first;
  64     vertex_t second_vertex = first_vertex;
  65     adjacency_iterator_t ai, ai_end;
  66     for (boost::tie(ai, ai_end) = adjacent_vertices(first_vertex, g);
  67          ai != ai_end; ++ai)
  68     {
  69         if (*ai == first_vertex)
  70             continue;
  71         second_vertex = *ai;
  72         break;
  73     }
  74
  75     ready_to_be_processed.push_back(first_vertex);
  76     status[first_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
  77     ready_to_be_processed.push_back(second_vertex);
  78     status[second_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
  79
  80     while (!ready_to_be_processed.empty())
  81     {
  82         vertex_t u = ready_to_be_processed.front();
  83         ready_to_be_processed.pop_front();
  84
  85         if (status[u] != detail::PCO_READY_TO_BE_PROCESSED
  86             && u != second_vertex)
  87             continue;
  88
  89         embedding_iterator_t ei, ei_start, ei_end;
  90         embedding_iterator_t next_edge_itr, prior_edge_itr;
  91
  92         ei_start = embedding[u].begin();
  93         ei_end = embedding[u].end();
  94         prior_edge_itr = prior(ei_end);
  95         while (source(*prior_edge_itr, g) == target(*prior_edge_itr, g))
  96             prior_edge_itr = prior(prior_edge_itr);
  97
  98         for (ei = ei_start; ei != ei_end; ++ei)
  99         {
 100
 101             edge_t e(*ei); // e = (u,v)
 102             next_edge_itr
 103                 = boost::next(ei) == ei_end ? ei_start : boost::next(ei);
 104             vertex_t v = source(e, g) == u ? target(e, g) : source(e, g);
 105
 106             vertex_t prior_vertex = source(*prior_edge_itr, g) == u
 107                 ? target(*prior_edge_itr, g)
 108                 : source(*prior_edge_itr, g);
 109             vertex_t next_vertex = source(*next_edge_itr, g) == u
 110                 ? target(*next_edge_itr, g)
 111                 : source(*next_edge_itr, g);
 112
 113             // Need prior_vertex, u, v, and next_vertex to all be
 114             // distinct. This is possible, since the input graph is
 115             // triangulated. It'll be true all the time in a simple
 116             // graph, but loops and parallel edges cause some complications.
 117             if (prior_vertex == v || prior_vertex == u)
 118             {
 119                 prior_edge_itr = ei;
 120                 continue;
 121             }
 122
 123             // Skip any self-loops
 124             if (u == v)
 125                 continue;
 126
 127             // Move next_edge_itr (and next_vertex) forwards
 128             // past any loops or parallel edges
 129             while (next_vertex == v || next_vertex == u)
 130             {
 131                 next_edge_itr = boost::next(next_edge_itr) == ei_end
 132                     ? ei_start
 133                     : boost::next(next_edge_itr);
 134                 next_vertex = source(*next_edge_itr, g) == u
 135                     ? target(*next_edge_itr, g)
 136                     : source(*next_edge_itr, g);
 137             }
 138
 139             if (status[v] == detail::PCO_UNPROCESSED)
 140             {
 141                 status[v] = detail::PCO_ONE_NEIGHBOR_PROCESSED;
 142                 processed_neighbor[v] = u;
 143             }
 144             else if (status[v] == detail::PCO_ONE_NEIGHBOR_PROCESSED)
 145             {
 146                 vertex_t x = processed_neighbor[v];
 147                 // are edges (v,u) and (v,x) adjacent in the planar
 148                 // embedding? if so, set status[v] = 1. otherwise, set
 149                 // status[v] = 2.
 150
 151                 if ((next_vertex == x
 152                         && !(first_vertex == u && second_vertex == x))
 153                     || (prior_vertex == x
 154                         && !(first_vertex == x && second_vertex == u)))
 155                 {
 156                     status[v] = detail::PCO_READY_TO_BE_PROCESSED;
 157                 }
 158                 else
 159                 {
 160                     status[v] = detail::PCO_READY_TO_BE_PROCESSED + 1;
 161                 }
 162             }
 163             else if (status[v] > detail::PCO_ONE_NEIGHBOR_PROCESSED)
 164             {
 165                 // check the two edges before and after (v,u) in the planar
 166                 // embedding, and update status[v] accordingly
 167
 168                 bool processed_before = false;
 169                 if (status[prior_vertex] == detail::PCO_PROCESSED)
 170                     processed_before = true;
 171
 172                 bool processed_after = false;
 173                 if (status[next_vertex] == detail::PCO_PROCESSED)
 174                     processed_after = true;
 175
 176                 if (!processed_before && !processed_after)
 177                     ++status[v];
 178
 179                 else if (processed_before && processed_after)
 180                     --status[v];
 181             }
 182
 183             if (status[v] == detail::PCO_READY_TO_BE_PROCESSED)
 184                 ready_to_be_processed.push_back(v);
 185
 186             prior_edge_itr = ei;
 187         }
 188
 189         status[u] = detail::PCO_PROCESSED;
 190         *ordering = u;
 191         ++ordering;
 192     }
 193 }
 194
 195 template < typename Graph, typename PlanarEmbedding, typename OutputIterator >
 196 void planar_canonical_ordering(
 197     const Graph& g, PlanarEmbedding embedding, OutputIterator ordering)
 198 {
 199     planar_canonical_ordering(g, embedding, ordering, get(vertex_index, g));
 200 }
 201
 202 } // namespace boost
 203
 204 #endif //__PLANAR_CANONICAL_ORDERING_HPP__