|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r61232 - trunk/libs/graph/doc
From: jewillco_at_[hidden]
Date: 2010-04-12 17:00:25
Author: jewillco
Date: 2010-04-12 17:00:24 EDT (Mon, 12 Apr 2010)
New Revision: 61232
URL: http://svn.boost.org/trac/boost/changeset/61232
Log:
Cleaned up BGL layout docs, split topology docs into separate file
Added:
trunk/libs/graph/doc/topology.html (contents, props changed)
Text files modified:
trunk/libs/graph/doc/fruchterman_reingold.html | 50 +++----
trunk/libs/graph/doc/gursoy_atun_layout.html | 250 ++-------------------------------------
trunk/libs/graph/doc/kamada_kawai_spring_layout.html | 41 ++++-
trunk/libs/graph/doc/random_layout.html | 49 ++-----
trunk/libs/graph/doc/table_of_contents.html | 1
5 files changed, 79 insertions(+), 312 deletions(-)
Modified: trunk/libs/graph/doc/fruchterman_reingold.html
==============================================================================
--- trunk/libs/graph/doc/fruchterman_reingold.html (original)
+++ trunk/libs/graph/doc/fruchterman_reingold.html 2010-04-12 17:00:24 EDT (Mon, 12 Apr 2010)
@@ -1,6 +1,6 @@
<HTML>
<!--
- Copyright (c) 2004 Trustees of Indiana University
+ Copyright (c) 2004, 2010 Trustees of Indiana University
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
@@ -23,36 +23,35 @@
<P>
<PRE>
<i>// named parameter version</i>
-template<typename Graph, typename PositionMap, typename Dim, typename Param,
+template<typename Graph, typename PositionMap, typename Topology, typename Param,
typename Tag, typename Rest>
void
fruchterman_reingold_force_directed_layout
- (const Graph& g,
+ (const Graph& g,
PositionMap position,
- Dim width,
- Dim height,
+ const Topology& space,
const bgl_named_params<Param, Tag, Rest>& params);
<i>// non-named parameter version</i>
-template<typename Graph, typename PositionMap, typename Dim,
+template<typename Graph, typename PositionMap, typename Topology,
typename AttractiveForce, typename RepulsiveForce,
typename ForcePairs, typename DisplacementMap, typename Cooling>
void
fruchterman_reingold_force_directed_layout
(const Graph& g,
PositionMap position,
- Dim width,
- Dim height,
+ const Topology& space,
AttractiveForce fa,
RepulsiveForce fr,
ForcePairs fp,
Cooling cool,
DisplacementMap displacement);
-template<typename Graph, typename PositionMap, typename Dim>
+template<typename Graph, typename PositionMap, typename Topology>
void
-fruchterman_reingold_force_directed_layout(const Graph& g,
+fruchterman_reingold_force_directed_layout(const Graph& g,
PositionMap position,
+ Topology& space,
Dim width,
Dim height);
</PRE>
@@ -98,26 +97,20 @@
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 a structure
- with fields <tt>x</tt> and <tt>y</tt>, representing the coordinates
+ convertible to its key type. Its value type must be
+ <tt>Topology::point_type</tt>, representing the coordinates
of the vertex.<br>
<b>Python</b>: The position map must be a <tt>vertex_point2d_map</tt> for
the graph.<br>
<b>Python default</b>: <tt>graph.get_vertex_point2d_map("position")</tt>
</blockquote>
-IN: <tt>Dim width</tt>
+IN: <tt>const Topology& space</tt>
<blockquote>
- The width of the display area in which layout should occur. On
- termination of the algorithm, the <tt>x</tt> coordinates of all
- vertices will fall in <tt>[-width/2, width/2]</tt>.
-</blockquote>
-
-IN: <tt>Dim height</tt>
-<blockquote>
- The height of the display area in which layout should occur. On
- termination of the algorithm, the <tt>y</tt> coordinates of all
- vertices will fall in <tt>[-height/2, height/2]</tt>.
+ The topology used to lay out the vertices. This parameter describes both the
+ size and shape of the layout area. Topologies are described in more detail
+ (with a list of BGL-provided topologies) <a href="topology.html">in separate
+ documentation</a>.
</blockquote>
<h3>Named Parameters</h3>
@@ -184,10 +177,11 @@
UTIL: <tt>displacement_map(DisplacementMap displacement)</tt>
<blockquote>
The displacement map is used to compute the amount by which each
-vertex will move in each step. The <tt>DisplacementMap</tt> type
-carries the same requirements as the <tt>PositionMap</tt> type.<br>
-<b>Default:</b> An <tt>iterator_property_map</tt> with a value type
-of <tt>simple_point<double></tt> and using the given vertex index map.<br>
+vertex will move in each step. The <tt>DisplacementMap</tt> type must be a
+property map whose key type is the graph's vertex type and whose value type is
+<tt>Topology::point_difference_type</tt>.<br>
+<b>Default:</b> An <tt>iterator_property_map</tt> with the specified value type
+and using the given vertex index map.<br>
<b>Python:</b> Unsupported parameter.
</blockquote>
@@ -233,7 +227,7 @@
<HR>
<TABLE>
<TR valign=top>
-<TD nowrap>Copyright © 2004</TD><TD>
+<TD nowrap>Copyright © 2004, 2010 Trustees of Indiana University</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University
</TD></TR></TABLE>
Modified: trunk/libs/graph/doc/gursoy_atun_layout.html
==============================================================================
--- trunk/libs/graph/doc/gursoy_atun_layout.html (original)
+++ trunk/libs/graph/doc/gursoy_atun_layout.html 2010-04-12 17:00:24 EDT (Mon, 12 Apr 2010)
@@ -28,6 +28,7 @@
<BR Clear>
+<H1>
<TT>gursoy_atun_layout</TT>
</H1>
@@ -59,16 +60,6 @@
const Topology& space,
PositionMap position,
const bgl_named_params<P,T,R>& params = <em>all defaults</em>);
-
-<em>// Topologies</em>
-template<std::size_t Dims> class convex_topology;
-template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand> class hypercube_topology;
-template<typename RandomNumberGenerator = minstd_rand> class square_topology;
-template<typename RandomNumberGenerator = minstd_rand> class cube_topology;
-template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand> class ball_topology;
-template<typename RandomNumberGenerator = minstd_rand> class circle_topology;
-template<typename RandomNumberGenerator = minstd_rand> class sphere_topology;
-template<typename RandomNumberGenerator = minstd_rand> class heart_topology;
</PRE>
<h3>Description</h3>
@@ -81,26 +72,18 @@
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. The algorithm itself is
+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> Various topologies are provided that
-produce different, interesting results. The <a
-href="#square_topology">square topology</a> can be used for normal
-display of graphs or distributing vertices for parallel computation on
-a process array, for instance. Other topologies, such as the <a
-href="#sphere_topology">sphere topology</a> (or N-dimensional <a
-href="#ball_topology">ball topology</a>) make sense for different
-problems, whereas the heart topology is
-just plain fun. One can also <a href="#topology-concept">define a
-topology</a> to suit other particular needs. <br>
-
-
-
-
-
+<p>
+
+
+
+</p>
<h3>Where Defined</h3>
@@ -118,8 +101,8 @@
IN: <tt>const Topology& space</tt>
<blockquote>
- The topology on which the graph will be layed out. The type must
- model the Topology concept.
+ The topology on which the graph will be laid out. The type must
+ model the Topology concept.
</blockquote>
OUT: <tt>PositionMap position</tt>
@@ -128,8 +111,8 @@
<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 the type of a
- point in the topology.
+ convertible to its key type. Its value type must be
+ <tt>Topology::point_type</tt>.
</blockquote>
IN: <tt>int nsteps</tt>
@@ -242,216 +225,11 @@
not have an internal <tt>vertex_index</tt> property.
</blockquote>
-<a name="topologies"><h3>Topologies</h3></a>
-A topology is a description of a space on which layout can be
-performed. Some common two, three, and multidimensional topologies
-are provided, or you may create your own so long as it meets the
-requirements of the Topology concept.
-
-<a name="topology-concept"><h4>Topology Concept</h4></a> Let
-<tt>Topology</tt> be a model of the Topology concept and let
-<tt>space</tt> be an object of type <tt>Topology</tt>. <tt>p1</tt> and
-<tt>p2</tt> are objects of associated type <tt>point_type</tt> (see
-below). The following expressions must be valid:
-
-<table border="1">
- <tr>
- <th>Expression</th>
- <th>Type</th>
- <th>Description</th>
- </tr>
- <tr>
- <td><tt>Topology::point_type</tt></td>
- <td>type</td>
- <td>The type of points in the space.</td>
- </tr>
- <tr>
- <td><tt>space.random_point()</tt></td>
- <td>point_type</td>
- <td>Returns a random point (usually uniformly distributed) within
- the space.</td>
- </tr>
- <tr>
- <td><tt>space.distance(p1, p2)</tt></td>
- <td>double</td>
- <td>Get a quantity representing the distance between <tt>p1</tt>
- and <tt>p2</tt> using a path going completely inside the space.
- This only needs to have the same < relation as actual
- distances, and does not need to satisfy the other properties of a
- norm in a Banach space.</td>
- </tr>
- <tr>
- <td><tt>space.move_position_toward(p1, fraction, p2)</tt></td>
- <td>point_type</td>
- <td>Returns a point that is a fraction of the way from <tt>p1</tt>
- to <tt>p2</tt>, moving along a "line" in the space according to
- the distance measure. <tt>fraction</tt> is a <tt>double</tt>
- between 0 and 1, inclusive.</td>
- </tr>
-</table>
-
-<a name="convex_topology"><h3>Class template <tt>convex_topology</tt></h3></a>
-
-<p>Class template <tt>convex_topology</tt> implements the basic
-distance and point movement functions for any convex topology in
-<tt>Dims</tt> dimensions. It is not itself a topology, but is intended
-as a base class that any convex topology can derive from. The derived
-topology need only provide a suitable <tt>random_point</tt> function
-that returns a random point within the space.
-
-<pre>
-template<std::size_t Dims>
-class convex_topology
-{
- struct point
- {
- point() { }
- double& operator[](std::size_t i) {return values[i];}
- const double& operator[](std::size_t i) const {return values[i];}
-
- private:
- double values[Dims];
- };
-
- public:
- typedef point point_type;
-
- double distance(point a, point b) const;
- point move_position_toward(point a, double fraction, point b) const;
-};
-</pre>
-
-<a name="hypercube_topology"><h3>Class template <tt>hypercube_topology</tt></h3></a>
-
-<p>Class template <tt>hypercube_topology</tt> implements a
-<tt>Dims</tt>-dimensional hypercube. It is a convex topology whose
-points are drawn from a random number generator of type
-<tt>RandomNumberGenerator</tt>. The <tt>hypercube_topology</tt> can
-be constructed with a given random number generator; if omitted, a
-new, default-constructed random number generator will be used. The
-resulting layout will be contained within the hypercube, whose sides
-measure 2*<tt>scaling</tt> long (points will fall in the range
-[-<tt>scaling</tt>, <tt>scaling</tt>] in each dimension).
-
-<pre>
-template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand>
-class hypercube_topology : public convex_topology<Dims>
-{
-public:
- explicit hypercube_topology(double scaling = 1.0);
- hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0);
- point_type random_point() const;
-};
-</pre>
-
-<a name="square_topology"><h3>Class template <tt>square_topology</tt></h3></a>
-
-<p>Class template <tt>square_topology</tt> is a two-dimensional
-hypercube topology.
-
-<pre>
-template<typename RandomNumberGenerator = minstd_rand>
-class square_topology : public hypercube_topology<2, RandomNumberGenerator>
-{
- public:
- explicit square_topology(double scaling = 1.0);
- square_topology(RandomNumberGenerator& gen, double scaling = 1.0);
-};
-</pre>
-
-<a name="cube_topology"><h3>Class template <tt>cube_topology</tt></h3></a>
-
-<p>Class template <tt>cube_topology</tt> is a two-dimensional
-hypercube topology.
-
-<pre>
-template<typename RandomNumberGenerator = minstd_rand>
-class cube_topology : public hypercube_topology<3, RandomNumberGenerator>
-{
- public:
- explicit cube_topology(double scaling = 1.0);
- cube_topology(RandomNumberGenerator& gen, double scaling = 1.0);
-};
-</pre>
-
-<a name="ball_topology"><h3>Class template <tt>ball_topology</tt></h3></a>
-
-<p>Class template <tt>ball_topology</tt> implements a
-<tt>Dims</tt>-dimensional ball. It is a convex topology whose points
-are drawn from a random number generator of type
-<tt>RandomNumberGenerator</tt> but reside inside the ball. The
-<tt>ball_topology</tt> can be constructed with a given random number
-generator; if omitted, a new, default-constructed random number
-generator will be used. The resulting layout will be contained within
-the ball with the given <tt>radius</tt>.
-
-<pre>
-template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand>
-class ball_topology : public convex_topology<Dims>
-{
-public:
- explicit ball_topology(double radius = 1.0);
- ball_topology(RandomNumberGenerator& gen, double radius = 1.0);
- point_type random_point() const;
-};
-</pre>
-
-<a name="circle_topology"><h3>Class template <tt>circle_topology</tt></h3></a>
-
-<p>Class template <tt>circle_topology</tt> is a two-dimensional
-ball topology.
-
-<pre>
-template<typename RandomNumberGenerator = minstd_rand>
-class circle_topology : public ball_topology<2, RandomNumberGenerator>
-{
- public:
- explicit circle_topology(double radius = 1.0);
- circle_topology(RandomNumberGenerator& gen, double radius = 1.0);
-};
-</pre>
-
-<a name="sphere_topology"><h3>Class template <tt>sphere_topology</tt></h3></a>
-
-<p>Class template <tt>sphere_topology</tt> is a two-dimensional
-ball topology.
-
-<pre>
-template<typename RandomNumberGenerator = minstd_rand>
-class sphere_topology : public ball_topology<3, RandomNumberGenerator>
-{
- public:
- explicit sphere_topology(double radius = 1.0);
- sphere_topology(RandomNumberGenerator& gen, double radius = 1.0);
-};
-</pre>
-
-<a name="heart_topology"><h3>Class template <tt>heart_topology</tt></h3></a>
-
-<p>Class template <tt>heart_topology</tt> is topology in the shape of
-a heart. It serves as an example of a non-convex, nontrivial topology
-for layout.
-
-<pre>
-template<typename RandomNumberGenerator = minstd_rand>
-class heart_topology
-{
- public:
- typedef <em>unspecified</em> point_type;
-
- heart_topology();
- heart_topology(RandomNumberGenerator& gen);
- point_type random_point() const;
- double distance(point_type a, point_type b) const;
- point_type move_position_toward(point_type a, double fraction, point_type b) const;
-};
-</pre>
-
<br>
<HR>
<TABLE>
<TR valign=top>
-<TD nowrap>Copyright © 2004</TD><TD>
+<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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
Modified: trunk/libs/graph/doc/kamada_kawai_spring_layout.html
==============================================================================
--- trunk/libs/graph/doc/kamada_kawai_spring_layout.html (original)
+++ trunk/libs/graph/doc/kamada_kawai_spring_layout.html 2010-04-12 17:00:24 EDT (Mon, 12 Apr 2010)
@@ -1,7 +1,7 @@
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<!--
- Copyright (c) 2004 Trustees of Indiana University
+ Copyright (c) 2004, 2010 Trustees of Indiana University
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
@@ -46,6 +46,7 @@
"refsynopsisdiv">
<pre class="synopsis">
<span class="bold"><b>template</b></span><<span class=
+"bold"><b>typename</b></span> Topology, <span class=
"bold"><b>typename</b></span> Graph, <span class=
"bold"><b>typename</b></span> PositionMap, <span class=
"bold"><b>typename</b></span> WeightMap, <span class=
@@ -62,6 +63,7 @@
<span class="type"><span class=
"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position,
WeightMap weight,
+ <b>const</b> Topology& space,
<span class=
"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done,
<span class=
@@ -71,6 +73,7 @@
SpringStrengthMatrix spring_strength,
PartialDerivativeMap partial_derivatives);
<span class="bold"><b>template</b></span><<span class=
+"bold"><b>typename</b></span> Topology, <span class=
"bold"><b>typename</b></span> Graph, <span class=
"bold"><b>typename</b></span> PositionMap, <span class=
"bold"><b>typename</b></span> WeightMap, <span class=
@@ -82,12 +85,14 @@
<span class="type"><span class=
"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position,
WeightMap weight,
+ <b>const</b> Topology& space,
<span class=
"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done,
<span class=
"bold"><b>typename</b></span> property_traits< WeightMap >::value_type spring_constant,
VertexIndexMap index);
<span class="bold"><b>template</b></span><<span class=
+"bold"><b>typename</b></span> Topology, <span class=
"bold"><b>typename</b></span> Graph, <span class=
"bold"><b>typename</b></span> PositionMap, <span class=
"bold"><b>typename</b></span> WeightMap, <span class=
@@ -98,11 +103,13 @@
<span class="type"><span class=
"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position,
WeightMap weight,
+ <b>const</b> Topology& space,
<span class=
"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done,
<span class=
"bold"><b>typename</b></span> property_traits< WeightMap >::value_type spring_constant = typename property_traits< WeightMap >::value_type(1));
<span class="bold"><b>template</b></span><<span class=
+"bold"><b>typename</b></span> Topology, <span class=
"bold"><b>typename</b></span> Graph, <span class=
"bold"><b>typename</b></span> PositionMap, <span class=
"bold"><b>typename</b></span> WeightMap, <span class=
@@ -112,6 +119,7 @@
<span class="type"><span class=
"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position,
WeightMap weight,
+ <b>const</b> Topology& space,
<span class=
"emphasis"><em>unspecified</em></span> edge_or_side_length);
</pre></div>
@@ -158,7 +166,8 @@
This property map is used to store the position of each vertex. The
type <tt>PositionMap</tt> must be a model of <a
href="../../property_map/doc/WritablePropertyMap.html">Writable Property
- Map</a>, with the graph's vertex descriptor type as its key type.<br>
+ Map</a>, with the graph's vertex descriptor type as its key type and
+ <tt>Topology::point_type</tt> as its value type.<br>
<b>Python</b>: The position map must be a <tt>vertex_point2d_map</tt> for
the graph.<br>
@@ -182,6 +191,16 @@
<b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt>
</blockquote>
+IN: <tt>const Topology& space</tt>
+<blockquote>
+The topology used to lay out the vertices. This parameter describes both the
+size and shape of the layout area, as well as its dimensionality; up to three
+dimensions are supported by the current implementation. Topologies are
+described in more detail
+(with a list of BGL-provided topologies) <a href="topology.html">in separate
+documentation</a>.
+</blockquote>
+
IN: <tt>EdgeOrSideLength edge_or_side_length</tt>
<blockquote>
Provides either the unit length <tt class= "computeroutput">e</tt> of
@@ -257,17 +276,15 @@
UTIL: <tt>PartialDerivativeMap partial_derivatives</tt>
<blockquote>
-A property map that will be used to store the partial derivates of
-each vertex with respect to the <tt class="computeroutput">x</tt> and
-<tt class="computeroutput">y</tt> coordinates. This must be a
+A property map that will be used to store the partial derivatives of
+each vertex with respect to the vertex's current coordinates.
+coordinates. This must be a
<a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
-Property Map</a> whose value type is a pair with both types equivalent
-to the value type of the weight map. The default is an iterator
-property map.<br>
+Property Map</a> whose value type is <tt>Topology::point_difference_type</tt>.
+The default is an iterator property map built using the graph's vertex index
+map.<br>
<b>Default</b>: An <tt>iterator_property_map</tt> created from
-an <tt>std::vector</tt> of <tt>std::pair<weight_type,
- weight_type></tt>, where <tt>weight_type</tt> is the value type of
-the <tt>WeightMap</tt>.<br>
+an <tt>std::vector</tt> of <tt>Topology::point_difference_type</tt>.<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
@@ -294,7 +311,7 @@
<hr>
<table>
<tr valign="top">
-<td nowrap>Copyright © 2004</td>
+<td nowrap>Copyright © 2004, 2010 Trustees of Indiana University</td>
<td>Douglas Gregor,
Indiana University (dgregor -at cs.indiana.edu)<br>
<a href="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</a>, Indiana
Modified: trunk/libs/graph/doc/random_layout.html
==============================================================================
--- trunk/libs/graph/doc/random_layout.html (original)
+++ trunk/libs/graph/doc/random_layout.html 2010-04-12 17:00:24 EDT (Mon, 12 Apr 2010)
@@ -1,6 +1,6 @@
<HTML>
<!--
- Copyright (c) 2005 Trustees of Indiana University
+ Copyright (c) 2005, 2010 Trustees of Indiana University
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
@@ -22,17 +22,14 @@
<P>
<PRE>
<i>// non-named parameter version</i>
-template<typename Graph, typename PositionMap, typename Dimension,
- typename RandomNumberGenerator>
+template<typename Graph, typename PositionMap, typename Topology>
void
random_graph_layout(const Graph& g, PositionMap position_map,
- Dimension minX, Dimension maxX,
- Dimension minY, Dimension maxY,
- RandomNumberGenerator& gen);
+ const Topology& space);
</PRE>
<P> This algorithm places the points of the graph at random
-locations. </p>
+locations within a given space. </p>
<h3>Where Defined</h3>
@@ -53,37 +50,17 @@
<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 a structure with
- fields <tt>x</tt> and <tt>y</tt>, representing the coordinates of
- the vertex.
+ convertible to its key type. Its value type must be
+ <tt>Topology::point_type</tt>, representing the coordinates of the vertex.
</blockquote>
-IN: <tt>Dimension minX</tt>
+IN: <tt>const Topology& space</tt>
<blockquote>
- The minimum <tt>x</tt> coordinate.
-</blockquote>
-
-IN: <tt>Dimension maxX</tt>
-<blockquote>
- The maximum <tt>x</tt> coordinate.
-</blockquote>
-
-IN: <tt>Dimension minY</tt>
-<blockquote>
- The minimum <tt>y</tt> coordinate.
-</blockquote>
-
-IN: <tt>Dimension maxY</tt>
-<blockquote>
- The maximum <tt>y</tt> coordinate.
-</blockquote>
-
-IN/UTIL: <tt>RandomNumberGenerator& gen</tt>
-<blockquote>
-A random number generator that will be used to place vertices. The
-type <tt>RandomNumberGenerator</tt> must model the <a
-href="../../random/doc/html/boost_random/reference.html#boost_random.reference.concepts.number_generator">NumberGenerator</a>
-concept.
+ The topology used to lay out the vertices. This parameter describes both the
+ size and shape of the layout area and provides a random number generator used
+ to create random positions within the space. Topologies are described in
+ more detail (with a list of BGL-provided topologies) <a
+ href="topology.html">in separate documentation</a>.
</blockquote>
<H3>Complexity</H3>
@@ -93,7 +70,7 @@
<HR>
<TABLE>
<TR valign=top>
-<TD nowrap>Copyright © 2004</TD><TD>
+<TD nowrap>Copyright © 2004, 2010</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University
</TD></TR></TABLE>
Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html 2010-04-12 17:00:24 EDT (Mon, 12 Apr 2010)
@@ -227,6 +227,7 @@
<li>Layout Algorithms
<ol>
+ <li>Topologies used as spaces for graph drawing</li>
<li>random_graph_layout</li>
<li>circle_layout</li>
<li>kamada_kawai_spring_layout</li>
Added: trunk/libs/graph/doc/topology.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/topology.html 2010-04-12 17:00:24 EDT (Mon, 12 Apr 2010)
@@ -0,0 +1,280 @@
+<HTML>
+<!--
+ Copyright (c) 2004, 2010 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: Topologies for Graph Drawing</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>
+Topologies for Graph Drawing
+</H1>
+
+<P>
+
+<h3>Synopsis</h3>
+
+<pre>
+template<std::size_t Dims> class convex_topology;
+template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand> class hypercube_topology;
+template<typename RandomNumberGenerator = minstd_rand> class square_topology;
+template<typename RandomNumberGenerator = minstd_rand> class cube_topology;
+template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand> class ball_topology;
+template<typename RandomNumberGenerator = minstd_rand> class circle_topology;
+template<typename RandomNumberGenerator = minstd_rand> class sphere_topology;
+template<typename RandomNumberGenerator = minstd_rand> class heart_topology;
+</pre>
+
+<h3>Summary</h3>
+
+<p> Various topologies are provided that
+produce different, interesting results for graph layout algorithms. The <a
+href="#square_topology">square topology</a> can be used for normal
+display of graphs or distributing vertices for parallel computation on
+a process array, for instance. Other topologies, such as the <a
+href="#sphere_topology">sphere topology</a> (or N-dimensional <a
+href="#ball_topology">ball topology</a>) make sense for different
+problems, whereas the heart topology is
+just plain fun. One can also <a href="#topology-concept">define a
+topology</a> to suit other particular needs. <br>
+
+<a name="topologies"><h3>Topologies</h3></a>
+A topology is a description of a space on which layout can be
+performed. Some common two, three, and multidimensional topologies
+are provided, or you may create your own so long as it meets the
+requirements of the Topology concept.
+
+<a name="topology-concept"><h4>Topology Concept</h4></a> Let
+<tt>Topology</tt> be a model of the Topology concept and let
+<tt>space</tt> be an object of type <tt>Topology</tt>. <tt>p1</tt> and
+<tt>p2</tt> are objects of associated type <tt>point_type</tt> (see
+below). The following expressions must be valid:
+
+<table border="1">
+ <tr>
+ <th>Expression</th>
+ <th>Type</th>
+ <th>Description</th>
+ </tr>
+ <tr>
+ <td><tt>Topology::point_type</tt></td>
+ <td>type</td>
+ <td>The type of points in the space.</td>
+ </tr>
+ <tr>
+ <td><tt>space.random_point()</tt></td>
+ <td>point_type</td>
+ <td>Returns a random point (usually uniformly distributed) within
+ the space.</td>
+ </tr>
+ <tr>
+ <td><tt>space.distance(p1, p2)</tt></td>
+ <td>double</td>
+ <td>Get a quantity representing the distance between <tt>p1</tt>
+ and <tt>p2</tt> using a path going completely inside the space.
+ This only needs to have the same < relation as actual
+ distances, and does not need to satisfy the other properties of a
+ norm in a Banach space.</td>
+ </tr>
+ <tr>
+ <td><tt>space.move_position_toward(p1, fraction, p2)</tt></td>
+ <td>point_type</td>
+ <td>Returns a point that is a fraction of the way from <tt>p1</tt>
+ to <tt>p2</tt>, moving along a "line" in the space according to
+ the distance measure. <tt>fraction</tt> is a <tt>double</tt>
+ between 0 and 1, inclusive.</td>
+ </tr>
+</table>
+
+<a name="convex_topology"><h3>Class template <tt>convex_topology</tt></h3></a>
+
+<p>Class template <tt>convex_topology</tt> implements the basic
+distance and point movement functions for any convex topology in
+<tt>Dims</tt> dimensions. It is not itself a topology, but is intended
+as a base class that any convex topology can derive from. The derived
+topology need only provide a suitable <tt>random_point</tt> function
+that returns a random point within the space.
+
+<pre>
+template<std::size_t Dims>
+class convex_topology
+{
+ struct point
+ {
+ point() { }
+ double& operator[](std::size_t i) {return values[i];}
+ const double& operator[](std::size_t i) const {return values[i];}
+
+ private:
+ double values[Dims];
+ };
+
+ public:
+ typedef point point_type;
+
+ double distance(point a, point b) const;
+ point move_position_toward(point a, double fraction, point b) const;
+};
+</pre>
+
+<a name="hypercube_topology"><h3>Class template <tt>hypercube_topology</tt></h3></a>
+
+<p>Class template <tt>hypercube_topology</tt> implements a
+<tt>Dims</tt>-dimensional hypercube. It is a convex topology whose
+points are drawn from a random number generator of type
+<tt>RandomNumberGenerator</tt>. The <tt>hypercube_topology</tt> can
+be constructed with a given random number generator; if omitted, a
+new, default-constructed random number generator will be used. The
+resulting layout will be contained within the hypercube, whose sides
+measure 2*<tt>scaling</tt> long (points will fall in the range
+[-<tt>scaling</tt>, <tt>scaling</tt>] in each dimension).
+
+<pre>
+template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand>
+class hypercube_topology : public convex_topology<Dims>
+{
+public:
+ explicit hypercube_topology(double scaling = 1.0);
+ hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0);
+ point_type random_point() const;
+};
+</pre>
+
+<a name="square_topology"><h3>Class template <tt>square_topology</tt></h3></a>
+
+<p>Class template <tt>square_topology</tt> is a two-dimensional
+hypercube topology.
+
+<pre>
+template<typename RandomNumberGenerator = minstd_rand>
+class square_topology : public hypercube_topology<2, RandomNumberGenerator>
+{
+ public:
+ explicit square_topology(double scaling = 1.0);
+ square_topology(RandomNumberGenerator& gen, double scaling = 1.0);
+};
+</pre>
+
+<a name="cube_topology"><h3>Class template <tt>cube_topology</tt></h3></a>
+
+<p>Class template <tt>cube_topology</tt> is a two-dimensional
+hypercube topology.
+
+<pre>
+template<typename RandomNumberGenerator = minstd_rand>
+class cube_topology : public hypercube_topology<3, RandomNumberGenerator>
+{
+ public:
+ explicit cube_topology(double scaling = 1.0);
+ cube_topology(RandomNumberGenerator& gen, double scaling = 1.0);
+};
+</pre>
+
+<a name="ball_topology"><h3>Class template <tt>ball_topology</tt></h3></a>
+
+<p>Class template <tt>ball_topology</tt> implements a
+<tt>Dims</tt>-dimensional ball. It is a convex topology whose points
+are drawn from a random number generator of type
+<tt>RandomNumberGenerator</tt> but reside inside the ball. The
+<tt>ball_topology</tt> can be constructed with a given random number
+generator; if omitted, a new, default-constructed random number
+generator will be used. The resulting layout will be contained within
+the ball with the given <tt>radius</tt>.
+
+<pre>
+template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand>
+class ball_topology : public convex_topology<Dims>
+{
+public:
+ explicit ball_topology(double radius = 1.0);
+ ball_topology(RandomNumberGenerator& gen, double radius = 1.0);
+ point_type random_point() const;
+};
+</pre>
+
+<a name="circle_topology"><h3>Class template <tt>circle_topology</tt></h3></a>
+
+<p>Class template <tt>circle_topology</tt> is a two-dimensional
+ball topology.
+
+<pre>
+template<typename RandomNumberGenerator = minstd_rand>
+class circle_topology : public ball_topology<2, RandomNumberGenerator>
+{
+ public:
+ explicit circle_topology(double radius = 1.0);
+ circle_topology(RandomNumberGenerator& gen, double radius = 1.0);
+};
+</pre>
+
+<a name="sphere_topology"><h3>Class template <tt>sphere_topology</tt></h3></a>
+
+<p>Class template <tt>sphere_topology</tt> is a two-dimensional
+ball topology.
+
+<pre>
+template<typename RandomNumberGenerator = minstd_rand>
+class sphere_topology : public ball_topology<3, RandomNumberGenerator>
+{
+ public:
+ explicit sphere_topology(double radius = 1.0);
+ sphere_topology(RandomNumberGenerator& gen, double radius = 1.0);
+};
+</pre>
+
+<a name="heart_topology"><h3>Class template <tt>heart_topology</tt></h3></a>
+
+<p>Class template <tt>heart_topology</tt> is topology in the shape of
+a heart. It serves as an example of a non-convex, nontrivial topology
+for layout.
+
+<pre>
+template<typename RandomNumberGenerator = minstd_rand>
+class heart_topology
+{
+ public:
+ typedef <em>unspecified</em> point_type;
+
+ heart_topology();
+ heart_topology(RandomNumberGenerator& gen);
+ point_type random_point() const;
+ double distance(point_type a, point_type b) const;
+ point_type move_position_toward(point_type a, double fraction, point_type b) const;
+};
+</pre>
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2004, 2010 Trustees of Indiana University</TD><TD>
+Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br>
+Doug Gregor, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
+ Andrew Lumsdaine,
+Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk