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

<html><head><!-- 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)
    
  -->
<title>Planar Embedding Concept</title>
</head>
<body alink="#ff0000" 
      bgcolor="#ffffff" 
      link="#0000ee" 
      text="#000000" 
      vlink="#551a8b"> 
<img src="../../../boost.png" alt="C++ Boost" height="86" width="277"> 

<br clear="">

<h1>Planar Embedding Concept</h1>


A planar embedding is an important intermediate representation of a drawing
of a planar graph. Instead of specifying the absolute positions of the vertices
and edges in the plane, a planar embedding specifies their positions relative 
to one another. A planar embedding consists of a sequence, for each vertex in 
the graph, of all of the edges incident on that vertex in the order in which 
they are to be drawn around that vertex.
<p>
A planar embedding is a refinement of 
<a href="../../property_map/doc/LvaluePropertyMap.html">LValuePropertyMap</a> that
places additional restrictions the <tt>value_type</tt> used in the property
map.

</p><h3>Notation</h3>

<table>
<tbody>

<tr> 
<td> <tt>Embedding</tt> </td>  
<td> is a type that models the Planar Embedding concept.</td>
</tr>

<tr> 
<td> <tt>embedding</tt> </td>
<td> is an object of type <tt>Embedding</tt>. </td>
</tr>

<tr> 
<td> <tt>Graph</tt> </td>  
<td> is the type of the underlying graph.</td>
</tr>

<tr> 
<td> <tt>e</tt> </td>  
<td> is an object of type <tt>graph_traits&lt;Graph&gt;::edge_descriptor</tt>. 
</td>
</tr>

<tr>
<td> <tt>v</tt> </td>
<td> is an object of type <tt>graph_traits&lt;Graph&gt;::vertex_descriptor
</tt>.</td>

</tr><tr>
<td> 

</td></tr></tbody></table>


<h3>Associated Types</h3>

<table border="1">

<tbody><tr> 
<td> Const Iterator  </td>
<td> <tt>boost::property_traits&lt;Embedding&gt;::value_type::const_iterator
</tt>
</td>
<td> The iterator type used to iterate over the ordering of the edges in the 
planar embedding of a particular vertex
</td>
</tr>

</tbody></table>

<h3>Valid Expressions</h3>

<p>

<table border="1">

<tbody><tr><th>Expression</th><th>Return Type</th><th>Description</th>

</tr><tr> 
<td> <tt>embedding[v].begin()</tt>  </td>
<td> <tt>boost::property_traits&lt;Embedding&gt;::value_type::const_iterator
     </tt></td>
<td> Returns an iterator to the beginning of the range of edges in the 
     embedding around vertex v</td>
</tr>

<tr> 
<td> <tt>embedding[v].end()</tt>  </td>
<td> <tt>boost::property_traits&lt;Embedding&gt;::value_type::const_iterator
     </tt></td>
<td> Returns an iterator to the end of the range of edges in the 
     embedding around vertex v</td>
</tr>

<tr> 
<td> <tt>embedding[v].clear()</tt>  </td>
<td> <tt>void</tt></td>
<td> Clears all edges in the embedding around a vertex <tt>v</tt></td>
</tr>

<tr> 
<td> <tt>embedding[v].push_back(e)</tt>  </td>
<td> <tt>void</tt></td>
<td> Adds an edge <tt>e</tt> to the end of the sequence of embedded edges 
     around the vertex <tt>v</tt> </td>
</tr>

</tbody></table>

</p><h3>Complexity Guarantees</h3>

Starting with an empty embedding, any mixed sequence of <i>n</i> calls to a
particular vertex's <tt>push_back</tt> and <tt>clear</tt> should take 
<i>O(n)</i> time.

<h3>Models</h3>

Any LValue property map that maps vertices to a <tt>std::vector</tt>, 
<tt>std::list</tt>, or <tt>std::deque</tt> models this
concept. Below is an example of using this approach to create a model of
PlanarEmbedding:

<pre>
#include &lt;boost/property_map/property_map.hpp&gt;
#include &lt;vector&gt;

...

// Assume a graph type "Graph" defined somewhere above and
// an instance of Graph in a variable g.

// A typedef for the storage - a vector of vectors of edge descriptors
typedef 
    std::vector&lt; std::vector&lt; graph_traits&lt;Graph&gt;::edge_descriptor &gt; &gt;
    planar_embedding_storage_t;

// A typedef for the iterator property map, assuming the graph has
// an interior vertex index map
typedef
    boost::iterator_property_map&lt; planar_embedding_storage_t::iterator,
                                  property_map&lt;Graph, vertex_index_t&gt;::type
                                &gt;
    planar_embedding_t;

// Create an instance of the storage and the property map
planar_embedding_storage_t planar_embedding_storage(num_vertices(g));
planar_embedding_t planar_embedding(planar_embedding_storage.begin(),
                                    get(vertex_index, g)
                                    );

// planar_embedding can now be passed to any function expecting a model
// of PlanarEmbedding.
</pre>

<p>

<br>
</p><hr>
Commit	Line	Data
7c673cae FG	1	<html><head><!-- Copyright 2007 Aaron Windsor
	2
	3	Distributed under the Boost Software License, Version 1.0.
	4	(See accompanying file LICENSE_1_0.txt or copy at
	5	http://www.boost.org/LICENSE_1_0.txt)
	6
	7	-->
	8	<title>Planar Embedding Concept</title>
	9	</head>
	10	<body alink="#ff0000"
	11	bgcolor="#ffffff"
	12	link="#0000ee"
	13	text="#000000"
	14	vlink="#551a8b">
	15	<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
	16
	17	<br clear="">
	18
	19	<h1>Planar Embedding Concept</h1>
	20
	21
	22	A planar embedding is an important intermediate representation of a drawing
	23	of a planar graph. Instead of specifying the absolute positions of the vertices
	24	and edges in the plane, a planar embedding specifies their positions relative
	25	to one another. A planar embedding consists of a sequence, for each vertex in
	26	the graph, of all of the edges incident on that vertex in the order in which
	27	they are to be drawn around that vertex.
	28	<p>
	29	A planar embedding is a refinement of
	30	<a href="../../property_map/doc/LvaluePropertyMap.html">LValuePropertyMap</a> that
	31	places additional restrictions the <tt>value_type</tt> used in the property
	32	map.
	33
	34	</p><h3>Notation</h3>
	35
	36	<table>
	37	<tbody>
	38
	39	<tr>
	40	<td> <tt>Embedding</tt> </td>
	41	<td> is a type that models the Planar Embedding concept.</td>
	42	</tr>
	43
	44	<tr>
	45	<td> <tt>embedding</tt> </td>
	46	<td> is an object of type <tt>Embedding</tt>. </td>
	47	</tr>
	48
	49	<tr>
	50	<td> <tt>Graph</tt> </td>
	51	<td> is the type of the underlying graph.</td>
	52	</tr>
	53
	54	<tr>
	55	<td> <tt>e</tt> </td>
	56	<td> is an object of type <tt>graph_traits<Graph>::edge_descriptor</tt>.
	57	</td>
	58	</tr>
	59
	60	<tr>
	61	<td> <tt>v</tt> </td>
	62	<td> is an object of type <tt>graph_traits<Graph>::vertex_descriptor
	63	</tt>.</td>
	64
65	</tr><tr>
66	<td>
67
68	</td></tr></tbody></table>
69
70
71	<h3>Associated Types</h3>
72
73	<table border="1">
74
75	<tbody><tr>
76	<td> Const Iterator </td>
77	<td> <tt>boost::property_traits<Embedding>::value_type::const_iterator
78	</tt>
79	</td>
80	<td> The iterator type used to iterate over the ordering of the edges in the
81	planar embedding of a particular vertex
82	</td>
83	</tr>
84
85	</tbody></table>
86
87	<h3>Valid Expressions</h3>
88
89	<p>
90
91	<table border="1">
92
93	<tbody><tr><th>Expression</th><th>Return Type</th><th>Description</th>
94
95	</tr><tr>
96	<td> <tt>embedding[v].begin()</tt> </td>
97	<td> <tt>boost::property_traits<Embedding>::value_type::const_iterator
98	</tt></td>
99	<td> Returns an iterator to the beginning of the range of edges in the
100	embedding around vertex v</td>
101	</tr>
102
103	<tr>
104	<td> <tt>embedding[v].end()</tt> </td>
105	<td> <tt>boost::property_traits<Embedding>::value_type::const_iterator
106	</tt></td>
107	<td> Returns an iterator to the end of the range of edges in the
108	embedding around vertex v</td>
109	</tr>
110
111	<tr>
112	<td> <tt>embedding[v].clear()</tt> </td>
113	<td> <tt>void</tt></td>
114	<td> Clears all edges in the embedding around a vertex <tt>v</tt></td>
115	</tr>
116
117	<tr>
118	<td> <tt>embedding[v].push_back(e)</tt> </td>
119	<td> <tt>void</tt></td>
120	<td> Adds an edge <tt>e</tt> to the end of the sequence of embedded edges
121	around the vertex <tt>v</tt> </td>
122	</tr>
123
124	</tbody></table>
125
126	</p><h3>Complexity Guarantees</h3>
127
128	Starting with an empty embedding, any mixed sequence of <i>n</i> calls to a
129	particular vertex's <tt>push_back</tt> and <tt>clear</tt> should take
130	<i>O(n)</i> time.
131
132	<h3>Models</h3>
133
134	Any LValue property map that maps vertices to a <tt>std::vector</tt>,
135	<tt>std::list</tt>, or <tt>std::deque</tt> models this
136	concept. Below is an example of using this approach to create a model of
137	PlanarEmbedding:
138
139	<pre>
140	#include <boost/property_map/property_map.hpp>
141	#include <vector>
142
143	...
144
145	// Assume a graph type "Graph" defined somewhere above and
146	// an instance of Graph in a variable g.
147
148	// A typedef for the storage - a vector of vectors of edge descriptors
149	typedef
150	std::vector< std::vector< graph_traits<Graph>::edge_descriptor > >
151	planar_embedding_storage_t;
152
153	// A typedef for the iterator property map, assuming the graph has
154	// an interior vertex index map
155	typedef
156	boost::iterator_property_map< planar_embedding_storage_t::iterator,
157	property_map<Graph, vertex_index_t>::type
158	>
159	planar_embedding_t;
160
161	// Create an instance of the storage and the property map
162	planar_embedding_storage_t planar_embedding_storage(num_vertices(g));
163	planar_embedding_t planar_embedding(planar_embedding_storage.begin(),
164	get(vertex_index, g)
165	);
166
167	// planar_embedding can now be passed to any function expecting a model
168	// of PlanarEmbedding.
169	</pre>
170
171	<p>
172
173	<br>
174	</p><hr>
175