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
  20 namespace boost
  21 {
  22
  23
  24   namespace detail {
  25     enum planar_canonical_ordering_state
  26          {PCO_PROCESSED,
  27           PCO_UNPROCESSED,
  28           PCO_ONE_NEIGHBOR_PROCESSED,
  29           PCO_READY_TO_BE_PROCESSED};
  30   }
  31
  32   template<typename Graph,
  33            typename PlanarEmbedding,
  34            typename OutputIterator,
  35            typename VertexIndexMap>
  36   void planar_canonical_ordering(const Graph& g,
  37                                  PlanarEmbedding embedding,
  38                                  OutputIterator ordering,
  39                                  VertexIndexMap vm)
  40   {
  41
  42     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  43     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
  44     typedef typename graph_traits<Graph>::adjacency_iterator
  45       adjacency_iterator_t;
  46     typedef typename property_traits<PlanarEmbedding>::value_type
  47       embedding_value_t;
  48     typedef typename embedding_value_t::const_iterator embedding_iterator_t;
  49     typedef iterator_property_map
  50       <typename std::vector<vertex_t>::iterator, VertexIndexMap>
  51       vertex_to_vertex_map_t;
  52     typedef iterator_property_map
  53       <typename std::vector<std::size_t>::iterator, VertexIndexMap>
  54       vertex_to_size_t_map_t;
  55
  56     std::vector<vertex_t> processed_neighbor_vector(num_vertices(g));
  57     vertex_to_vertex_map_t processed_neighbor
  58       (processed_neighbor_vector.begin(), vm);
  59
  60     std::vector<std::size_t> status_vector(num_vertices(g), detail::PCO_UNPROCESSED);
  61     vertex_to_size_t_map_t status(status_vector.begin(), vm);
  62
  63     std::list<vertex_t> ready_to_be_processed;
  64
  65     vertex_t first_vertex = *vertices(g).first;
  66     vertex_t second_vertex;
  67     adjacency_iterator_t ai, ai_end;
  68     for(boost::tie(ai,ai_end) = adjacent_vertices(first_vertex,g); ai != ai_end; ++ai)
  69       {
  70         if (*ai == first_vertex)
  71           continue;
  72         second_vertex = *ai;
  73         break;
  74       }
  75
  76     ready_to_be_processed.push_back(first_vertex);
  77     status[first_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
  78     ready_to_be_processed.push_back(second_vertex);
  79     status[second_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
  80
  81     while(!ready_to_be_processed.empty())
  82       {
  83         vertex_t u = ready_to_be_processed.front();
  84         ready_to_be_processed.pop_front();
  85
  86         if (status[u] != detail::PCO_READY_TO_BE_PROCESSED && 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 = boost::next(ei) == ei_end ? ei_start : boost::next(ei);
 103             vertex_t v = source(e,g) == u ? target(e,g) : source(e,g);
 104
 105             vertex_t prior_vertex = source(*prior_edge_itr, g) == u ?
 106               target(*prior_edge_itr, g) : source(*prior_edge_itr, g);
 107             vertex_t next_vertex = source(*next_edge_itr, g) == u ?
 108               target(*next_edge_itr, g) : source(*next_edge_itr, g);
 109
 110             // Need prior_vertex, u, v, and next_vertex to all be
 111             // distinct. This is possible, since the input graph is
 112             // triangulated. It'll be true all the time in a simple
 113             // graph, but loops and parallel edges cause some complications.
 114             if (prior_vertex == v || prior_vertex == u)
 115               {
 116                 prior_edge_itr = ei;
 117                 continue;
 118               }
 119
 120             //Skip any self-loops
 121             if (u == v)
 122                 continue;
 123
 124             // Move next_edge_itr (and next_vertex) forwards
 125             // past any loops or parallel edges
 126             while (next_vertex == v || next_vertex == u)
 127               {
 128                 next_edge_itr = boost::next(next_edge_itr) == ei_end ?
 129                   ei_start : boost::next(next_edge_itr);
 130                 next_vertex = source(*next_edge_itr, g) == u ?
 131                   target(*next_edge_itr, g) : source(*next_edge_itr, g);
 132               }
 133
 134
 135             if (status[v] == detail::PCO_UNPROCESSED)
 136               {
 137                 status[v] = detail::PCO_ONE_NEIGHBOR_PROCESSED;
 138                 processed_neighbor[v] = u;
 139               }
 140             else if (status[v] == detail::PCO_ONE_NEIGHBOR_PROCESSED)
 141               {
 142                 vertex_t x = processed_neighbor[v];
 143                 //are edges (v,u) and (v,x) adjacent in the planar
 144                 //embedding? if so, set status[v] = 1. otherwise, set
 145                 //status[v] = 2.
 146
 147                 if ((next_vertex == x &&
 148                      !(first_vertex == u && second_vertex == x)
 149                      )
 150                     ||
 151                     (prior_vertex == x &&
 152                      !(first_vertex == x && second_vertex == u)
 153                      )
 154                     )
 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
 184             if (status[v] == detail::PCO_READY_TO_BE_PROCESSED)
 185               ready_to_be_processed.push_back(v);
 186
 187             prior_edge_itr = ei;
 188
 189           }
 190
 191         status[u] = detail::PCO_PROCESSED;
 192         *ordering = u;
 193         ++ordering;
 194
 195       }
 196
 197   }
 198
 199
 200   template<typename Graph, typename PlanarEmbedding, typename OutputIterator>
 201   void planar_canonical_ordering(const Graph& g,
 202                                  PlanarEmbedding embedding,
 203                                  OutputIterator ordering
 204                                  )
 205   {
 206     planar_canonical_ordering(g, embedding, ordering, get(vertex_index,g));
 207   }
 208
 209
 210 } //namespace boost
 211
 212 #endif //__PLANAR_CANONICAL_ORDERING_HPP__