Chris@16: //=======================================================================
Chris@16: // Copyright (c) Aaron Windsor 2007
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: 
Chris@16: #ifndef __PLANAR_CANONICAL_ORDERING_HPP__
Chris@16: #define __PLANAR_CANONICAL_ORDERING_HPP__
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <list>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/next_prior.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16:   namespace detail {
Chris@16:     enum planar_canonical_ordering_state
Chris@16:          {PCO_PROCESSED, 
Chris@16:           PCO_UNPROCESSED, 
Chris@16:           PCO_ONE_NEIGHBOR_PROCESSED, 
Chris@16:           PCO_READY_TO_BE_PROCESSED};
Chris@16:   }
Chris@16:     
Chris@16:   template<typename Graph, 
Chris@16:            typename PlanarEmbedding, 
Chris@16:            typename OutputIterator, 
Chris@16:            typename VertexIndexMap>
Chris@16:   void planar_canonical_ordering(const Graph& g, 
Chris@16:                                  PlanarEmbedding embedding, 
Chris@16:                                  OutputIterator ordering, 
Chris@16:                                  VertexIndexMap vm)
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>::adjacency_iterator
Chris@16:       adjacency_iterator_t;
Chris@16:     typedef typename property_traits<PlanarEmbedding>::value_type 
Chris@16:       embedding_value_t;
Chris@16:     typedef typename embedding_value_t::const_iterator embedding_iterator_t;
Chris@16:     typedef iterator_property_map
Chris@16:       <typename std::vector<vertex_t>::iterator, VertexIndexMap> 
Chris@16:       vertex_to_vertex_map_t;
Chris@16:     typedef iterator_property_map
Chris@16:       <typename std::vector<std::size_t>::iterator, VertexIndexMap> 
Chris@16:       vertex_to_size_t_map_t;
Chris@16:     
Chris@16:     std::vector<vertex_t> processed_neighbor_vector(num_vertices(g));
Chris@16:     vertex_to_vertex_map_t processed_neighbor
Chris@16:       (processed_neighbor_vector.begin(), vm);
Chris@16: 
Chris@16:     std::vector<std::size_t> status_vector(num_vertices(g), detail::PCO_UNPROCESSED);
Chris@16:     vertex_to_size_t_map_t status(status_vector.begin(), vm);
Chris@16: 
Chris@16:     std::list<vertex_t> ready_to_be_processed;
Chris@16:     
Chris@16:     vertex_t first_vertex = *vertices(g).first;
Chris@16:     vertex_t second_vertex;
Chris@16:     adjacency_iterator_t ai, ai_end;
Chris@16:     for(boost::tie(ai,ai_end) = adjacent_vertices(first_vertex,g); ai != ai_end; ++ai)
Chris@16:       {
Chris@16:         if (*ai == first_vertex)
Chris@16:           continue;
Chris@16:         second_vertex = *ai;
Chris@16:         break;
Chris@16:       }
Chris@16: 
Chris@16:     ready_to_be_processed.push_back(first_vertex);
Chris@16:     status[first_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
Chris@16:     ready_to_be_processed.push_back(second_vertex);
Chris@16:     status[second_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
Chris@16: 
Chris@16:     while(!ready_to_be_processed.empty())
Chris@16:       {
Chris@16:         vertex_t u = ready_to_be_processed.front();
Chris@16:         ready_to_be_processed.pop_front();
Chris@16: 
Chris@16:         if (status[u] != detail::PCO_READY_TO_BE_PROCESSED && u != second_vertex)
Chris@16:           continue;
Chris@16: 
Chris@16:         embedding_iterator_t ei, ei_start, ei_end;
Chris@16:         embedding_iterator_t next_edge_itr, prior_edge_itr;
Chris@16: 
Chris@16:         ei_start = embedding[u].begin();
Chris@16:         ei_end = embedding[u].end();
Chris@16:         prior_edge_itr = prior(ei_end);
Chris@16:         while(source(*prior_edge_itr, g) == target(*prior_edge_itr,g))
Chris@16:           prior_edge_itr = prior(prior_edge_itr);
Chris@16: 
Chris@16:         for(ei = ei_start; ei != ei_end; ++ei)
Chris@16:           {
Chris@16:             
Chris@16:             edge_t e(*ei); // e = (u,v)
Chris@16:             next_edge_itr = boost::next(ei) == ei_end ? ei_start : boost::next(ei);
Chris@16:             vertex_t v = source(e,g) == u ? target(e,g) : source(e,g);
Chris@16: 
Chris@16:             vertex_t prior_vertex = source(*prior_edge_itr, g) == u ? 
Chris@16:               target(*prior_edge_itr, g) : source(*prior_edge_itr, g);
Chris@16:             vertex_t next_vertex = source(*next_edge_itr, g) == u ? 
Chris@16:               target(*next_edge_itr, g) : source(*next_edge_itr, g);
Chris@16: 
Chris@16:             // Need prior_vertex, u, v, and next_vertex to all be
Chris@16:             // distinct. This is possible, since the input graph is
Chris@16:             // triangulated. It'll be true all the time in a simple
Chris@16:             // graph, but loops and parallel edges cause some complications.
Chris@16:             if (prior_vertex == v || prior_vertex == u)
Chris@16:               {
Chris@16:                 prior_edge_itr = ei;
Chris@16:                 continue;
Chris@16:               }
Chris@16: 
Chris@16:             //Skip any self-loops
Chris@16:             if (u == v)
Chris@16:                 continue;
Chris@16:                                                                 
Chris@16:             // Move next_edge_itr (and next_vertex) forwards
Chris@16:             // past any loops or parallel edges
Chris@16:             while (next_vertex == v || next_vertex == u)
Chris@16:               {
Chris@16:                 next_edge_itr = boost::next(next_edge_itr) == ei_end ?
Chris@16:                   ei_start : boost::next(next_edge_itr);
Chris@16:                 next_vertex = source(*next_edge_itr, g) == u ? 
Chris@16:                   target(*next_edge_itr, g) : source(*next_edge_itr, g);
Chris@16:               }
Chris@16: 
Chris@16: 
Chris@16:             if (status[v] == detail::PCO_UNPROCESSED)
Chris@16:               {
Chris@16:                 status[v] = detail::PCO_ONE_NEIGHBOR_PROCESSED;
Chris@16:                 processed_neighbor[v] = u;
Chris@16:               }
Chris@16:             else if (status[v] == detail::PCO_ONE_NEIGHBOR_PROCESSED)
Chris@16:               {
Chris@16:                 vertex_t x = processed_neighbor[v];
Chris@16:                 //are edges (v,u) and (v,x) adjacent in the planar
Chris@16:                 //embedding? if so, set status[v] = 1. otherwise, set
Chris@16:                 //status[v] = 2.
Chris@16: 
Chris@16:                 if ((next_vertex == x &&
Chris@16:                      !(first_vertex == u && second_vertex == x)
Chris@16:                      )
Chris@16:                     ||
Chris@16:                     (prior_vertex == x &&
Chris@16:                      !(first_vertex == x && second_vertex == u)
Chris@16:                      )
Chris@16:                     )
Chris@16:                   {
Chris@16:                     status[v] = detail::PCO_READY_TO_BE_PROCESSED;
Chris@16:                   }
Chris@16:                 else
Chris@16:                   {
Chris@16:                     status[v] = detail::PCO_READY_TO_BE_PROCESSED + 1;
Chris@16:                   }                                                        
Chris@16:               }
Chris@16:             else if (status[v] > detail::PCO_ONE_NEIGHBOR_PROCESSED)
Chris@16:               {
Chris@16:                 //check the two edges before and after (v,u) in the planar
Chris@16:                 //embedding, and update status[v] accordingly
Chris@16: 
Chris@16:                 bool processed_before = false;
Chris@16:                 if (status[prior_vertex] == detail::PCO_PROCESSED)
Chris@16:                   processed_before = true;
Chris@16: 
Chris@16:                 bool processed_after = false;
Chris@16:                 if (status[next_vertex] == detail::PCO_PROCESSED)
Chris@16:                   processed_after = true;
Chris@16: 
Chris@16:                 if (!processed_before && !processed_after)
Chris@16:                     ++status[v];
Chris@16: 
Chris@16:                 else if (processed_before && processed_after)
Chris@16:                     --status[v];
Chris@16: 
Chris@16:               }
Chris@16: 
Chris@16:             if (status[v] == detail::PCO_READY_TO_BE_PROCESSED)
Chris@16:               ready_to_be_processed.push_back(v);
Chris@16: 
Chris@16:             prior_edge_itr = ei;
Chris@16: 
Chris@16:           }
Chris@16: 
Chris@16:         status[u] = detail::PCO_PROCESSED;
Chris@16:         *ordering = u;
Chris@16:         ++ordering;
Chris@16:         
Chris@16:       }
Chris@16:     
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   template<typename Graph, typename PlanarEmbedding, typename OutputIterator>
Chris@16:   void planar_canonical_ordering(const Graph& g, 
Chris@16:                                  PlanarEmbedding embedding, 
Chris@16:                                  OutputIterator ordering
Chris@16:                                  )
Chris@16:   {
Chris@16:     planar_canonical_ordering(g, embedding, ordering, get(vertex_index,g));
Chris@16:   }
Chris@16:  
Chris@16: 
Chris@16: } //namespace boost
Chris@16: 
Chris@16: #endif //__PLANAR_CANONICAL_ORDERING_HPP__