203 lines
6.8 KiB
HTML
203 lines
6.8 KiB
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<typename Graph, typename PlanarEmbedding, typename PlanarFaceVisitor, typename EdgeIndexMap>
|
|
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 <typename Vertex> 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& 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 © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
|
|
aaron.windsor@gmail.com</a>)
|
|
</BODY>
|
|
</HTML>
|