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: make_biconnected_planar</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><tt>make_biconnected_planar</tt></H1> 19 20<p> 21 22<pre> 23template <typename Graph, typename PlanarEmbedding, typename EdgeIndexMap, typename AddEdgeVisitor> 24void make_biconnected_planar(Graph& g, PlanarEmbedding embedding, EdgeIndexMap em, AddEdgeVisitor& vis); 25</pre> 26 27<p> 28 29A graph <i>G</i> is biconnected if, for every pair of vertices <i>u,v</i> in 30<i>G</i>, there is a cycle containing both <i>u</i> and <i>v</i>. 31Alternatively, a graph is biconnected if it is connected and cannot be made 32disconnected by removing any single vertex. <tt>make_biconnected_planar</tt> 33takes a <a href="./make_connected.html">connected</a> 34<a href="planar_graphs.html">planar</a> graph <tt>g</tt> as input and adds zero 35or more edges to make <tt>g</tt> biconnected while preserving planarity. 36<p> 37The default behavior of <tt>make_biconnected_planar</tt> is to modify the 38graph <tt>g</tt> by calling <tt>add_edge(u,v,g)</tt> for every pair of 39vertices <i>(u,v)</i> where an edge needs to be added to make <tt>g</tt> 40biconnected. This behavior can be overriden by providing a vistor as the 41<tt>AddEdgeVisitor</tt> parameter. The only requirement for an 42<tt>AddEdgeVisitor</tt> is that it define a member function with the 43following signature: 44<pre> 45template <typename Graph, typename Vertex> 46void visit_vertex_pair(Vertex u, Vertex v, Graph& g); 47</pre> 48This event point can also be used as a hook to update the underlying edge 49index map automatically as edges are added. See the 50documentation for the <a href="./AddEdgeVisitor.html">AddEdgeVisitor</a> 51concept for more information. 52 53<H3>Where Defined</H3> 54 55<P> 56<a href="../../../boost/graph/make_biconnected_planar.hpp"> 57<TT>boost/graph/make_biconnected_planar.hpp</TT> 58</a> 59 60<h3>Parameters</h3> 61 62IN/OUT: <tt>Graph& g</tt> 63 64<blockquote> 65An undirected graph. The graph type must be a model of <a 66href="VertexListGraph.html">Vertex List Graph</a>, <a 67href="IncidenceGraph.html">Incidence Graph</a>, and 68a <a href="MutableGraph.html">Mutable Graph</a><br> 69</blockquote> 70 71IN: <tt>PlanarEmbedding embedding</tt> 72 73<blockquote> 74A model of <a href="PlanarEmbedding.html">PlanarEmbedding</a>. 75</blockquote> 76 77IN: <tt>EdgeIndexMap vm</tt> 78 79<blockquote> 80A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map 81</a> that maps edges from <tt>g</tt> to distinct integers in the range 82<tt>[0, num_edges(g) )</tt><br> 83<b>Default</b>: <tt>get(edge_index,g)</tt><br> 84</blockquote> 85 86IN: <tt>AddEdgeVisitor</tt> 87 88<blockquote> 89A model of <a href="AddEdgeVisitor.html">AddEdgeVisitor 90</a>.<br> 91<b>Default</b>: <tt>default_add_edge_visitor</tt>, a class defines 92<tt>visit_vertex_pair</tt> to dispatch its calls to <tt>add_edge</tt>. 93</blockquote> 94 95 96<h3>Complexity</h3> 97 98On a planar graph with <i>n</i> vertices, <tt>make_biconnected_planar</tt> 99runs in time <i>O(n)</i> 100 101<H3>Example</H3> 102 103<P> 104<a href="../example/make_biconnected_planar.cpp"> 105<TT>examples/make_biconnected_planar.cpp</TT> 106</a> 107 108<h3>See Also</h3> 109 110<a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a> 111 112<br> 113<HR> 114Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> 115aaron.windsor@gmail.com</a>) 116</BODY> 117</HTML> 118
