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 __CHROBAK_PAYNE_DRAWING_HPP__
Chris@16: #define __CHROBAK_PAYNE_DRAWING_HPP__
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <list>
Chris@16: #include <stack>
Chris@16: #include <boost/config.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:   namespace graph { namespace detail
Chris@16:   {
Chris@16: 
Chris@16:     template<typename Graph, 
Chris@16:              typename VertexToVertexMap, 
Chris@16:              typename VertexTo1DCoordMap>
Chris@16:     void accumulate_offsets(typename graph_traits<Graph>::vertex_descriptor v,
Chris@16:                             std::size_t offset,
Chris@16:                             const Graph& g,
Chris@16:                             VertexTo1DCoordMap x,
Chris@16:                             VertexTo1DCoordMap delta_x,
Chris@16:                             VertexToVertexMap left,
Chris@16:                             VertexToVertexMap right)
Chris@16:     {
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:       // Suggestion of explicit stack from Aaron Windsor to avoid system stack
Chris@16:       // overflows.
Chris@16:       typedef std::pair<vertex_descriptor, std::size_t> stack_entry;
Chris@16:       std::stack<stack_entry> st;
Chris@16:       st.push(stack_entry(v, offset));
Chris@16:       while (!st.empty()) {
Chris@16:         vertex_descriptor v = st.top().first;
Chris@16:         std::size_t offset = st.top().second;
Chris@16:         st.pop();
Chris@16:         if (v != graph_traits<Graph>::null_vertex()) {
Chris@16:           x[v] += delta_x[v] + offset;
Chris@16:           st.push(stack_entry(left[v], x[v]));
Chris@16:           st.push(stack_entry(right[v], x[v]));
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:   } /*namespace detail*/ } /*namespace graph*/
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template<typename Graph, 
Chris@16:            typename PlanarEmbedding, 
Chris@16:            typename ForwardIterator, 
Chris@16:            typename GridPositionMap,
Chris@16:            typename VertexIndexMap>
Chris@16:   void chrobak_payne_straight_line_drawing(const Graph& g, 
Chris@16:                                            PlanarEmbedding embedding, 
Chris@16:                                            ForwardIterator ordering_begin,
Chris@16:                                            ForwardIterator ordering_end,
Chris@16:                                            GridPositionMap drawing,
Chris@16:                                            VertexIndexMap vm
Chris@16:                                            )
Chris@16:   {
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
Chris@16:     typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
Chris@16:     typedef typename PlanarEmbedding::value_type::const_iterator 
Chris@16:       edge_permutation_iterator_t;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
Chris@16:     typedef std::vector<vertex_t> vertex_vector_t;
Chris@16:     typedef std::vector<v_size_t> vsize_vector_t;
Chris@16:     typedef std::vector<bool> bool_vector_t;
Chris@16:     typedef boost::iterator_property_map
Chris@16:       <typename vertex_vector_t::iterator, VertexIndexMap> 
Chris@16:       vertex_to_vertex_map_t;
Chris@16:     typedef boost::iterator_property_map
Chris@16:       <typename vsize_vector_t::iterator, VertexIndexMap> 
Chris@16:       vertex_to_vsize_map_t;
Chris@16:     typedef boost::iterator_property_map
Chris@16:       <typename bool_vector_t::iterator, VertexIndexMap> 
Chris@16:       vertex_to_bool_map_t;
Chris@16: 
Chris@16:     vertex_vector_t left_vector(num_vertices(g), 
Chris@16:                                 graph_traits<Graph>::null_vertex()
Chris@16:                                 );
Chris@16:     vertex_vector_t right_vector(num_vertices(g), 
Chris@16:                                  graph_traits<Graph>::null_vertex()
Chris@16:                                  );
Chris@16:     vsize_vector_t seen_as_right_vector(num_vertices(g), 0);
Chris@16:     vsize_vector_t seen_vector(num_vertices(g), 0);
Chris@16:     vsize_vector_t delta_x_vector(num_vertices(g),0);
Chris@16:     vsize_vector_t y_vector(num_vertices(g));
Chris@16:     vsize_vector_t x_vector(num_vertices(g),0);
Chris@16:     bool_vector_t installed_vector(num_vertices(g),false);
Chris@16: 
Chris@16:     vertex_to_vertex_map_t left(left_vector.begin(), vm);
Chris@16:     vertex_to_vertex_map_t right(right_vector.begin(), vm);
Chris@16:     vertex_to_vsize_map_t seen_as_right(seen_as_right_vector.begin(), vm);
Chris@16:     vertex_to_vsize_map_t seen(seen_vector.begin(), vm);
Chris@16:     vertex_to_vsize_map_t delta_x(delta_x_vector.begin(), vm);
Chris@16:     vertex_to_vsize_map_t y(y_vector.begin(), vm);
Chris@16:     vertex_to_vsize_map_t x(x_vector.begin(), vm);
Chris@16:     vertex_to_bool_map_t installed(installed_vector.begin(), vm);
Chris@16: 
Chris@16:     v_size_t timestamp = 1;
Chris@16:     vertex_vector_t installed_neighbors;
Chris@16: 
Chris@16:     ForwardIterator itr = ordering_begin;
Chris@16:     vertex_t v1 = *itr; ++itr;
Chris@16:     vertex_t v2 = *itr; ++itr;
Chris@16:     vertex_t v3 = *itr; ++itr;
Chris@16: 
Chris@16:     delta_x[v2] = 1; 
Chris@16:     delta_x[v3] = 1;
Chris@16:     
Chris@16:     y[v1] = 0;
Chris@16:     y[v2] = 0;
Chris@16:     y[v3] = 1;
Chris@16: 
Chris@16:     right[v1] = v3;
Chris@16:     right[v3] = v2;
Chris@16: 
Chris@16:     installed[v1] = installed[v2] = installed[v3] = true;
Chris@16: 
Chris@16:     for(ForwardIterator itr_end = ordering_end; itr != itr_end; ++itr)
Chris@16:       {
Chris@16:         vertex_t v = *itr;
Chris@16: 
Chris@16:         // First, find the leftmost and rightmost neighbor of v on the outer 
Chris@16:         // cycle of the embedding. 
Chris@16:         // Note: since we're moving clockwise through the edges adjacent to v, 
Chris@16:         // we're actually moving from right to left among v's neighbors on the
Chris@16:         // outer face (since v will be installed above them all) looking for 
Chris@16:         // the leftmost and rightmost installed neigbhors
Chris@16: 
Chris@16:         vertex_t leftmost = graph_traits<Graph>::null_vertex();
Chris@16:         vertex_t rightmost = graph_traits<Graph>::null_vertex();
Chris@16: 
Chris@16:         installed_neighbors.clear();
Chris@16: 
Chris@16:         vertex_t prev_vertex = graph_traits<Graph>::null_vertex();
Chris@16:         edge_permutation_iterator_t pi, pi_end;
Chris@16:         pi_end = embedding[v].end();
Chris@16:         for(pi = embedding[v].begin(); pi != pi_end; ++pi)
Chris@16:           {
Chris@16:             vertex_t curr_vertex = source(*pi,g) == v ? 
Chris@16:               target(*pi,g) : source(*pi,g);
Chris@16:             
Chris@16:             // Skip any self-loops or parallel edges
Chris@16:             if (curr_vertex == v || curr_vertex == prev_vertex)
Chris@16:                 continue;
Chris@16: 
Chris@16:             if (installed[curr_vertex])
Chris@16:               {
Chris@16:                 seen[curr_vertex] = timestamp;
Chris@16: 
Chris@16:                 if (right[curr_vertex] != graph_traits<Graph>::null_vertex())
Chris@16:                   {
Chris@16:                     seen_as_right[right[curr_vertex]] = timestamp;
Chris@16:                   }
Chris@16:                 installed_neighbors.push_back(curr_vertex);
Chris@16:               }
Chris@16: 
Chris@16:             prev_vertex = curr_vertex;
Chris@16:           }
Chris@16: 
Chris@16:         typename vertex_vector_t::iterator vi, vi_end;
Chris@16:         vi_end = installed_neighbors.end();
Chris@16:         for(vi = installed_neighbors.begin(); vi != vi_end; ++vi)
Chris@16:           {
Chris@16:             if (right[*vi] == graph_traits<Graph>::null_vertex() || 
Chris@16:                 seen[right[*vi]] != timestamp
Chris@16:                 )
Chris@16:               rightmost = *vi;
Chris@16:             if (seen_as_right[*vi] != timestamp)
Chris@16:               leftmost = *vi;
Chris@16:           }
Chris@16: 
Chris@16:         ++timestamp;
Chris@16: 
Chris@16:         //stretch gaps
Chris@16:         ++delta_x[right[leftmost]];
Chris@16:         ++delta_x[rightmost];
Chris@16: 
Chris@16:         //adjust offsets
Chris@16:         std::size_t delta_p_q = 0;
Chris@16:         vertex_t stopping_vertex = right[rightmost];
Chris@16:         for(vertex_t temp = right[leftmost]; temp != stopping_vertex; 
Chris@16:             temp = right[temp]
Chris@16:             )
Chris@16:           {
Chris@16:             delta_p_q += delta_x[temp];
Chris@16:           }
Chris@16: 
Chris@16:         delta_x[v] = ((y[rightmost] + delta_p_q) - y[leftmost])/2;
Chris@16:         y[v] = y[leftmost] + delta_x[v];
Chris@16:         delta_x[rightmost] = delta_p_q - delta_x[v];
Chris@16:         
Chris@16:         bool leftmost_and_rightmost_adjacent = right[leftmost] == rightmost;
Chris@16:         if (!leftmost_and_rightmost_adjacent)
Chris@16:           delta_x[right[leftmost]] -= delta_x[v];
Chris@16: 
Chris@16:         //install v
Chris@16:         if (!leftmost_and_rightmost_adjacent)
Chris@16:           {
Chris@16:             left[v] = right[leftmost];
Chris@16:             vertex_t next_to_rightmost;
Chris@16:             for(vertex_t temp = leftmost; temp != rightmost; 
Chris@16:                 temp = right[temp]
Chris@16:                 )
Chris@16:               {
Chris@16:                 next_to_rightmost = temp;
Chris@16:               }
Chris@16: 
Chris@16:             right[next_to_rightmost] = graph_traits<Graph>::null_vertex();
Chris@16:           }
Chris@16:         else
Chris@16:           {
Chris@16:             left[v] = graph_traits<Graph>::null_vertex();
Chris@16:           }
Chris@16: 
Chris@16:         right[leftmost] = v;
Chris@16:         right[v] = rightmost;
Chris@16:         installed[v] = true;
Chris@16: 
Chris@16:       }
Chris@16: 
Chris@16:     graph::detail::accumulate_offsets
Chris@16:       (*ordering_begin,0,g,x,delta_x,left,right);
Chris@16: 
Chris@16:     vertex_iterator_t vi, vi_end;
Chris@16:     for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
Chris@16:       {
Chris@16:         vertex_t v(*vi);
Chris@16:         drawing[v].x = x[v];
Chris@16:         drawing[v].y = y[v];
Chris@16:       }
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template<typename Graph, 
Chris@16:            typename PlanarEmbedding, 
Chris@16:            typename ForwardIterator, 
Chris@16:            typename GridPositionMap>
Chris@16:   inline void chrobak_payne_straight_line_drawing(const Graph& g, 
Chris@16:                                                   PlanarEmbedding embedding, 
Chris@16:                                                   ForwardIterator ord_begin,
Chris@16:                                                   ForwardIterator ord_end,
Chris@16:                                                   GridPositionMap drawing
Chris@16:                                                   )
Chris@16:   {
Chris@16:     chrobak_payne_straight_line_drawing(g, 
Chris@16:                                         embedding, 
Chris@16:                                         ord_begin, 
Chris@16:                                         ord_end, 
Chris@16:                                         drawing, 
Chris@16:                                         get(vertex_index,g)
Chris@16:                                         );
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif //__CHROBAK_PAYNE_DRAWING_HPP__