3 Copyright (c) 2004 Trustees of Indiana University
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)
10 <Title>Boost Graph Library: G
ürsoy-Atun Layout
</Title>
11 <script language=
"JavaScript" type=
"text/JavaScript">
13 function address(host, user) {
15 var thingy = user+atchar+host;
16 thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
17 document.write(thingy);
24 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
26 <IMG SRC=
"../../../boost.png"
27 ALT=
"C++ Boost" width=
"277" height=
"86">
32 <TT>gursoy_atun_layout
</TT>
39 <em>// Non-named parameter version
</em>
40 template
<typename VertexListAndIncidenceGraph, typename Topology,
41 typename PositionMap, typename VertexIndexMap,
42 typename EdgeWeightMap
>
44 gursoy_atun_layout(const VertexListAndIncidenceGraph
& g,
45 const Topology
& space,
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());
55 <em>// Named parameter version
</em>
56 template
<typename VertexListAndIncidenceGraph, typename Topology,
57 typename PositionMap, typename P, typename T, typename R
>
59 gursoy_atun_layout(const VertexListAndIncidenceGraph
& g,
60 const Topology
& space,
62 const bgl_named_params
<P,T,R
>& params =
<em>all defaults
</em>);
67 <P> This algorithm
[
<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
79 href=
"http://davis.wpi.edu/~matt/courses/soms/">Self-Organizing
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>
88 <h3>Where Defined
</h3>
90 <a href=
"../../../boost/graph/gursoy_atun_layout.hpp"><tt>boost/graph/gursoy_atun_layout.hpp
</tt></a>
94 IN:
<tt>const Graph
& g
</tt>
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>.
102 IN:
<tt>const Topology
& space
</tt>
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.
108 OUT:
<tt>PositionMap position
</tt>
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>.
118 IN:
<tt>int nsteps
</tt>
120 The number of iterations to perform.
<br>
121 <b>Default
</b>:
<tt>num_vertices(g)
</tt>
124 IN:
<tt>double diameter_initial
</tt>
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>
139 IN:
<tt>double diameter_final
</tt>
141 The final value of the diameter.
<br>
145 IN:
<tt>double learning_constant_initial
</tt>
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
155 IN:
<tt>double learning_constant_final
</tt>
157 The final learning rate constant.
<br>
161 IN:
<tt>VertexIndexMap vertex_index_map
</tt>
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
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.
178 IN:
<tt>EdgeWeightMap weight
</tt>
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
188 <b>Default:
</b> <tt>dummy_property_map()
</tt>
191 <h3>Named Parameters
</h3>
193 IN:
<tt>iterations(int n)
</tt>
195 Executes the algorithm for
<em>n
</em> iterations.
<br>
196 <b>Default:
</b> <tt>num_vertices(g)
</tt>
199 IN:
<tt>diameter_range(std::pair
<T, T
> range)
</tt>
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>
205 IN:
<tt>learning_constant_range(std::pair
<T, T
> range)
</tt>
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>
211 IN:
<tt>edge_weight(EdgeWeightMap weight)
</tt>
213 Equivalent to the non-named
<tt>weight
</tt> parameter.
<br>
214 <b>Default:
</b> <tt>dummy_property_map()
</tt>
217 IN:
<tt>vertex_index_map(VertexIndexMap i_map)
</tt>
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.
231 <TD nowrap
>Copyright
© 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>)