Author: jewillco
Date: 2010-04-12 17:08:02 EDT (Mon, 12 Apr 2010)
New Revision: 61233
URL: http://svn.boost.org/trac/boost/changeset/61233
Log:
Merged r61231 and r61232 from trunk
Added:
branches/release/libs/graph/doc/topology.html
- copied unchanged from r61232, /trunk/libs/graph/doc/topology.html
Properties modified:
branches/release/ (props changed)
branches/release/CMakeLists.txt (props changed)
branches/release/INSTALL (props changed)
branches/release/Jamroot (props changed)
branches/release/LICENSE_1_0.txt (props changed)
branches/release/boost/ (props changed)
branches/release/boost-build.jam (props changed)
branches/release/boost.css (props changed)
branches/release/boost.png (props changed)
branches/release/boost/algorithm/string/ (props changed)
branches/release/boost/archive/ (props changed)
branches/release/boost/array.hpp (props changed)
branches/release/boost/bimap/ (props changed)
branches/release/boost/config/ (props changed)
branches/release/boost/detail/ (props changed)
branches/release/boost/filesystem/ (props changed)
branches/release/boost/functional/hash/ (props changed)
branches/release/boost/fusion/ (props changed)
branches/release/boost/graph/ (props changed)
branches/release/boost/integer/ (props changed)
branches/release/boost/interprocess/ (props changed)
branches/release/boost/intrusive/ (props changed)
branches/release/boost/iostreams/ (props changed)
branches/release/boost/math/ (props changed)
branches/release/boost/numeric/ublas/ (props changed)
branches/release/boost/program_options/ (props changed)
branches/release/boost/property_tree/ (props changed)
branches/release/boost/python/ (props changed)
branches/release/boost/range/ (props changed)
branches/release/boost/regex/ (props changed)
branches/release/boost/serialization/ (props changed)
branches/release/boost/serialization/factory.hpp (props changed)
branches/release/boost/signals/ (props changed)
branches/release/boost/signals2/ (props changed)
branches/release/boost/spirit/ (props changed)
branches/release/boost/spirit/home/ (props changed)
branches/release/boost/spirit/home/karma/ (props changed)
branches/release/boost/spirit/home/support/attributes.hpp (props changed)
branches/release/boost/statechart/ (props changed)
branches/release/boost/system/ (props changed)
branches/release/boost/thread/ (props changed)
branches/release/boost/thread.hpp (props changed)
branches/release/boost/tr1/ (props changed)
branches/release/boost/type_traits/ (props changed)
branches/release/boost/unordered/ (props changed)
branches/release/boost/utility/ (props changed)
branches/release/boost/utility/value_init.hpp (props changed)
branches/release/boost/uuid/ (props changed)
branches/release/boost/variant/ (props changed)
branches/release/boost/version.hpp (props changed)
branches/release/boost/wave/ (props changed)
branches/release/bootstrap.bat (props changed)
branches/release/bootstrap.sh (props changed)
branches/release/doc/ (props changed)
branches/release/index.htm (props changed)
branches/release/index.html (props changed)
branches/release/libs/ (props changed)
branches/release/libs/array/doc/array.xml (props changed)
branches/release/libs/array/test/array0.cpp (props changed)
branches/release/libs/bimap/ (props changed)
branches/release/libs/config/ (props changed)
branches/release/libs/filesystem/ (props changed)
branches/release/libs/functional/hash/ (props changed)
branches/release/libs/fusion/ (props changed)
branches/release/libs/graph_parallel/ (props changed)
branches/release/libs/integer/ (props changed)
branches/release/libs/interprocess/ (props changed)
branches/release/libs/intrusive/ (props changed)
branches/release/libs/iostreams/ (props changed)
branches/release/libs/libraries.htm (props changed)
branches/release/libs/maintainers.txt (props changed)
branches/release/libs/math/ (props changed)
branches/release/libs/math/doc/sf_and_dist/ (props changed)
branches/release/libs/mpl/doc/refmanual/broken-compiler-workarounds.html (props changed)
branches/release/libs/mpl/doc/refmanual/categorized-index-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/cfg-no-preprocessed-headers.html (props changed)
branches/release/libs/mpl/doc/refmanual/composition-and-argument-binding.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-miscellaneous.html (props changed)
branches/release/libs/mpl/doc/refmanual/extensible-associative-sequence.html (props changed)
branches/release/libs/mpl/doc/refmanual/inserter-class.html (props changed)
branches/release/libs/mpl/doc/refmanual/tag-dispatched-metafunction.html (props changed)
branches/release/libs/mpl/doc/refmanual/trivial-metafunctions-summary.html (props changed)
branches/release/libs/mpl/doc/src/refmanual/Iterators-Iterator.rst (props changed)
branches/release/libs/numeric/ublas/ (props changed)
branches/release/libs/numeric/ublas/doc/ (props changed)
branches/release/libs/program_options/ (props changed)
branches/release/libs/property_tree/ (props changed)
branches/release/libs/python/ (props changed)
branches/release/libs/range/ (props changed)
branches/release/libs/regex/ (props changed)
branches/release/libs/regex/doc/ (props changed)
branches/release/libs/serialization/ (props changed)
branches/release/libs/signals/ (props changed)
branches/release/libs/signals2/ (props changed)
branches/release/libs/spirit/ (props changed)
branches/release/libs/spirit/classic/example/ (props changed)
branches/release/libs/spirit/doc/ (props changed)
branches/release/libs/spirit/example/ (props changed)
branches/release/libs/spirit/phoenix/ (props changed)
branches/release/libs/spirit/test/ (props changed)
branches/release/libs/spirit/test/qi/optional.cpp (props changed)
branches/release/libs/statechart/ (props changed)
branches/release/libs/static_assert/ (props changed)
branches/release/libs/system/ (props changed)
branches/release/libs/thread/ (props changed)
branches/release/libs/timer/ (props changed)
branches/release/libs/tr1/ (props changed)
branches/release/libs/type_traits/ (props changed)
branches/release/libs/unordered/ (props changed)
branches/release/libs/utility/ (props changed)
branches/release/libs/utility/swap.html (props changed)
branches/release/libs/utility/swap/test/std_bitset.cpp (props changed)
branches/release/libs/utility/value_init.htm (props changed)
branches/release/libs/utility/value_init_test.cpp (props changed)
branches/release/libs/uuid/ (props changed)
branches/release/libs/wave/ (props changed)
branches/release/more/ (props changed)
branches/release/people/ (props changed)
branches/release/rst.css (props changed)
branches/release/status/ (props changed)
branches/release/status/Jamfile.v2 (props changed)
branches/release/tools/ (props changed)
branches/release/tools/bcp/ (props changed)
branches/release/tools/boostbook/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/inspect/ (props changed)
branches/release/tools/quickbook/ (props changed)
branches/release/tools/regression/ (props changed)
branches/release/tools/release/ (props changed)
branches/release/tools/wave/ (props changed)
branches/release/wiki/ (props changed)
Text files modified:
branches/release/libs/graph/doc/fruchterman_reingold.html | 50 +++----
branches/release/libs/graph/doc/gursoy_atun_layout.html | 250 ++-------------------------------------
branches/release/libs/graph/doc/kamada_kawai_spring_layout.html | 41 ++++-
branches/release/libs/graph/doc/random_layout.html | 49 ++-----
branches/release/libs/graph/doc/table_of_contents.html | 1
branches/release/libs/graph/example/Jamfile.v2 | 1
branches/release/libs/graph/example/fr_layout.cpp | 14 +
7 files changed, 89 insertions(+), 317 deletions(-)
Modified: branches/release/libs/graph/doc/fruchterman_reingold.html
==============================================================================
--- branches/release/libs/graph/doc/fruchterman_reingold.html (original)
+++ branches/release/libs/graph/doc/fruchterman_reingold.html 2010-04-12 17:08:02 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: branches/release/libs/graph/doc/gursoy_atun_layout.html
==============================================================================
--- branches/release/libs/graph/doc/gursoy_atun_layout.html (original)
+++ branches/release/libs/graph/doc/gursoy_atun_layout.html 2010-04-12 17:08:02 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: branches/release/libs/graph/doc/kamada_kawai_spring_layout.html
==============================================================================
--- branches/release/libs/graph/doc/kamada_kawai_spring_layout.html (original)
+++ branches/release/libs/graph/doc/kamada_kawai_spring_layout.html 2010-04-12 17:08:02 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: branches/release/libs/graph/doc/random_layout.html
==============================================================================
--- branches/release/libs/graph/doc/random_layout.html (original)
+++ branches/release/libs/graph/doc/random_layout.html 2010-04-12 17:08:02 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: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2010-04-12 17:08:02 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>
Modified: branches/release/libs/graph/example/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/example/Jamfile.v2 (original)
+++ branches/release/libs/graph/example/Jamfile.v2 2010-04-12 17:08:02 EDT (Mon, 12 Apr 2010)
@@ -21,3 +21,4 @@
exe mcgregor_subgraphs_example : mcgregor_subgraphs_example.cpp ;
exe grid_graph_example : grid_graph_example.cpp ;
exe bipartite_example : bipartite_example.cpp ;
+exe fr_layout : fr_layout.cpp ;
Modified: branches/release/libs/graph/example/fr_layout.cpp
==============================================================================
--- branches/release/libs/graph/example/fr_layout.cpp (original)
+++ branches/release/libs/graph/example/fr_layout.cpp 2010-04-12 17:08:02 EDT (Mon, 12 Apr 2010)
@@ -9,7 +9,7 @@
#include <boost/graph/fruchterman_reingold.hpp>
#include <boost/graph/random_layout.hpp>
#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/simple_point.hpp>
+#include <boost/graph/topology.hpp>
#include <boost/lexical_cast.hpp>
#include <string>
#include <iostream>
@@ -37,6 +37,9 @@
<< " Vertices and their positions are written to standard output with the label,\n x-position, and y-position of a vertex on each line, separated by spaces.\n";
}
+typedef boost::rectangle_topology<> topology_type;
+typedef topology_type::point_type point_type;
+
typedef adjacency_list<listS, vecS, undirectedS,
property<vertex_name_t, std::string> > Graph;
@@ -110,7 +113,7 @@
add_edge(get_vertex(source, g, names), get_vertex(target, g, names), g);
}
- typedef std::vector<simple_point<double> > PositionVec;
+ typedef std::vector<point_type> PositionVec;
PositionVec position_vec(num_vertices(g));
typedef iterator_property_map<PositionVec::iterator,
property_map<Graph, vertex_index_t>::type>
@@ -118,15 +121,16 @@
PositionMap position(position_vec.begin(), get(vertex_index, g));
minstd_rand gen;
- random_graph_layout(g, position, -width/2, width/2, -height/2, height/2, gen);
+ topology_type topo(gen, -width/2, -height/2, width/2, height/2);
+ random_graph_layout(g, position, topo);
fruchterman_reingold_force_directed_layout
- (g, position, width, height,
+ (g, position, topo,
cooling(progress_cooling(iterations)));
graph_traits<Graph>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
std::cout << get(vertex_name, g, *vi) << '\t'
- << position[*vi].x << '\t' << position[*vi].y << std::endl;
+ << position[*vi][0] << '\t' << position[*vi][1] << std::endl;
}
return 0;
}