281 lines
10 KiB
HTML
281 lines
10 KiB
HTML
<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 <a href="#convex_topology">convex_topology</a>;
|
|
template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand> class <a href="#hypercube_topology">hypercube_topology</a>;
|
|
template<typename RandomNumberGenerator = minstd_rand> class <a href="#square_topology">square_topology</a>;
|
|
template<typename RandomNumberGenerator = minstd_rand> class <a href="#cube_topology">cube_topology</a>;
|
|
template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand> class <a href="#ball_topology">ball_topology</a>;
|
|
template<typename RandomNumberGenerator = minstd_rand> class <a href="#circle_topology">circle_topology</a>;
|
|
template<typename RandomNumberGenerator = minstd_rand> class <a href="#sphere_topology">sphere_topology</a>;
|
|
template<typename RandomNumberGenerator = minstd_rand> class <a href="#heart_topology">heart_topology</a>;
|
|
</pre>
|
|
|
|
<h3>Summary</h3>
|
|
|
|
<p> <a href="#topologies">Various topologies</a> 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 <a href="#heart_topology">heart topology</a> 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 <a href="#topology-concept">Topology concept</a>.
|
|
|
|
<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 <a href="#convex_topology">convex_topology</a><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 <a href="#hypercube_topology">hypercube_topology</a><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 three-dimensional
|
|
hypercube topology.
|
|
|
|
<pre>
|
|
template<typename RandomNumberGenerator = minstd_rand>
|
|
class cube_topology : public <a href="#hypercube_topology">hypercube_topology</a><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 <a href="#convex_topology">convex_topology</a><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 <a href="#ball_topology">ball_topology</a><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 three-dimensional
|
|
ball topology.
|
|
|
|
<pre>
|
|
template<typename RandomNumberGenerator = minstd_rand>
|
|
class sphere_topology : public <a href="#ball_topology">ball_topology</a><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>
|
|
<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>
|