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ürsoy-Atun Layout</Title> 11<script language="JavaScript" type="text/JavaScript"> 12<!-- 13function 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> 40template<typename VertexListAndIncidenceGraph, typename Topology, 41 typename PositionMap, typename VertexIndexMap, 42 typename EdgeWeightMap> 43void 44gursoy_atun_layout(const VertexListAndIncidenceGraph& g, 45 const Topology& 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> 56template<typename VertexListAndIncidenceGraph, typename Topology, 57 typename PositionMap, typename P, typename T, typename R> 58void 59gursoy_atun_layout(const VertexListAndIncidenceGraph& g, 60 const Topology& space, 61 PositionMap position, 62 const bgl_named_params<P,T,R>& params = <em>all defaults</em>); 63</PRE> 64 65<h3>Description</h3> 66 67<P> This algorithm [<A HREF="bibliography.html#gursoy00">60</A>] 68performs layout of directed graphs, either weighted or unweighted. This 69algorithm is very different from the <a 70href="kamada_kawai_spring_layout.html">Kamada-Kawai</a> and <a 71href="fruchterman_reingold.html">Fruchterman-Reingold</a> algorithms, 72because it does not explicitly strive to layout graphs in a visually 73pleasing manner. Instead, it attempts to distribute the vertices 74uniformly within a <em>topology</em> (e.g., rectangle, sphere, heart shape), 75keeping vertices close to their neighbors; <a href="topology.html">various 76topologies</a> are provided by BGL, and users can also create their own. The 77algorithm itself is 78based on <a 79href="http://davis.wpi.edu/~matt/courses/soms/">Self-Organizing 80Maps</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 94IN: <tt>const Graph& 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 102IN: <tt>const Topology& 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 108OUT: <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 118IN: <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 124IN: <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 133href="fruchterman_reingold.html">Fruchterman-Reingold</a>. The 134diameter should typically decrease in later iterations, so this value 135should not be less than <tt>diameter_final</tt>.<br> 136 <b>Default</b>: <tt>sqrt((double)num_vertices(g))</tt> 137</blockquote> 138 139IN: <tt>double diameter_final</tt> 140<blockquote> 141 The final value of the diameter.<br> 142 <b>Default</b>: 1.0 143</blockquote> 144 145IN: <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 155IN: <tt>double learning_constant_final</tt> 156<blockquote> 157 The final learning rate constant.<br> 158 <b>Default</b>: 0.2 159</blockquote> 160 161IN: <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>adjacency_list</tt> with <tt>VertexList=listS</tt> does 175 not have an internal <tt>vertex_index</tt> property. 176</blockquote> 177 178IN: <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 193IN: <tt>iterations(int n)</tt> 194<blockquote> 195Executes the algorithm for <em>n</em> iterations.<br> 196<b>Default:</b> <tt>num_vertices(g)</tt> 197</blockquote> 198 199IN: <tt>diameter_range(std::pair<T, T> range)</tt> 200<blockquote> 201Range 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 205IN: <tt>learning_constant_range(std::pair<T, T> range)</tt> 206<blockquote> 207Range 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 211IN: <tt>edge_weight(EdgeWeightMap weight)</tt> 212<blockquote> 213Equivalent to the non-named <tt>weight</tt> parameter.<br> 214<b>Default:</b> <tt>dummy_property_map()</tt> 215</blockquote> 216 217IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> 218<blockquote> 219Equivalent 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 © 2004 Trustees of Indiana University</TD><TD> 232Jeremiah 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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 235Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>) 236</TD></TR></TABLE> 237 238</BODY> 239</HTML> 240
