1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
<HTML>
<!-- Copyright 2007 Aaron Windsor
--
-- 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)
--
-->
<Head>
<Title>Boost Graph Library: Chrobak-Payne Straight Line Drawing</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../boost.png"
ALT="C++ Boost" width="277" height="86">
<BR Clear>
<H1>Chrobak-Payne Straight Line Drawing</H1>
<p>
<pre>
template<typename Graph,
typename PlanarEmbedding,
typename ForwardIterator,
typename PositionMap,
typename VertexIndexMap>
void chrobak_payne_straight_line_drawing(const Graph& g,
PlanarEmbedding perm,
ForwardIterator ordering_begin,
ForwardIterator ordering_end,
PositionMap drawing,
VertexIndexMap vm
);
</pre>
<br>
<p>
A <i>straight line drawing</i> of a <a href="./planar_graphs.html#planar">
planar graph</a> is a <a href="./planar_graphs.html#plane_drawing">plane
drawing</a> where each edge is drawn using a straight line segment. Since all
edges are line segments, the drawing is completely determined by the placement
of vertices in the plane. <tt>chrobak_payne_straight_line_drawing</tt> uses an
algorithm of Chrobak and Payne
[<a href = "./bibliography.html#chrobakpayne95">71</a>]
to form a straight
line drawing of a planar graph by mapping all <i>n</i> vertices in a planar
graph to integer coordinates in a <i>(2n - 4) x (n - 2)</i> grid.
<center>
<img src="./figs/straight_line_drawing.png">
</center>
<p>
The input graph passed to <tt>chrobak_payne_straight_line_drawing</tt> must
be a <a href="make_maximal_planar.html">maximal planar graph</a> with at least
3 vertices. Self-loops and parallel edges are ignored by this function. Note
that the restriction that the graph be maximal planar does not
mean that this function can only draw maximal planar graphs (the graph pictured
above is not maximal planar, for example). If you want to
draw a graph <i>g</i>, you can create a copy <i>g'</i> of <i>g</i>, store a
mapping <i>m</i> of vertices in <i>g'</i> to vertices in <i>g</i>,
<a href="make_maximal_planar.html">triangulate</a> <i>g'</i>, and then send
<i>g'</i> in as the input to <tt>chrobak_payne_straight_line_drawing</tt>. The
drawing returned can then be applied to <i>g</i> using <i>m</i> to translate
vertices from one graph to another, since <i>g</i> contains a subset of the
edges in <i>g'</i>.
<h3>Complexity</h3>
If the vertex index map provides constant-time access to indices, this
function takes time <i>O(n + m)</i> for a planar graph with <i>n</i> vertices
and <i>m</i> edges. Note that
in a simple planar graph with <i>f</i> faces, <i>m</i> edges, and <i>n</i>
vertices, both <i>f</i> and <i>m</i> are <i>O(n)</i>.
<H3>Where Defined</H3>
<P>
<a href="../../../boost/graph/chrobak_payne_drawing.hpp">
<TT>boost/graph/chrobak_payne_drawing.hpp</TT>
</a>
<h3>Parameters</h3>
IN: <tt>Graph& g</tt>
<blockquote>
An undirected graph. The graph type must be a model of <a
href="VertexListGraph.html">Vertex List Graph</a>
</blockquote>
IN <tt>PlanarEmbedding embedding</tt>
<blockquote>
A <a href="../../property_map/ReadablePropertyMap.html">Readable Property Map
</a> that models the <a href="PlanarEmbedding.html">PlanarEmbedding</a>
concept.
</blockquote>
IN <tt>ForwardIterator</tt>
<blockquote>
A ForwardIterator that has <tt>value_type</tt> equal to
<tt>graph_traits<Graph>::vertex_descriptor</tt>.
</blockquote>
OUT: <tt>PositionMap</tt>
<blockquote>
A <a href="../../property_map/LvaluePropertyMap.html">Writable LValue Property
Map</a> that models the Position Map concept. The Position Map concept requires
that the value mapped to be an object that has members <tt>x</tt> and
<tt>y</tt>. For example, if <tt>p</tt> models PositionMap and <tt>v</tt>
is a vertex in the graph, <tt>p[v].x</tt> and <tt>p[v].y</tt> are valid
expressions. The type of <tt>x</tt> and <tt>y</tt> must be implicitly
convertable to <tt>std::size_t</tt>.
</blockquote>
IN: <tt>VertexIndexMap vm</tt>
<blockquote>
A <a href="../../property_map/ReadablePropertyMap.html">Readable Property Map
</a> that maps vertices from <tt>g</tt> to distinct integers in the range
<tt>[0, num_vertices(g) )</tt><br>
<b>Default</b>: <tt>get(vertex_index,g)</tt><br>
</blockquote>
<H3>Example</H3>
<P>
<a href="../example/straight_line_drawing.cpp">
<TT>examples/straight_line_drawing.cpp</TT>
</a>
<h3>See Also</h3>
<p>
<ul>
<li> <a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a>
<li> <a href="is_straight_line_drawing.html"><tt>is_straight_line_drawing</tt>
</a>
</ul>
<br>
<HR>
Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
aaron.windsor@gmail.com</a>)
</BODY>
</HTML>
|
