boost/graph/chrobak_payne_drawing.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 __CHROBAK_PAYNE_DRAWING_HPP__
  10 #define __CHROBAK_PAYNE_DRAWING_HPP__
  11
  12 #include <vector>
  13 #include <list>
  14 #include <boost/config.hpp>
  15 #include <boost/utility.hpp>  //for next and prior
  16 #include <boost/graph/graph_traits.hpp>
  17 #include <boost/property_map/property_map.hpp>
  18
  19
  20 namespace boost
  21 {
  22
  23   namespace graph { namespace detail
  24   {
  25
  26     template<typename Graph,
  27              typename VertexToVertexMap,
  28              typename VertexTo1DCoordMap>
  29     void accumulate_offsets(typename graph_traits<Graph>::vertex_descriptor v,
  30                             std::size_t offset,
  31                             const Graph& g,
  32                             VertexTo1DCoordMap x,
  33                             VertexTo1DCoordMap delta_x,
  34                             VertexToVertexMap left,
  35                             VertexToVertexMap right)
  36     {
  37       if (v != graph_traits<Graph>::null_vertex())
  38         {
  39           x[v] += delta_x[v] + offset;
  40           accumulate_offsets(left[v], x[v], g, x, delta_x, left, right);
  41           accumulate_offsets(right[v], x[v], g, x, delta_x, left, right);
  42         }
  43     }
  44
  45   } /*namespace detail*/ } /*namespace graph*/
  46
  47
  48
  49
  50
  51   template<typename Graph,
  52            typename PlanarEmbedding,
  53            typename ForwardIterator,
  54            typename GridPositionMap,
  55            typename VertexIndexMap>
  56   void chrobak_payne_straight_line_drawing(const Graph& g,
  57                                            PlanarEmbedding embedding,
  58                                            ForwardIterator ordering_begin,
  59                                            ForwardIterator ordering_end,
  60                                            GridPositionMap drawing,
  61                                            VertexIndexMap vm
  62                                            )
  63   {
  64
  65     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  66     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
  67     typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
  68     typedef typename PlanarEmbedding::value_type::const_iterator
  69       edge_permutation_iterator_t;
  70     typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
  71     typedef std::vector<vertex_t> vertex_vector_t;
  72     typedef std::vector<v_size_t> vsize_vector_t;
  73     typedef std::vector<bool> bool_vector_t;
  74     typedef boost::iterator_property_map
  75       <typename vertex_vector_t::iterator, VertexIndexMap>
  76       vertex_to_vertex_map_t;
  77     typedef boost::iterator_property_map
  78       <typename vsize_vector_t::iterator, VertexIndexMap>
  79       vertex_to_vsize_map_t;
  80     typedef boost::iterator_property_map
  81       <typename bool_vector_t::iterator, VertexIndexMap>
  82       vertex_to_bool_map_t;
  83
  84     vertex_vector_t left_vector(num_vertices(g),
  85                                 graph_traits<Graph>::null_vertex()
  86                                 );
  87     vertex_vector_t right_vector(num_vertices(g),
  88                                  graph_traits<Graph>::null_vertex()
  89                                  );
  90     vsize_vector_t seen_as_right_vector(num_vertices(g), 0);
  91     vsize_vector_t seen_vector(num_vertices(g), 0);
  92     vsize_vector_t delta_x_vector(num_vertices(g),0);
  93     vsize_vector_t y_vector(num_vertices(g));
  94     vsize_vector_t x_vector(num_vertices(g),0);
  95     bool_vector_t installed_vector(num_vertices(g),false);
  96
  97     vertex_to_vertex_map_t left(left_vector.begin(), vm);
  98     vertex_to_vertex_map_t right(right_vector.begin(), vm);
  99     vertex_to_vsize_map_t seen_as_right(seen_as_right_vector.begin(), vm);
 100     vertex_to_vsize_map_t seen(seen_vector.begin(), vm);
 101     vertex_to_vsize_map_t delta_x(delta_x_vector.begin(), vm);
 102     vertex_to_vsize_map_t y(y_vector.begin(), vm);
 103     vertex_to_vsize_map_t x(x_vector.begin(), vm);
 104     vertex_to_bool_map_t installed(installed_vector.begin(), vm);
 105
 106     v_size_t timestamp = 1;
 107     vertex_vector_t installed_neighbors;
 108
 109     ForwardIterator itr = ordering_begin;
 110     vertex_t v1 = *itr; ++itr;
 111     vertex_t v2 = *itr; ++itr;
 112     vertex_t v3 = *itr; ++itr;
 113
 114     delta_x[v2] = 1;
 115     delta_x[v3] = 1;
 116
 117     y[v1] = 0;
 118     y[v2] = 0;
 119     y[v3] = 1;
 120
 121     right[v1] = v3;
 122     right[v3] = v2;
 123
 124     installed[v1] = installed[v2] = installed[v3] = true;
 125
 126     for(ForwardIterator itr_end = ordering_end; itr != itr_end; ++itr)
 127       {
 128         vertex_t v = *itr;
 129
 130         // First, find the leftmost and rightmost neighbor of v on the outer
 131         // cycle of the embedding.
 132         // Note: since we're moving clockwise through the edges adjacent to v,
 133         // we're actually moving from right to left among v's neighbors on the
 134         // outer face (since v will be installed above them all) looking for
 135         // the leftmost and rightmost installed neigbhors
 136
 137         vertex_t leftmost = graph_traits<Graph>::null_vertex();
 138         vertex_t rightmost = graph_traits<Graph>::null_vertex();
 139
 140         installed_neighbors.clear();
 141
 142         vertex_t prev_vertex = graph_traits<Graph>::null_vertex();
 143         edge_permutation_iterator_t pi, pi_end;
 144         pi_end = embedding[v].end();
 145         for(pi = embedding[v].begin(); pi != pi_end; ++pi)
 146           {
 147             vertex_t curr_vertex = source(*pi,g) == v ?
 148               target(*pi,g) : source(*pi,g);
 149
 150             // Skip any self-loops or parallel edges
 151             if (curr_vertex == v || curr_vertex == prev_vertex)
 152                 continue;
 153
 154             if (installed[curr_vertex])
 155               {
 156                 seen[curr_vertex] = timestamp;
 157
 158                 if (right[curr_vertex] != graph_traits<Graph>::null_vertex())
 159                   {
 160                     seen_as_right[right[curr_vertex]] = timestamp;
 161                   }
 162                 installed_neighbors.push_back(curr_vertex);
 163               }
 164
 165             prev_vertex = curr_vertex;
 166           }
 167
 168         typename vertex_vector_t::iterator vi, vi_end;
 169         vi_end = installed_neighbors.end();
 170         for(vi = installed_neighbors.begin(); vi != vi_end; ++vi)
 171           {
 172             if (right[*vi] == graph_traits<Graph>::null_vertex() ||
 173                 seen[right[*vi]] != timestamp
 174                 )
 175               rightmost = *vi;
 176             if (seen_as_right[*vi] != timestamp)
 177               leftmost = *vi;
 178           }
 179
 180         ++timestamp;
 181
 182         //stretch gaps
 183         ++delta_x[right[leftmost]];
 184         ++delta_x[rightmost];
 185
 186         //adjust offsets
 187         std::size_t delta_p_q = 0;
 188         vertex_t stopping_vertex = right[rightmost];
 189         for(vertex_t temp = right[leftmost]; temp != stopping_vertex;
 190             temp = right[temp]
 191             )
 192           {
 193             delta_p_q += delta_x[temp];
 194           }
 195
 196         delta_x[v] = ((y[rightmost] + delta_p_q) - y[leftmost])/2;
 197         y[v] = y[leftmost] + delta_x[v];
 198         delta_x[rightmost] = delta_p_q - delta_x[v];
 199
 200         bool leftmost_and_rightmost_adjacent = right[leftmost] == rightmost;
 201         if (!leftmost_and_rightmost_adjacent)
 202           delta_x[right[leftmost]] -= delta_x[v];
 203
 204         //install v
 205         if (!leftmost_and_rightmost_adjacent)
 206           {
 207             left[v] = right[leftmost];
 208             vertex_t next_to_rightmost;
 209             for(vertex_t temp = leftmost; temp != rightmost;
 210                 temp = right[temp]
 211                 )
 212               {
 213                 next_to_rightmost = temp;
 214               }
 215
 216             right[next_to_rightmost] = graph_traits<Graph>::null_vertex();
 217           }
 218         else
 219           {
 220             left[v] = graph_traits<Graph>::null_vertex();
 221           }
 222
 223         right[leftmost] = v;
 224         right[v] = rightmost;
 225         installed[v] = true;
 226
 227       }
 228
 229     graph::detail::accumulate_offsets
 230       (*ordering_begin,0,g,x,delta_x,left,right);
 231
 232     vertex_iterator_t vi, vi_end;
 233     for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
 234       {
 235         vertex_t v(*vi);
 236         drawing[v].x = x[v];
 237         drawing[v].y = y[v];
 238       }
 239
 240   }
 241
 242
 243
 244
 245   template<typename Graph,
 246            typename PlanarEmbedding,
 247            typename ForwardIterator,
 248            typename GridPositionMap>
 249   inline void chrobak_payne_straight_line_drawing(const Graph& g,
 250                                                   PlanarEmbedding embedding,
 251                                                   ForwardIterator ord_begin,
 252                                                   ForwardIterator ord_end,
 253                                                   GridPositionMap drawing
 254                                                   )
 255   {
 256     chrobak_payne_straight_line_drawing(g,
 257                                         embedding,
 258                                         ord_begin,
 259                                         ord_end,
 260                                         drawing,
 261                                         get(vertex_index,g)
 262                                         );
 263   }
 264
 265
 266
 267
 268 } // namespace boost
 269
 270 #endif //__CHROBAK_PAYNE_DRAWING_HPP__