boost/graph/planar_canonical_ordering.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_CANONICAL_ORDERING_HPP__
0010 #define __PLANAR_CANONICAL_ORDERING_HPP__
0011
0012 #include <vector>
0013 #include <list>
0014 #include <boost/config.hpp>
0015 #include <boost/next_prior.hpp>
0016 #include <boost/graph/graph_traits.hpp>
0017 #include <boost/graph/properties.hpp>
0018 #include <boost/property_map/property_map.hpp>
0019
0020 namespace boost
0021 {
0022
0023 namespace detail
0024 {
0025     enum planar_canonical_ordering_state
0026     {
0027         PCO_PROCESSED,
0028         PCO_UNPROCESSED,
0029         PCO_ONE_NEIGHBOR_PROCESSED,
0030         PCO_READY_TO_BE_PROCESSED
0031     };
0032 }
0033
0034 template < typename Graph, typename PlanarEmbedding, typename OutputIterator,
0035     typename VertexIndexMap >
0036 void planar_canonical_ordering(const Graph& g, PlanarEmbedding embedding,
0037     OutputIterator ordering, VertexIndexMap vm)
0038 {
0039
0040     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0041     typedef typename graph_traits< Graph >::edge_descriptor edge_t;
0042     typedef
0043         typename graph_traits< Graph >::adjacency_iterator adjacency_iterator_t;
0044     typedef typename property_traits< PlanarEmbedding >::value_type
0045         embedding_value_t;
0046     typedef typename embedding_value_t::const_iterator embedding_iterator_t;
0047     typedef iterator_property_map< typename std::vector< vertex_t >::iterator,
0048         VertexIndexMap >
0049         vertex_to_vertex_map_t;
0050     typedef iterator_property_map<
0051         typename std::vector< std::size_t >::iterator, VertexIndexMap >
0052         vertex_to_size_t_map_t;
0053
0054     std::vector< vertex_t > processed_neighbor_vector(num_vertices(g));
0055     vertex_to_vertex_map_t processed_neighbor(
0056         processed_neighbor_vector.begin(), vm);
0057
0058     std::vector< std::size_t > status_vector(
0059         num_vertices(g), detail::PCO_UNPROCESSED);
0060     vertex_to_size_t_map_t status(status_vector.begin(), vm);
0061
0062     std::list< vertex_t > ready_to_be_processed;
0063
0064     vertex_t first_vertex = *vertices(g).first;
0065     vertex_t second_vertex = first_vertex;
0066     adjacency_iterator_t ai, ai_end;
0067     for (boost::tie(ai, ai_end) = adjacent_vertices(first_vertex, g);
0068          ai != ai_end; ++ai)
0069     {
0070         if (*ai == first_vertex)
0071             continue;
0072         second_vertex = *ai;
0073         break;
0074     }
0075
0076     ready_to_be_processed.push_back(first_vertex);
0077     status[first_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
0078     ready_to_be_processed.push_back(second_vertex);
0079     status[second_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
0080
0081     while (!ready_to_be_processed.empty())
0082     {
0083         vertex_t u = ready_to_be_processed.front();
0084         ready_to_be_processed.pop_front();
0085
0086         if (status[u] != detail::PCO_READY_TO_BE_PROCESSED
0087             && u != second_vertex)
0088             continue;
0089
0090         embedding_iterator_t ei, ei_start, ei_end;
0091         embedding_iterator_t next_edge_itr, prior_edge_itr;
0092
0093         ei_start = embedding[u].begin();
0094         ei_end = embedding[u].end();
0095         prior_edge_itr = prior(ei_end);
0096         while (source(*prior_edge_itr, g) == target(*prior_edge_itr, g))
0097             prior_edge_itr = prior(prior_edge_itr);
0098
0099         for (ei = ei_start; ei != ei_end; ++ei)
0100         {
0101
0102             edge_t e(*ei); // e = (u,v)
0103             next_edge_itr
0104                 = boost::next(ei) == ei_end ? ei_start : boost::next(ei);
0105             vertex_t v = source(e, g) == u ? target(e, g) : source(e, g);
0106
0107             vertex_t prior_vertex = source(*prior_edge_itr, g) == u
0108                 ? target(*prior_edge_itr, g)
0109                 : source(*prior_edge_itr, g);
0110             vertex_t next_vertex = source(*next_edge_itr, g) == u
0111                 ? target(*next_edge_itr, g)
0112                 : source(*next_edge_itr, g);
0113
0114             // Need prior_vertex, u, v, and next_vertex to all be
0115             // distinct. This is possible, since the input graph is
0116             // triangulated. It'll be true all the time in a simple
0117             // graph, but loops and parallel edges cause some complications.
0118             if (prior_vertex == v || prior_vertex == u)
0119             {
0120                 prior_edge_itr = ei;
0121                 continue;
0122             }
0123
0124             // Skip any self-loops
0125             if (u == v)
0126                 continue;
0127
0128             // Move next_edge_itr (and next_vertex) forwards
0129             // past any loops or parallel edges
0130             while (next_vertex == v || next_vertex == u)
0131             {
0132                 next_edge_itr = boost::next(next_edge_itr) == ei_end
0133                     ? ei_start
0134                     : boost::next(next_edge_itr);
0135                 next_vertex = source(*next_edge_itr, g) == u
0136                     ? target(*next_edge_itr, g)
0137                     : source(*next_edge_itr, g);
0138             }
0139
0140             if (status[v] == detail::PCO_UNPROCESSED)
0141             {
0142                 status[v] = detail::PCO_ONE_NEIGHBOR_PROCESSED;
0143                 processed_neighbor[v] = u;
0144             }
0145             else if (status[v] == detail::PCO_ONE_NEIGHBOR_PROCESSED)
0146             {
0147                 vertex_t x = processed_neighbor[v];
0148                 // are edges (v,u) and (v,x) adjacent in the planar
0149                 // embedding? if so, set status[v] = 1. otherwise, set
0150                 // status[v] = 2.
0151
0152                 if ((next_vertex == x
0153                         && !(first_vertex == u && second_vertex == x))
0154                     || (prior_vertex == x
0155                         && !(first_vertex == x && second_vertex == u)))
0156                 {
0157                     status[v] = detail::PCO_READY_TO_BE_PROCESSED;
0158                 }
0159                 else
0160                 {
0161                     status[v] = detail::PCO_READY_TO_BE_PROCESSED + 1;
0162                 }
0163             }
0164             else if (status[v] > detail::PCO_ONE_NEIGHBOR_PROCESSED)
0165             {
0166                 // check the two edges before and after (v,u) in the planar
0167                 // embedding, and update status[v] accordingly
0168
0169                 bool processed_before = false;
0170                 if (status[prior_vertex] == detail::PCO_PROCESSED)
0171                     processed_before = true;
0172
0173                 bool processed_after = false;
0174                 if (status[next_vertex] == detail::PCO_PROCESSED)
0175                     processed_after = true;
0176
0177                 if (!processed_before && !processed_after)
0178                     ++status[v];
0179
0180                 else if (processed_before && processed_after)
0181                     --status[v];
0182             }
0183
0184             if (status[v] == detail::PCO_READY_TO_BE_PROCESSED)
0185                 ready_to_be_processed.push_back(v);
0186
0187             prior_edge_itr = ei;
0188         }
0189
0190         status[u] = detail::PCO_PROCESSED;
0191         *ordering = u;
0192         ++ordering;
0193     }
0194 }
0195
0196 template < typename Graph, typename PlanarEmbedding, typename OutputIterator >
0197 void planar_canonical_ordering(
0198     const Graph& g, PlanarEmbedding embedding, OutputIterator ordering)
0199 {
0200     planar_canonical_ordering(g, embedding, ordering, get(vertex_index, g));
0201 }
0202
0203 } // namespace boost
0204
0205 #endif //__PLANAR_CANONICAL_ORDERING_HPP__