[ceph.git] / ceph / src / boost / libs / graph / doc / straight_line_drawing.html

<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&lt;typename Graph, 
         typename PlanarEmbedding, 
         typename ForwardIterator, 
         typename PositionMap,
         typename VertexIndexMap&gt;
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&amp; 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/doc/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&lt;Graph&gt;::vertex_descriptor</tt>.
</blockquote>

OUT: <tt>PositionMap</tt> 

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