ceph/src/boost/libs/graph/doc/straight_line_drawing.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: Chrobak-Payne Straight Line Drawing</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>Chrobak-Payne Straight Line Drawing</H1>
  19
  20 <p>
  21 <pre>
  22 template&lt;typename Graph,
  23          typename PlanarEmbedding,
  24          typename ForwardIterator,
  25          typename PositionMap,
  26          typename VertexIndexMap&gt;
  27 void chrobak_payne_straight_line_drawing(const Graph& g,
  28                                          PlanarEmbedding perm,
  29                                          ForwardIterator ordering_begin,
  30                                          ForwardIterator ordering_end,
  31                                          PositionMap drawing,
  32                                          VertexIndexMap vm
  33                                          );
  34 </pre>
  35
  36 <br>
  37 <p>
  38 A <i>straight line drawing</i> of a <a href="./planar_graphs.html#planar">
  39 planar graph</a> is a <a href="./planar_graphs.html#plane_drawing">plane
  40 drawing</a> where each edge is drawn using a straight line segment. Since all
  41 edges are line segments, the drawing is completely determined by the placement
  42 of vertices in the plane. <tt>chrobak_payne_straight_line_drawing</tt> uses an
  43 algorithm of Chrobak and Payne
  44 [<a href = "./bibliography.html#chrobakpayne95">71</a>]
  45 to form a straight
  46 line drawing of a planar graph by mapping all <i>n</i> vertices in a planar
  47 graph to integer coordinates in a <i>(2n - 4) x (n - 2)</i> grid.
  48
  49 <center>
  50 <img src="./figs/straight_line_drawing.png">
  51 </center>
  52
  53 <p>
  54 The input graph passed to <tt>chrobak_payne_straight_line_drawing</tt> must
  55 be a <a href="make_maximal_planar.html">maximal planar graph</a> with at least
  56 3 vertices. Self-loops and parallel edges are ignored by this function. Note
  57 that the restriction that the graph be maximal planar does not
  58 mean that this function can only draw maximal planar graphs (the graph pictured
  59 above is not maximal planar, for example). If you want to
  60 draw a graph <i>g</i>, you can create a copy <i>g'</i> of <i>g</i>, store a
  61 mapping <i>m</i> of vertices in <i>g'</i> to vertices in <i>g</i>,
  62 <a href="make_maximal_planar.html">triangulate</a> <i>g'</i>, and then send
  63 <i>g'</i> in as the input to <tt>chrobak_payne_straight_line_drawing</tt>. The
  64 drawing returned can then be applied to <i>g</i> using <i>m</i> to translate
  65 vertices from one graph to another, since <i>g</i> contains a subset of the
  66 edges in <i>g'</i>.
  67
  68
  69
  70 <h3>Complexity</h3>
  71
  72 If the vertex index map provides constant-time access to indices, this
  73 function takes time <i>O(n + m)</i> for a planar graph with <i>n</i> vertices
  74 and <i>m</i> edges. Note that
  75 in a simple planar graph with <i>f</i> faces, <i>m</i> edges, and <i>n</i>
  76 vertices, both <i>f</i> and <i>m</i> are <i>O(n)</i>.
  77
  78 <H3>Where Defined</H3>
  79
  80 <P>
  81 <a href="../../../boost/graph/chrobak_payne_drawing.hpp">
  82 <TT>boost/graph/chrobak_payne_drawing.hpp</TT>
  83 </a>
  84
  85
  86 <h3>Parameters</h3>
  87
  88 IN: <tt>Graph&amp; g</tt>
  89
  90 <blockquote>
  91 An undirected graph. The graph type must be a model of <a
  92 href="VertexListGraph.html">Vertex List Graph</a>
  93 </blockquote>
  94
  95 IN <tt>PlanarEmbedding embedding</tt>
  96
  97 <blockquote>
  98 A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
  99 </a> that models the <a href="PlanarEmbedding.html">PlanarEmbedding</a>
 100 concept.
 101 </blockquote>
 102
 103 IN <tt>ForwardIterator</tt>
 104
 105 <blockquote>
 106 A ForwardIterator that has <tt>value_type</tt> equal to
 107 <tt>graph_traits&lt;Graph&gt;::vertex_descriptor</tt>.
 108 </blockquote>
 109
 110 OUT: <tt>PositionMap</tt>
 111
 112 <blockquote>
 113 A <a href="../../property_map/doc/LvaluePropertyMap.html">Writable LValue Property
 114 Map</a> that models the Position Map concept. The Position Map concept requires
 115 that the value mapped to be an object that has members <tt>x</tt> and
 116 <tt>y</tt>. For example, if <tt>p</tt> models PositionMap and <tt>v</tt>
 117 is a vertex in the graph, <tt>p[v].x</tt> and <tt>p[v].y</tt> are valid
 118 expressions. The type of <tt>x</tt> and <tt>y</tt> must be implicitly
 119 convertable to <tt>std::size_t</tt>.
 120 </blockquote>
 121
 122 IN: <tt>VertexIndexMap vm</tt>
 123
 124 <blockquote>
 125 A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
 126 </a> that maps vertices from <tt>g</tt> to distinct integers in the range
 127 <tt>[0, num_vertices(g) )</tt><br>
 128 <b>Default</b>: <tt>get(vertex_index,g)</tt><br>
 129 </blockquote>
 130
 131
 132
 133 <H3>Example</H3>
 134
 135 <P>
 136 <a href="../example/straight_line_drawing.cpp">
 137 <TT>examples/straight_line_drawing.cpp</TT>
 138 </a>
 139
 140 <h3>See Also</h3>
 141
 142 <p>
 143 <ul>
 144 <li> <a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a>
 145 <li> <a href="is_straight_line_drawing.html"><tt>is_straight_line_drawing</tt>
 146 </a>
 147 </ul>
 148
 149 <br>
 150 <HR>
 151 Copyright &copy; 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
 152 aaron.windsor@gmail.com</a>)
 153 </BODY>
 154 </HTML>