123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280 |
- <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>
|