Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/gursoy_atun_layout.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 17.0 KB
Line 
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<!--
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<TT>gursoy_atun_layout</TT>
32</H1>
33
34<P>
35
36<h3>Synopsis</h3>
37<PRE>
38<em>// Non-named parameter version</em>
39template&lt;typename VertexListAndIncidenceGraph,  typename Topology,
40         typename PositionMap, typename VertexIndexMap,
41         typename EdgeWeightMap&gt;
42void
43gursoy_atun_layout(const VertexListAndIncidenceGraph&amp; g,
44                   const Topology&amp; space,
45                   PositionMap position,
46                   int nsteps = num_vertices(g),
47                   double diameter_initial = sqrt((double)num_vertices(g)),
48                   double diameter_final = 1,
49                   double learning_constant_initial = 0.8,
50                   double learning_constant_final = 0.2,
51                   VertexIndexMap vertex_index_map = get(vertex_index, g),
52                   EdgeWeightMap weight = dummy_property_map());
53
54<em>// Named parameter version</em>
55template&lt;typename VertexListAndIncidenceGraph, typename Topology,
56         typename PositionMap, typename P, typename T, typename R&gt;
57void
58gursoy_atun_layout(const VertexListAndIncidenceGraph&amp; g, 
59                   const Topology&amp; space,
60                   PositionMap position,
61                   const bgl_named_params&lt;P,T,R&gt;&amp; params = <em>all defaults</em>);
62
63<em>// Topologies</em>
64template&lt;std::size_t Dims&gt; class <a href="#convex_topology">convex_topology</a>;
65template&lt;std::size_t Dims, typename RandomNumberGenerator = minstd_rand&gt; class <a href="#hypercube_topology">hypercube_topology</a>;
66template&lt;typename RandomNumberGenerator = minstd_rand&gt; class <a href="#square_topology">square_topology</a>;
67template&lt;typename RandomNumberGenerator = minstd_rand&gt; class <a href="#cube_topology">cube_topology</a>;
68template&lt;std::size_t Dims, typename RandomNumberGenerator = minstd_rand&gt; class <a href="#ball_topology">ball_topology</a>;
69template&lt;typename RandomNumberGenerator = minstd_rand&gt; class <a href="#circle_topology">circle_topology</a>;
70template&lt;typename RandomNumberGenerator = minstd_rand&gt; class <a href="#sphere_topology">sphere_topology</a>;
71template&lt;typename RandomNumberGenerator = minstd_rand&gt; class <a href="#heart_topology">heart_topology</a>;
72</PRE>
73
74<h3>Description</h3>
75
76<P> This algorithm&nbsp;[<A HREF="bibliography.html#gursoy00">60</A>]
77performs layout of directed graphs, either weighted or unweighted. This
78algorithm is very different from the <a
79href="kamada_kawai_spring_layout.html">Kamada-Kawai</a> and <a
80href="fruchterman_reingold.html">Fruchterman-Reingold</a> algorithms,
81because it does not explicitly strive to layout graphs in a visually
82pleasing manner. Instead, it attempts to distribute the vertices
83uniformly within a <em>topology</em> (e.g., rectangle, sphere, heart shape),
84keeping vertices close to their neighbors. The algorithm itself is
85based on <a
86href="http://davis.wpi.edu/~matt/courses/soms/">Self-Organizing
87Maps</a>.
88
89<p> <a href="#topologies">Various topologies</a> are provided that
90produce different, interesting results. The <a
91href="#square_topology">square topology</a> can be used for normal
92display of graphs or distributing vertices for parallel computation on
93a process array, for instance. Other topologies, such as the <a
94href="#sphere_topology">sphere topology</a> (or N-dimensional <a
95href="#ball_topology">ball topology</a>) make sense for different
96problems, whereas the <a href="#heart_topology">heart topology</a> is
97just plain fun. One can also <a href="#topology-concept">define a
98topology</a> to suit other particular needs. <br>
99
100<a href="#square_topology"><img src="figs/ga-square.png"></a>
101<a href="#heart_topology"><img src="figs/ga-heart.png"></a>
102<a href="#circle_topology"><img src="figs/ga-circle.png"></a>
103
104
105<h3>Where Defined</h3>
106
107<a href="../../../boost/graph/gursoy_atun_layout.hpp"><tt>boost/graph/gursoy_atun_layout.hpp</tt></a>
108
109<h3>Parameters</h3>
110
111IN: <tt>const Graph&amp; g</tt> 
112<blockquote>
113  The graph object on which the algorithm will be applied.  The type
114  <tt>Graph</tt> must be a model of <a
115  href="./VertexAndEdgeListGraph.html">Vertex List Graph</a> and <a
116  href="IncidenceGraph.html">Incidence Graph</a>.
117</blockquote>
118
119IN: <tt>const Topology&amp; space</tt>
120<blockquote>
121  The topology on which the graph will be layed out. The type must
122  model the <a href="#topology-concept">Topology</a> concept.
123</blockquote>
124
125OUT: <tt>PositionMap position</tt>
126<blockquote>
127  The property map that stores the position of each vertex. The type
128  <tt>PositionMap</tt> must be a model of <a
129  href="../../property_map/LvaluePropertyMap.html">Lvalue Property
130  Map</a> such that the vertex descriptor type of <tt>Graph</tt> is
131  convertible to its key type. Its value type must be the type of a
132  point in the topology.
133</blockquote>
134
135IN: <tt>int nsteps</tt>
136<blockquote>
137  The number of iterations to perform.<br>
138  <b>Default</b>: <tt>num_vertices(g)</tt>
139</blockquote>
140
141IN: <tt>double diameter_initial</tt>
142<blockquote>
143  When a vertex is selected to be updated, all vertices that are
144  reachable from that vertex within a certain diameter (in graph
145  terms) will also be updated. This diameter begins at
146  <tt>diameter_initial</tt> in the first iteration and ends at
147  <tt>diameter_final</tt> in the last iteration, progressing
148  exponentially. Generally the diameter decreases, in a manner similar to
149  the cooling schedule in <a
150href="fruchterman_reingold.html">Fruchterman-Reingold</a>. The
151diameter should typically decrease in later iterations, so this value
152should not be less than <tt>diameter_final</tt>.<br>
153  <b>Default</b>: <tt>sqrt((double)num_vertices(g))</tt>
154</blockquote>
155
156IN: <tt>double diameter_final</tt>
157<blockquote>
158  The final value of the diameter.<br>
159  <b>Default</b>: 1.0
160</blockquote>
161
162IN: <tt>double learning_constant_initial</tt>
163<blockquote>
164  The learning rate affects how far vertices can moved to rearrange
165  themselves in a given iteration. The learning rate progresses
166  linearly from the initial value to the final value, both of which
167  should be between 0 and 1. The learning rate should typically
168  decrease, so the initial value should not exceed the final
169  value.<br> <b>Default</b>: 0.8
170</blockquote>
171
172IN: <tt>double learning_constant_final</tt>
173<blockquote>
174  The final learning rate constant.<br>
175  <b>Default</b>: 0.2
176</blockquote>
177
178IN: <tt>VertexIndexMap vertex_index_map</tt> 
179<blockquote>
180  This maps each vertex to an integer in the range <tt>[0,
181    num_vertices(g))</tt>.
182  The type <tt>VertexIndexMap</tt> must be a model of <a
183  href="../../property_map/ReadablePropertyMap.html">Readable Property
184  Map</a>. The value type of the map must be an integer type. The
185  vertex descriptor type of the graph needs to be usable as the key
186  type of the map.<br>
187<b>Default:</b> <tt>get(vertex_index, g)</tt>
188    Note: if you use this default, make sure your graph has
189    an internal <tt>vertex_index</tt> property. For example,
190    <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
191    not have an internal <tt>vertex_index</tt> property.
192</blockquote>
193
194IN: <tt>EdgeWeightMap weight</tt> 
195<blockquote>
196  This maps each edge to an weight.
197    num_vertices(g))</tt>. This is only necessary when no
198    displacement map is provided.
199  The type <tt>EdgeWeightMap</tt> must be a model of <a
200  href="../../property_map/ReadablePropertyMap.html">Readable Property
201  Map</a>. The value type of the map must be an floating-point type
202  compatible with <tt>double</tt>. The edge descriptor type of the
203  graph needs to be usable as the key type of the map. When this map
204  is a <tt>dummy_property_map</tt>, the algorithm assumes the graph is
205  unweighted.<br>
206<b>Default:</b> <tt>dummy_property_map()</tt>
207</blockquote>
208
209<h3>Named Parameters</h3>
210
211IN: <tt>iterations(int n)</tt>
212<blockquote>
213Executes the algorithm for <em>n</em> iterations.<br>
214<b>Default:</b> <tt>num_vertices(g)</tt>
215</blockquote>
216
217IN: <tt>diameter_range(std::pair<T, T> range)</tt>
218<blockquote>
219Range specifying the parameters (<tt>diameter_initial</tt>, <tt>diameter_final</tt>). <br>
220<b>Default:</b> <tt>std::make_pair(sqrt((double)num_vertices(g)), 1.0)</tt>
221</blockquote>
222
223IN: <tt>learning_constant_range(std::pair<T, T> range)</tt>
224<blockquote>
225Range specifying the parameters (<tt>learning_constant_initial</tt>, <tt>learning_constant_final</tt>). <br>
226<b>Default:</b> <tt>std::make_pair(0.8, 0.2)</tt>
227</blockquote>
228
229IN: <tt>edge_weight(EdgeWeightMap weight)</tt>
230<blockquote>
231Equivalent to the non-named <tt>weight</tt> parameter.<br>
232<b>Default:</b> <tt>dummy_property_map()</tt>
233</blockquote>
234
235IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> 
236<blockquote>
237Equivalent to the non-named <tt>vertex_index_map</tt> parameter.<br>
238<b>Default:</b> <tt>get(vertex_index, g)</tt>
239    Note: if you use this default, make sure your graph has
240    an internal <tt>vertex_index</tt> property. For example,
241    <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
242    not have an internal <tt>vertex_index</tt> property.
243</blockquote>
244
245<a name="topologies"><h3>Topologies</h3></a>
246A topology is a description of a space on which layout can be
247performed. Some common two, three, and multidimensional topologies
248are provided, or you may create your own so long as it meets the
249requirements of the <a href="#topology-concept">Topology concept</a>.
250
251<a name="topology-concept"><h4>Topology Concept</h4></a> Let
252<tt>Topology</tt> be a model of the Topology concept and let
253<tt>space</tt> be an object of type <tt>Topology</tt>. <tt>p1</tt> and
254<tt>p2</tt> are objects of associated type <tt>point_type</tt> (see
255below). The following expressions must be valid:
256
257<table border="1">
258  <tr>
259    <th>Expression</th>
260    <th>Type</th>
261    <th>Description</th>
262  </tr>
263  <tr>
264    <td><tt>Topology::point_type</tt></td>
265    <td>type</td>
266    <td>The type of points in the space.</td>
267  </tr>
268  <tr>
269    <td><tt>space.random_point()</tt></td>
270    <td>point_type</td>
271    <td>Returns a random point (usually uniformly distributed) within
272    the space.</td>
273  </tr>
274  <tr>
275    <td><tt>space.distance(p1, p2)</tt></td>
276    <td>double</td>
277    <td>Get a quantity representing the distance between <tt>p1</tt>
278    and <tt>p2</tt> using a path going completely inside the space.
279    This only needs to have the same &lt; relation as actual
280    distances, and does not need to satisfy the other properties of a
281    norm in a Banach space.</td>
282  </tr>
283  <tr>
284    <td><tt>space.move_position_toward(p1, fraction, p2)</tt></td>
285    <td>point_type</td>
286    <td>Returns a point that is a fraction of the way from <tt>p1</tt>
287    to <tt>p2</tt>, moving along a "line" in the space according to
288    the distance measure. <tt>fraction</tt> is a <tt>double</tt>
289    between 0 and 1, inclusive.</td>
290  </tr>
291</table>
292
293<a name="convex_topology"><h3>Class template <tt>convex_topology</tt></h3></a>
294
295<p>Class template <tt>convex_topology</tt> implements the basic
296distance and point movement functions for any convex topology in
297<tt>Dims</tt> dimensions. It is not itself a topology, but is intended
298as a base class that any convex topology can derive from. The derived
299topology need only provide a suitable <tt>random_point</tt> function
300that returns a random point within the space.
301
302<pre>
303template&lt;std::size_t Dims&gt;
304class convex_topology
305{
306  struct point
307  {
308    point() { }
309    double& operator[](std::size_t i) {return values[i];}
310    const double& operator[](std::size_t i) const {return values[i];}
311
312  private:
313    double values[Dims];
314  };
315
316 public:
317  typedef point point_type;
318
319  double distance(point a, point b) const;
320  point move_position_toward(point a, double fraction, point b) const;
321};
322</pre>
323
324<a name="hypercube_topology"><h3>Class template <tt>hypercube_topology</tt></h3></a>
325
326<p>Class template <tt>hypercube_topology</tt> implements a
327<tt>Dims</tt>-dimensional hypercube. It is a convex topology whose
328points are drawn from a random number generator of type
329<tt>RandomNumberGenerator</tt>. The <tt>hypercube_topology</tt> can
330be constructed with a given random number generator; if omitted, a
331new, default-constructed random number generator will be used. The
332resulting layout will be contained within the hypercube, whose sides
333measure 2*<tt>scaling</tt> long (points will fall in the range
334[-<tt>scaling</tt>, <tt>scaling</tt>] in each dimension).
335
336<pre>
337template&lt;std::size_t Dims, typename RandomNumberGenerator = minstd_rand&gt;
338class hypercube_topology : public <a href="#convex_topology">convex_topology</a>&lt;Dims&gt;
339{
340public:
341  explicit hypercube_topology(double scaling = 1.0);
342  hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0);
343  point_type random_point() const;
344};
345</pre>
346
347<a name="square_topology"><h3>Class template <tt>square_topology</tt></h3></a>
348
349<p>Class template <tt>square_topology</tt> is a two-dimensional
350hypercube topology.
351
352<pre>
353template&lt;typename RandomNumberGenerator = minstd_rand&gt;
354class square_topology : public <a href="#hypercube_topology">hypercube_topology</a>&lt;2, RandomNumberGenerator&gt;
355{
356 public:
357  explicit square_topology(double scaling = 1.0);
358  square_topology(RandomNumberGenerator& gen, double scaling = 1.0);
359};
360</pre>
361
362<a name="cube_topology"><h3>Class template <tt>cube_topology</tt></h3></a>
363
364<p>Class template <tt>cube_topology</tt> is a two-dimensional
365hypercube topology.
366
367<pre>
368template&lt;typename RandomNumberGenerator = minstd_rand&gt;
369class cube_topology : public <a href="#hypercube_topology">hypercube_topology</a>&lt;3, RandomNumberGenerator&gt;
370{
371 public:
372  explicit cube_topology(double scaling = 1.0);
373  cube_topology(RandomNumberGenerator& gen, double scaling = 1.0);
374};
375</pre>
376
377<a name="ball_topology"><h3>Class template <tt>ball_topology</tt></h3></a>
378
379<p>Class template <tt>ball_topology</tt> implements a
380<tt>Dims</tt>-dimensional ball. It is a convex topology whose points
381are drawn from a random number generator of type
382<tt>RandomNumberGenerator</tt> but reside inside the ball. The
383<tt>ball_topology</tt> can be constructed with a given random number
384generator; if omitted, a new, default-constructed random number
385generator will be used. The resulting layout will be contained within
386the ball with the given <tt>radius</tt>.
387
388<pre>
389template&lt;std::size_t Dims, typename RandomNumberGenerator = minstd_rand&gt;
390class ball_topology : public <a href="#convex_topology">convex_topology</a>&lt;Dims&gt;
391{
392public:
393  explicit ball_topology(double radius = 1.0);
394  ball_topology(RandomNumberGenerator& gen, double radius = 1.0);
395  point_type random_point() const;
396};
397</pre>
398
399<a name="circle_topology"><h3>Class template <tt>circle_topology</tt></h3></a>
400
401<p>Class template <tt>circle_topology</tt> is a two-dimensional
402ball topology.
403
404<pre>
405template&lt;typename RandomNumberGenerator = minstd_rand&gt;
406class circle_topology : public <a href="#ball_topology">ball_topology</a>&lt;2, RandomNumberGenerator&gt;
407{
408 public:
409  explicit circle_topology(double radius = 1.0);
410  circle_topology(RandomNumberGenerator& gen, double radius = 1.0);
411};
412</pre>
413
414<a name="sphere_topology"><h3>Class template <tt>sphere_topology</tt></h3></a>
415
416<p>Class template <tt>sphere_topology</tt> is a two-dimensional
417ball topology.
418
419<pre>
420template&lt;typename RandomNumberGenerator = minstd_rand&gt;
421class sphere_topology : public <a href="#ball_topology">ball_topology</a>&lt;3, RandomNumberGenerator&gt;
422{
423 public:
424  explicit sphere_topology(double radius = 1.0);
425  sphere_topology(RandomNumberGenerator& gen, double radius = 1.0);
426};
427</pre>
428
429<a name="heart_topology"><h3>Class template <tt>heart_topology</tt></h3></a>
430
431<p>Class template <tt>heart_topology</tt> is topology in the shape of
432a heart. It serves as an example of a non-convex, nontrivial topology
433for layout.
434
435<pre>
436template&lt;typename RandomNumberGenerator = minstd_rand&gt;
437class heart_topology
438{
439 public:
440  typedef <em>unspecified</em> point_type;
441
442  heart_topology();
443  heart_topology(RandomNumberGenerator& gen);
444  point_type random_point() const;
445  double distance(point_type a, point_type b) const;
446  point_type move_position_toward(point_type a, double fraction, point_type b) const;
447};
448</pre>
449
450<br>
451<HR>
452<TABLE>
453<TR valign=top>
454<TD nowrap>Copyright &copy; 2004</TD><TD>
455Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br>
456<A HREF="../../../people/doug_gregor.html">Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
457  <A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
458Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
459</TD></TR></TABLE>
460
461</BODY>
462</HTML> 
Note: See TracBrowser for help on using the repository browser.