[ceph.git] / ceph / src / boost / libs / graph / doc / planar_face_traversal.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: Planar Face Traversal</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>Planar Face Traversal</H1>

<pre>
template&lt;typename Graph, typename PlanarEmbedding, typename PlanarFaceVisitor, typename EdgeIndexMap&gt;
void planar_face_traversal(const Graph& g, PlanarEmbedding embedding, PlanarFaceVisitor& visitor, EdgeIndexMap em);
</pre>

<p>
A graph is <i>planar</i> if it can be drawn in two-dimensional space with no 
two of its edges crossing. Any embedding of a planar graph separates the plane 
into distinct regions that are bounded by sequences of edges in the graph. 
These regions are called <i>faces</i>. 

<br>
<br>
<table align="center" class="image">
<caption align="bottom">
<h5>A plane drawing of a graph (left), and the 8 faces defined by the planar 
embedding (right.) Each connected blue region in the image on the right is a 
face. The large blue region surrounding the graph is the <i>outer face</i>.
</h5>
</caption>
<tr>
<td>
<img src="./figs/face_illustration.png">
</td>
</tr>
<tr></tr>
</table>
<br>


A traversal of the faces of a planar graph involves iterating through all faces
of the graph, and on each face, iterating through all vertices and edges of the
face. The iteration through all vertices and edges of each face follows a 
path around the border of the face.
<p>
In a biconnected graph, like the one shown above, each face is bounded by a 
cycle and each edge belongs to exactly two faces. For this reason, when 
<tt>planar_face_traversal</tt> is called on a biconnected graph, each edge will
be visited exactly twice: once on each of two distinct faces, and no vertex 
will be visited more than once on a particular face. The output of 
<tt>planar_face_traversal</tt> on non-biconnected graphs is less intuitive - 
for example, if the graph 
consists solely of a path of vertices (and therefore a single face), 
<tt>planar_face_traversal</tt> will iterate <i>around</i> the path, visiting 
each edge twice and visiting some vertices more than once. 
<tt>planar_face_traversal</tt> does not visit isolated vertices.
<p>
Like other graph traversal algorithms in the Boost Graph Library, the planar 
face traversal is a generic traversal that can be customized by the 
redefinition of certain visitor event points. By defining an appropriate
visitor, this traversal can be 
used to enumerate the faces of a planar graph, triangulate a planar graph, or 
even construct a dual of a planar graph. 

<br>
<center>
<img src="./figs/face_traversal_example.png">
</center>
<br>

For example, on the above graph, an instance <tt>my_visitor</tt> of the 
following visitor:
<pre>
    struct output_visitor: public planar_face_traversal_visitor
    {
        void begin_face() { std::cout << "New face: "; }
        template &lt;typename Vertex&gt; void next_vertex(Vertex v) { std::cout << v << " "; } 
        void finish_face() { std::cout << std::endl; }
    };
</pre>
can be passed to the <tt>planar_face_traversal</tt> function:
<pre>
    output_visitor my_visitor;
    planar_face_traversal(g, embed, my_visitor); //embed is a planar embedding of g
</pre>
and might produce the output
<pre>
    New face: 1 2 5 4
    New face: 2 3 4 5
    New face: 3 0 1 4
    New face: 1 0 3 2
</pre>

<h3>Visitor Event Points</h3> 
         
<ul>
<li><tt>visitor.begin_traversal()</tt>: called once before any faces are 
visited.
<li><tt>visitor.begin_face()</tt>: called once, for each face, before any 
vertex or edge on that face has been visited.
<li><tt>visitor.end_face()</tt>: called once, for each face, after all vertices
and all edges on that face have been visited.
<li><tt>visitor.next_vertex(Vertex v)</tt>: called once on each vertex in the 
current face (the start and end of which are designated by calls to 
<tt>begin_face()</tt> and <tt>end_face()</tt>, respectively) in order 
according to the order established by the planar embedding.
<li><tt>visitor.next_edge(Edge e)</tt>: called once on each edge in the current
face (the start and end of which are designated by calls to 
<tt>begin_face()</tt> and <tt>end_face()</tt>, respectively) in order 
according to the order established by the planar embedding.
<li><tt>visitor.end_traversal()</tt>: called once after all faces have been 
visited.
</ul>

Although <tt>next_vertex</tt> is guaranteed to be called in sequence for each
vertex as the traversal moves around a face and <tt>next_edge</tt> is
guaranteed to be called in sequence for each edge as the traversal moves
around a face, there's no guarantee about the order in which 
<tt>next_vertex</tt> and <tt>next_edge</tt> are called with respect to each 
other in between calls to <tt>begin_face</tt> and <tt>end_face</tt>. These 
calls may be interleaved, all vertex visits may precede all edge visits, or 
vise-versa.
<p>
<tt>planar_face_traversal</tt> iterates over a copy of the edges of the input 
graph, so it is safe to add edges to the graph during visitor event points.


<h3>Complexity</h3>

If all of the visitor event points run in constant time, the traversal 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/planar_face_traversal.hpp">
<TT>boost/graph/planar_face_traversal.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="VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>
</blockquote>

IN: <tt>PlanarEmbedding</tt> 

<blockquote>
A model of <a href="PlanarEmbedding.html">PlanarEmbedding</a>.
</blockquote>

IN: <tt>PlanarFaceVisitor</tt>

<blockquote>
A model of <a href="PlanarFaceVisitor.html">PlanarFaceVisitor</a>.
</blockquote>

IN: <tt>EdgeIndexMap vm</tt>

<blockquote>
A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
</a> that maps edges from <tt>g</tt> to distinct integers in the range 
<tt>[0, num_edges(g) )</tt><br>
<b>Default</b>: <tt>get(edge_index,g)</tt><br>
</blockquote>


<H3>Example</H3>

<P>
<a href="../example/planar_face_traversal.cpp">
<TT>examples/planar_face_traversal.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="./PlanarFaceVisitor.html">PlanarFaceVisitor</a> concept.
</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: Planar Face Traversal</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>Planar Face Traversal</H1>
	19
	20	<pre>
	21	template<typename Graph, typename PlanarEmbedding, typename PlanarFaceVisitor, typename EdgeIndexMap>
	22	void planar_face_traversal(const Graph& g, PlanarEmbedding embedding, PlanarFaceVisitor& visitor, EdgeIndexMap em);
	23	</pre>
	24
	25	<p>
	26	A graph is <i>planar</i> if it can be drawn in two-dimensional space with no
	27	two of its edges crossing. Any embedding of a planar graph separates the plane
	28	into distinct regions that are bounded by sequences of edges in the graph.
	29	These regions are called <i>faces</i>.
	30
	31	<br>
	32	<br>
	33	<table align="center" class="image">
	34	<caption align="bottom">
	35	<h5>A plane drawing of a graph (left), and the 8 faces defined by the planar
	36	embedding (right.) Each connected blue region in the image on the right is a
	37	face. The large blue region surrounding the graph is the <i>outer face</i>.
	38	</h5>
	39	</caption>
	40	<tr>
	41	<td>
	42	<img src="./figs/face_illustration.png">
	43	</td>
	44	</tr>
	45	<tr></tr>
	46	</table>
	47	<br>
	48
	49
	50	A traversal of the faces of a planar graph involves iterating through all faces
	51	of the graph, and on each face, iterating through all vertices and edges of the
	52	face. The iteration through all vertices and edges of each face follows a
	53	path around the border of the face.
	54	<p>
	55	In a biconnected graph, like the one shown above, each face is bounded by a
	56	cycle and each edge belongs to exactly two faces. For this reason, when
	57	<tt>planar_face_traversal</tt> is called on a biconnected graph, each edge will
	58	be visited exactly twice: once on each of two distinct faces, and no vertex
	59	will be visited more than once on a particular face. The output of
	60	<tt>planar_face_traversal</tt> on non-biconnected graphs is less intuitive -
	61	for example, if the graph
	62	consists solely of a path of vertices (and therefore a single face),
	63	<tt>planar_face_traversal</tt> will iterate <i>around</i> the path, visiting
	64	each edge twice and visiting some vertices more than once.
65	<tt>planar_face_traversal</tt> does not visit isolated vertices.
66	<p>
67	Like other graph traversal algorithms in the Boost Graph Library, the planar
68	face traversal is a generic traversal that can be customized by the
69	redefinition of certain visitor event points. By defining an appropriate
70	visitor, this traversal can be
71	used to enumerate the faces of a planar graph, triangulate a planar graph, or
72	even construct a dual of a planar graph.
73
74	<br>
75	<center>
76	<img src="./figs/face_traversal_example.png">
77	</center>
78	<br>
79
80	For example, on the above graph, an instance <tt>my_visitor</tt> of the
81	following visitor:
82	<pre>
83	struct output_visitor: public planar_face_traversal_visitor
84	{
85	void begin_face() { std::cout << "New face: "; }
86	template <typename Vertex> void next_vertex(Vertex v) { std::cout << v << " "; }
87	void finish_face() { std::cout << std::endl; }
88	};
89	</pre>
90	can be passed to the <tt>planar_face_traversal</tt> function:
91	<pre>
92	output_visitor my_visitor;
93	planar_face_traversal(g, embed, my_visitor); //embed is a planar embedding of g
94	</pre>
95	and might produce the output
96	<pre>
97	New face: 1 2 5 4
98	New face: 2 3 4 5
99	New face: 3 0 1 4
100	New face: 1 0 3 2
101	</pre>
102
103	<h3>Visitor Event Points</h3>
104
105	<ul>
106	<li><tt>visitor.begin_traversal()</tt>: called once before any faces are
107	visited.
108	<li><tt>visitor.begin_face()</tt>: called once, for each face, before any
109	vertex or edge on that face has been visited.
110	<li><tt>visitor.end_face()</tt>: called once, for each face, after all vertices
111	and all edges on that face have been visited.
112	<li><tt>visitor.next_vertex(Vertex v)</tt>: called once on each vertex in the
113	current face (the start and end of which are designated by calls to
114	<tt>begin_face()</tt> and <tt>end_face()</tt>, respectively) in order
115	according to the order established by the planar embedding.
116	<li><tt>visitor.next_edge(Edge e)</tt>: called once on each edge in the current
117	face (the start and end of which are designated by calls to
118	<tt>begin_face()</tt> and <tt>end_face()</tt>, respectively) in order
119	according to the order established by the planar embedding.
120	<li><tt>visitor.end_traversal()</tt>: called once after all faces have been
121	visited.
122	</ul>
123
124	Although <tt>next_vertex</tt> is guaranteed to be called in sequence for each
125	vertex as the traversal moves around a face and <tt>next_edge</tt> is
126	guaranteed to be called in sequence for each edge as the traversal moves
127	around a face, there's no guarantee about the order in which
128	<tt>next_vertex</tt> and <tt>next_edge</tt> are called with respect to each
129	other in between calls to <tt>begin_face</tt> and <tt>end_face</tt>. These
130	calls may be interleaved, all vertex visits may precede all edge visits, or
131	vise-versa.
132	<p>
133	<tt>planar_face_traversal</tt> iterates over a copy of the edges of the input
134	graph, so it is safe to add edges to the graph during visitor event points.
135
136
137	<h3>Complexity</h3>
138
139	If all of the visitor event points run in constant time, the traversal takes
140	time <i>O(n + m)</i> for a planar graph with <i>n</i> vertices and <i>m</i>
141	edges. Note that
142	in a simple planar graph with <i>f</i> faces, <i>m</i> edges, and <i>n</i>
143	vertices, both <i>f</i> and <i>m</i> are <i>O(n)</i>.
144
145	<H3>Where Defined</H3>
146
147	<P>
148	<a href="../../../boost/graph/planar_face_traversal.hpp">
149	<TT>boost/graph/planar_face_traversal.hpp</TT>
150	</a>
151
152	<h3>Parameters</h3>
153
154	IN: <tt>Graph& g</tt>
155
156	<blockquote>
157	An undirected graph. The graph type must
158	be a model of <a href="VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>
159	</blockquote>
160
161	IN: <tt>PlanarEmbedding</tt>
162
163	<blockquote>
164	A model of <a href="PlanarEmbedding.html">PlanarEmbedding</a>.
165	</blockquote>
166
167	IN: <tt>PlanarFaceVisitor</tt>
168
169	<blockquote>
170	A model of <a href="PlanarFaceVisitor.html">PlanarFaceVisitor</a>.
171	</blockquote>
172
173	IN: <tt>EdgeIndexMap vm</tt>
174
175	<blockquote>
176	A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
177	</a> that maps edges from <tt>g</tt> to distinct integers in the range
178	<tt>[0, num_edges(g) )</tt><br>
179	<b>Default</b>: <tt>get(edge_index,g)</tt><br>
180	</blockquote>
181
182
183	<H3>Example</H3>
184
185	<P>
186	<a href="../example/planar_face_traversal.cpp">
187	<TT>examples/planar_face_traversal.cpp</TT></a>
188
189	<h3>See Also</h3>
190
191	<p>
192	<ul>
193	<li><a href="./planar_graphs.html">Planar Graphs in the Boost Graph Library</a>
194	<li><a href="./PlanarFaceVisitor.html">PlanarFaceVisitor</a> concept.
195	</ul>
196
197	<br>
198	<HR>
199	Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
200	aaron.windsor@gmail.com</a>)
201	</BODY>
202	</HTML>