Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/gursoy_atun_layout.html @ 12

Last change on this file since 12 was 12, checked in by landauf, 17 years ago

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