[ceph.git] / ceph / src / boost / libs / graph / doc / gursoy_atun_layout.html

<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&uuml;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&lt;typename VertexListAndIncidenceGraph,  typename Topology,
	 typename PositionMap, typename VertexIndexMap, 
         typename EdgeWeightMap&gt;
void
gursoy_atun_layout(const VertexListAndIncidenceGraph&amp; g,
                   const Topology&amp; 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&lt;typename VertexListAndIncidenceGraph, typename Topology,
         typename PositionMap, typename P, typename T, typename R&gt;
void 
gursoy_atun_layout(const VertexListAndIncidenceGraph&amp; g,  
                   const Topology&amp; space,
                   PositionMap position,
                   const bgl_named_params&lt;P,T,R&gt;&amp; params = <em>all defaults</em>);
</PRE>

<h3>Description</h3>

<P> This algorithm&nbsp;[<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&amp; 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&amp; 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 &copy; 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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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	<!--
	13	function 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>
	40	template<typename VertexListAndIncidenceGraph, typename Topology,
	41	typename PositionMap, typename VertexIndexMap,
	42	typename EdgeWeightMap>
	43	void
	44	gursoy_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>
	56	template<typename VertexListAndIncidenceGraph, typename Topology,
	57	typename PositionMap, typename P, typename T, typename R>
	58	void
	59	gursoy_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>]
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
77	algorithm itself is
78	based on <a
79	href="http://davis.wpi.edu/~matt/courses/soms/">Self-Organizing
80	Maps</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
94	IN: <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
102	IN: <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
108	OUT: <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
118	IN: <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
124	IN: <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
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>
137	</blockquote>
138
139	IN: <tt>double diameter_final</tt>
140	<blockquote>
141	The final value of the diameter.<br>
142	<b>Default</b>: 1.0
143	</blockquote>
144
145	IN: <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
155	IN: <tt>double learning_constant_final</tt>
156	<blockquote>
157	The final learning rate constant.<br>
158	<b>Default</b>: 0.2
159	</blockquote>
160
161	IN: <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
178	IN: <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
193	IN: <tt>iterations(int n)</tt>
194	<blockquote>
195	Executes the algorithm for <em>n</em> iterations.<br>
196	<b>Default:</b> <tt>num_vertices(g)</tt>
197	</blockquote>
198
199	IN: <tt>diameter_range(std::pair<T, T> range)</tt>
200	<blockquote>
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>
203	</blockquote>
204
205	IN: <tt>learning_constant_range(std::pair<T, T> range)</tt>
206	<blockquote>
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>
209	</blockquote>
210
211	IN: <tt>edge_weight(EdgeWeightMap weight)</tt>
212	<blockquote>
213	Equivalent to the non-named <tt>weight</tt> parameter.<br>
214	<b>Default:</b> <tt>dummy_property_map()</tt>
215	</blockquote>
216
217	IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
218	<blockquote>
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.
225	</blockquote>
226
227	<br>
228	<HR>
229	<TABLE>
230	<TR valign=top>
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>)
236	</TD></TR></TABLE>
237
238	</BODY>
239	</HTML>