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