123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239 |
- <HTML>
- <!--
- Copyright (c) 2004 Trustees of Indiana University
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <Head>
- <Title>Boost Graph Library: Gürsoy-Atun Layout</Title>
- <script language="JavaScript" type="text/JavaScript">
- <!--
- function address(host, user) {
- var atchar = '@';
- var thingy = user+atchar+host;
- thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
- document.write(thingy);
- }
- //-->
- </script>
- </head>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1>
- <TT>gursoy_atun_layout</TT>
- </H1>
- <P>
- <h3>Synopsis</h3>
- <PRE>
- <em>// Non-named parameter version</em>
- template<typename VertexListAndIncidenceGraph, typename Topology,
- typename PositionMap, typename VertexIndexMap,
- typename EdgeWeightMap>
- void
- gursoy_atun_layout(const VertexListAndIncidenceGraph& g,
- const Topology& space,
- PositionMap position,
- int nsteps = num_vertices(g),
- double diameter_initial = sqrt((double)num_vertices(g)),
- double diameter_final = 1,
- double learning_constant_initial = 0.8,
- double learning_constant_final = 0.2,
- VertexIndexMap vertex_index_map = get(vertex_index, g),
- EdgeWeightMap weight = dummy_property_map());
- <em>// Named parameter version</em>
- template<typename VertexListAndIncidenceGraph, typename Topology,
- typename PositionMap, typename P, typename T, typename R>
- void
- gursoy_atun_layout(const VertexListAndIncidenceGraph& g,
- const Topology& space,
- PositionMap position,
- const bgl_named_params<P,T,R>& params = <em>all defaults</em>);
- </PRE>
- <h3>Description</h3>
- <P> This algorithm [<A HREF="bibliography.html#gursoy00">60</A>]
- performs layout of directed graphs, either weighted or unweighted. This
- algorithm is very different from the <a
- href="kamada_kawai_spring_layout.html">Kamada-Kawai</a> and <a
- href="fruchterman_reingold.html">Fruchterman-Reingold</a> algorithms,
- because it does not explicitly strive to layout graphs in a visually
- pleasing manner. Instead, it attempts to distribute the vertices
- uniformly within a <em>topology</em> (e.g., rectangle, sphere, heart shape),
- keeping vertices close to their neighbors; <a href="topology.html">various
- topologies</a> are provided by BGL, and users can also create their own. The
- algorithm itself is
- based on <a
- href="http://davis.wpi.edu/~matt/courses/soms/">Self-Organizing
- Maps</a>.
- <p>
- <a href="topology.html#square_topology"><img src="figs/ga-square.png"></a>
- <a href="topology.html#heart_topology"><img src="figs/ga-heart.png"></a>
- <a href="topology.html#circle_topology"><img src="figs/ga-circle.png"></a>
- </p>
- <h3>Where Defined</h3>
- <a href="../../../boost/graph/gursoy_atun_layout.hpp"><tt>boost/graph/gursoy_atun_layout.hpp</tt></a>
- <h3>Parameters</h3>
- IN: <tt>const Graph& g</tt>
- <blockquote>
- The graph object on which the algorithm will be applied. The type
- <tt>Graph</tt> must be a model of <a
- href="./VertexAndEdgeListGraph.html">Vertex List Graph</a> and <a
- href="IncidenceGraph.html">Incidence Graph</a>.
- </blockquote>
- IN: <tt>const Topology& space</tt>
- <blockquote>
- The topology on which the graph will be laid out. The type must
- model the <a href="topology.html#topology-concept">Topology</a> concept.
- </blockquote>
- OUT: <tt>PositionMap position</tt>
- <blockquote>
- The property map that stores the position of each vertex. The type
- <tt>PositionMap</tt> must be a model of <a
- href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
- Map</a> such that the vertex descriptor type of <tt>Graph</tt> is
- convertible to its key type. Its value type must be
- <tt>Topology::point_type</tt>.
- </blockquote>
- IN: <tt>int nsteps</tt>
- <blockquote>
- The number of iterations to perform.<br>
- <b>Default</b>: <tt>num_vertices(g)</tt>
- </blockquote>
- IN: <tt>double diameter_initial</tt>
- <blockquote>
- When a vertex is selected to be updated, all vertices that are
- reachable from that vertex within a certain diameter (in graph
- terms) will also be updated. This diameter begins at
- <tt>diameter_initial</tt> in the first iteration and ends at
- <tt>diameter_final</tt> in the last iteration, progressing
- exponentially. Generally the diameter decreases, in a manner similar to
- the cooling schedule in <a
- href="fruchterman_reingold.html">Fruchterman-Reingold</a>. The
- diameter should typically decrease in later iterations, so this value
- should not be less than <tt>diameter_final</tt>.<br>
- <b>Default</b>: <tt>sqrt((double)num_vertices(g))</tt>
- </blockquote>
- IN: <tt>double diameter_final</tt>
- <blockquote>
- The final value of the diameter.<br>
- <b>Default</b>: 1.0
- </blockquote>
- IN: <tt>double learning_constant_initial</tt>
- <blockquote>
- The learning rate affects how far vertices can moved to rearrange
- themselves in a given iteration. The learning rate progresses
- linearly from the initial value to the final value, both of which
- should be between 0 and 1. The learning rate should typically
- decrease, so the initial value should not exceed the final
- value.<br> <b>Default</b>: 0.8
- </blockquote>
- IN: <tt>double learning_constant_final</tt>
- <blockquote>
- The final learning rate constant.<br>
- <b>Default</b>: 0.2
- </blockquote>
- IN: <tt>VertexIndexMap vertex_index_map</tt>
- <blockquote>
- This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. This is only necessary when no
- displacement map is provided.
- The type <tt>VertexIndexMap</tt> must be a model of <a
- href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
- Map</a>. The value type of the map must be an integer type. The
- vertex descriptor type of the graph needs to be usable as the key
- type of the map.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt>
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.
- </blockquote>
- IN: <tt>EdgeWeightMap weight</tt>
- <blockquote>
- This maps each edge to a weight.
- The type <tt>EdgeWeightMap</tt> must be a model of <a
- href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
- Map</a>. The value type of the map must be an floating-point type
- compatible with <tt>double</tt>. The edge descriptor type of the
- graph needs to be usable as the key type of the map. When this map
- is a <tt>dummy_property_map</tt>, the algorithm assumes the graph is
- unweighted.<br>
- <b>Default:</b> <tt>dummy_property_map()</tt>
- </blockquote>
- <h3>Named Parameters</h3>
- IN: <tt>iterations(int n)</tt>
- <blockquote>
- Executes the algorithm for <em>n</em> iterations.<br>
- <b>Default:</b> <tt>num_vertices(g)</tt>
- </blockquote>
- IN: <tt>diameter_range(std::pair<T, T> range)</tt>
- <blockquote>
- Range specifying the parameters (<tt>diameter_initial</tt>, <tt>diameter_final</tt>). <br>
- <b>Default:</b> <tt>std::make_pair(sqrt((double)num_vertices(g)), 1.0)</tt>
- </blockquote>
- IN: <tt>learning_constant_range(std::pair<T, T> range)</tt>
- <blockquote>
- Range specifying the parameters (<tt>learning_constant_initial</tt>, <tt>learning_constant_final</tt>). <br>
- <b>Default:</b> <tt>std::make_pair(0.8, 0.2)</tt>
- </blockquote>
- IN: <tt>edge_weight(EdgeWeightMap weight)</tt>
- <blockquote>
- Equivalent to the non-named <tt>weight</tt> parameter.<br>
- <b>Default:</b> <tt>dummy_property_map()</tt>
- </blockquote>
- IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
- <blockquote>
- Equivalent to the non-named <tt>vertex_index_map</tt> parameter.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt>
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.
- </blockquote>
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2004 Trustees of Indiana University</TD><TD>
- Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br>
- <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>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|