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