ceph/src/boost/libs/graph/doc/make_biconnected_planar.html

   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>
  23 template &lt;typename Graph, typename PlanarEmbedding, typename EdgeIndexMap, typename AddEdgeVisitor&gt;
  24 void make_biconnected_planar(Graph& g, PlanarEmbedding embedding, EdgeIndexMap em, AddEdgeVisitor& vis);
  25 </pre>
  26
  27 <p>
  28
  29 A 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>.
  31 Alternatively, a graph is biconnected if it is connected and cannot be made
  32 disconnected by removing any single vertex. <tt>make_biconnected_planar</tt>
  33 takes 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
  35 or more edges to make <tt>g</tt> biconnected while preserving planarity.
  36 <p>
  37 The default behavior of <tt>make_biconnected_planar</tt> is to modify the
  38 graph <tt>g</tt> by calling <tt>add_edge(u,v,g)</tt> for every pair of
  39 vertices <i>(u,v)</i> where an edge needs to be added to make <tt>g</tt>
  40 biconnected. 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
  43 following signature:
  44 <pre>
  45 template &lt;typename Graph, typename Vertex&gt;
  46 void visit_vertex_pair(Vertex u, Vertex v, Graph& g);
  47 </pre>
  48 This event point can also be used as a hook to update the underlying edge
  49 index map automatically as edges are added. See the
  50 documentation for the <a href="./AddEdgeVisitor.html">AddEdgeVisitor</a>
  51 concept 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
  62 IN/OUT: <tt>Graph&amp; g</tt>
  63
  64 <blockquote>
  65 An undirected graph. The graph type must be a model of <a
  66 href="VertexListGraph.html">Vertex List Graph</a>, <a
  67 href="IncidenceGraph.html">Incidence Graph</a>, and
  68 a <a href="MutableGraph.html">Mutable Graph</a><br>
  69 </blockquote>
  70
  71 IN: <tt>PlanarEmbedding embedding</tt>
  72
  73 <blockquote>
  74 A model of <a href="PlanarEmbedding.html">PlanarEmbedding</a>.
  75 </blockquote>
  76
  77 IN: <tt>EdgeIndexMap vm</tt>
  78
  79 <blockquote>
  80 A <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
  86 IN: <tt>AddEdgeVisitor</tt>
  87
  88 <blockquote>
  89 A 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
  98 On a planar graph with <i>n</i> vertices, <tt>make_biconnected_planar</tt>
  99 runs 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>
 114 Copyright &copy; 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
 115 aaron.windsor@gmail.com</a>)
 116 </BODY>
 117 </HTML>