| <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 two-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 two-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="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> |