libs/graph/doc/gursoy_atun_layout.html

   1 <HTML>
   2 <!--
   3      Copyright (c) 2004 Trustees of Indiana University
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Boost Graph Library: G&uuml;rsoy-Atun Layout</Title>
  11 <script language="JavaScript" type="text/JavaScript">
  12 <!--
  13 function address(host, user) {
  14         var atchar = '@';
  15         var thingy = user+atchar+host;
  16         thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
  17         document.write(thingy);
  18 }
  19 //-->
  20 </script>
  21 </head>
  22
  23
  24 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  25         ALINK="#ff0000">
  26 <IMG SRC="../../../boost.png"
  27      ALT="C++ Boost" width="277" height="86">
  28
  29 <BR Clear>
  30
  31 <H1>
  32 <TT>gursoy_atun_layout</TT>
  33 </H1>
  34
  35 <P>
  36
  37 <h3>Synopsis</h3>
  38 <PRE>
  39 <em>// Non-named parameter version</em>
  40 template&lt;typename VertexListAndIncidenceGraph,  typename Topology,
  41          typename PositionMap, typename VertexIndexMap,
  42          typename EdgeWeightMap&gt;
  43 void
  44 gursoy_atun_layout(const VertexListAndIncidenceGraph&amp; g,
  45                    const Topology&amp; space,
  46                    PositionMap position,
  47                    int nsteps = num_vertices(g),
  48                    double diameter_initial = sqrt((double)num_vertices(g)),
  49                    double diameter_final = 1,
  50                    double learning_constant_initial = 0.8,
  51                    double learning_constant_final = 0.2,
  52                    VertexIndexMap vertex_index_map = get(vertex_index, g),
  53                    EdgeWeightMap weight = dummy_property_map());
  54
  55 <em>// Named parameter version</em>
  56 template&lt;typename VertexListAndIncidenceGraph, typename Topology,
  57          typename PositionMap, typename P, typename T, typename R&gt;
  58 void
  59 gursoy_atun_layout(const VertexListAndIncidenceGraph&amp; g,
  60                    const Topology&amp; space,
  61                    PositionMap position,
  62                    const bgl_named_params&lt;P,T,R&gt;&amp; params = <em>all defaults</em>);
  63 </PRE>
  64
  65 <h3>Description</h3>
  66
  67 <P> This algorithm&nbsp;[<A HREF="bibliography.html#gursoy00">60</A>]
  68 performs layout of directed graphs, either weighted or unweighted. This
  69 algorithm is very different from the <a
  70 href="kamada_kawai_spring_layout.html">Kamada-Kawai</a> and <a
  71 href="fruchterman_reingold.html">Fruchterman-Reingold</a> algorithms,
  72 because it does not explicitly strive to layout graphs in a visually
  73 pleasing manner. Instead, it attempts to distribute the vertices
  74 uniformly within a <em>topology</em> (e.g., rectangle, sphere, heart shape),
  75 keeping vertices close to their neighbors; <a href="topology.html">various
  76 topologies</a> are provided by BGL, and users can also create their own. The
  77 algorithm itself is
  78 based on <a
  79 href="http://davis.wpi.edu/~matt/courses/soms/">Self-Organizing
  80 Maps</a>.
  81
  82 <p>
  83 <a href="topology.html#square_topology"><img src="figs/ga-square.png"></a>
  84 <a href="topology.html#heart_topology"><img src="figs/ga-heart.png"></a>
  85 <a href="topology.html#circle_topology"><img src="figs/ga-circle.png"></a>
  86 </p>
  87
  88 <h3>Where Defined</h3>
  89
  90 <a href="../../../boost/graph/gursoy_atun_layout.hpp"><tt>boost/graph/gursoy_atun_layout.hpp</tt></a>
  91
  92 <h3>Parameters</h3>
  93
  94 IN: <tt>const Graph&amp; g</tt>
  95 <blockquote>
  96   The graph object on which the algorithm will be applied.  The type
  97   <tt>Graph</tt> must be a model of <a
  98   href="./VertexAndEdgeListGraph.html">Vertex List Graph</a> and <a
  99   href="IncidenceGraph.html">Incidence Graph</a>.
 100 </blockquote>
 101
 102 IN: <tt>const Topology&amp; space</tt>
 103 <blockquote>
 104   The topology on which the graph will be laid out. The type must
 105   model the <a href="topology.html#topology-concept">Topology</a> concept.
 106 </blockquote>
 107
 108 OUT: <tt>PositionMap position</tt>
 109 <blockquote>
 110   The property map that stores the position of each vertex. The type
 111   <tt>PositionMap</tt> must be a model of <a
 112   href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
 113   Map</a> such that the vertex descriptor type of <tt>Graph</tt> is
 114   convertible to its key type. Its value type must be
 115   <tt>Topology::point_type</tt>.
 116 </blockquote>
 117
 118 IN: <tt>int nsteps</tt>
 119 <blockquote>
 120   The number of iterations to perform.<br>
 121   <b>Default</b>: <tt>num_vertices(g)</tt>
 122 </blockquote>
 123
 124 IN: <tt>double diameter_initial</tt>
 125 <blockquote>
 126   When a vertex is selected to be updated, all vertices that are
 127   reachable from that vertex within a certain diameter (in graph
 128   terms) will also be updated. This diameter begins at
 129   <tt>diameter_initial</tt> in the first iteration and ends at
 130   <tt>diameter_final</tt> in the last iteration, progressing
 131   exponentially. Generally the diameter decreases, in a manner similar to
 132   the cooling schedule in <a
 133 href="fruchterman_reingold.html">Fruchterman-Reingold</a>. The
 134 diameter should typically decrease in later iterations, so this value
 135 should not be less than <tt>diameter_final</tt>.<br>
 136   <b>Default</b>: <tt>sqrt((double)num_vertices(g))</tt>
 137 </blockquote>
 138
 139 IN: <tt>double diameter_final</tt>
 140 <blockquote>
 141   The final value of the diameter.<br>
 142   <b>Default</b>: 1.0
 143 </blockquote>
 144
 145 IN: <tt>double learning_constant_initial</tt>
 146 <blockquote>
 147   The learning rate affects how far vertices can moved to rearrange
 148   themselves in a given iteration. The learning rate progresses
 149   linearly from the initial value to the final value, both of which
 150   should be between 0 and 1. The learning rate should typically
 151   decrease, so the initial value should not exceed the final
 152   value.<br> <b>Default</b>: 0.8
 153 </blockquote>
 154
 155 IN: <tt>double learning_constant_final</tt>
 156 <blockquote>
 157   The final learning rate constant.<br>
 158   <b>Default</b>: 0.2
 159 </blockquote>
 160
 161 IN: <tt>VertexIndexMap vertex_index_map</tt>
 162 <blockquote>
 163   This maps each vertex to an integer in the range <tt>[0,
 164     num_vertices(g))</tt>. This is only necessary when no
 165     displacement map is provided.
 166   The type <tt>VertexIndexMap</tt> must be a model of <a
 167   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 168   Map</a>. The value type of the map must be an integer type. The
 169   vertex descriptor type of the graph needs to be usable as the key
 170   type of the map.<br>
 171 <b>Default:</b> <tt>get(vertex_index, g)</tt>
 172     Note: if you use this default, make sure your graph has
 173     an internal <tt>vertex_index</tt> property. For example,
 174     <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
 175     not have an internal <tt>vertex_index</tt> property.
 176 </blockquote>
 177
 178 IN: <tt>EdgeWeightMap weight</tt>
 179 <blockquote>
 180   This maps each edge to a weight.
 181   The type <tt>EdgeWeightMap</tt> must be a model of <a
 182   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 183   Map</a>. The value type of the map must be an floating-point type
 184   compatible with <tt>double</tt>. The edge descriptor type of the
 185   graph needs to be usable as the key type of the map. When this map
 186   is a <tt>dummy_property_map</tt>, the algorithm assumes the graph is
 187   unweighted.<br>
 188 <b>Default:</b> <tt>dummy_property_map()</tt>
 189 </blockquote>
 190
 191 <h3>Named Parameters</h3>
 192
 193 IN: <tt>iterations(int n)</tt>
 194 <blockquote>
 195 Executes the algorithm for <em>n</em> iterations.<br>
 196 <b>Default:</b> <tt>num_vertices(g)</tt>
 197 </blockquote>
 198
 199 IN: <tt>diameter_range(std::pair<T, T> range)</tt>
 200 <blockquote>
 201 Range specifying the parameters (<tt>diameter_initial</tt>, <tt>diameter_final</tt>). <br>
 202 <b>Default:</b> <tt>std::make_pair(sqrt((double)num_vertices(g)), 1.0)</tt>
 203 </blockquote>
 204
 205 IN: <tt>learning_constant_range(std::pair<T, T> range)</tt>
 206 <blockquote>
 207 Range specifying the parameters (<tt>learning_constant_initial</tt>, <tt>learning_constant_final</tt>). <br>
 208 <b>Default:</b> <tt>std::make_pair(0.8, 0.2)</tt>
 209 </blockquote>
 210
 211 IN: <tt>edge_weight(EdgeWeightMap weight)</tt>
 212 <blockquote>
 213 Equivalent to the non-named <tt>weight</tt> parameter.<br>
 214 <b>Default:</b> <tt>dummy_property_map()</tt>
 215 </blockquote>
 216
 217 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
 218 <blockquote>
 219 Equivalent to the non-named <tt>vertex_index_map</tt> parameter.<br>
 220 <b>Default:</b> <tt>get(vertex_index, g)</tt>
 221     Note: if you use this default, make sure your graph has
 222     an internal <tt>vertex_index</tt> property. For example,
 223     <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
 224     not have an internal <tt>vertex_index</tt> property.
 225 </blockquote>
 226
 227 <br>
 228 <HR>
 229 <TABLE>
 230 <TR valign=top>
 231 <TD nowrap>Copyright &copy; 2004 Trustees of Indiana University</TD><TD>
 232 Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br>
 233 <A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
 234   <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 235 Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
 236 </TD></TR></TABLE>
 237
 238 </BODY>
 239 </HTML>