//======================================================================= | |
// 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 <boost/config.hpp> | |
#include <boost/utility.hpp> //for next and prior | |
#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) | |
{ | |
if (v != graph_traits<Graph>::null_vertex()) | |
{ | |
x[v] += delta_x[v] + offset; | |
accumulate_offsets(left[v], x[v], g, x, delta_x, left, right); | |
accumulate_offsets(right[v], x[v], g, x, delta_x, left, right); | |
} | |
} | |
} /*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>::edge_descriptor edge_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(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__ |