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