3 Copyright (c) 2004, 2010 Trustees of Indiana University
5 Distributed under the Boost Software License, Version 1.0.
6 (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
10 <Title>Boost Graph Library: Topologies for Graph Drawing
</Title>
11 <script language=
"JavaScript" type=
"text/JavaScript">
13 function address(host, user) {
15 var thingy = user+atchar+host;
16 thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
17 document.write(thingy);
24 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
26 <IMG SRC=
"../../../boost.png"
27 ALT=
"C++ Boost" width=
"277" height=
"86">
32 Topologies for Graph Drawing
40 template
<std::size_t Dims
> class
<a href=
"#convex_topology">convex_topology
</a>;
41 template
<std::size_t Dims, typename RandomNumberGenerator = minstd_rand
> class
<a href=
"#hypercube_topology">hypercube_topology
</a>;
42 template
<typename RandomNumberGenerator = minstd_rand
> class
<a href=
"#square_topology">square_topology
</a>;
43 template
<typename RandomNumberGenerator = minstd_rand
> class
<a href=
"#cube_topology">cube_topology
</a>;
44 template
<std::size_t Dims, typename RandomNumberGenerator = minstd_rand
> class
<a href=
"#ball_topology">ball_topology
</a>;
45 template
<typename RandomNumberGenerator = minstd_rand
> class
<a href=
"#circle_topology">circle_topology
</a>;
46 template
<typename RandomNumberGenerator = minstd_rand
> class
<a href=
"#sphere_topology">sphere_topology
</a>;
47 template
<typename RandomNumberGenerator = minstd_rand
> class
<a href=
"#heart_topology">heart_topology
</a>;
52 <p> <a href=
"#topologies">Various topologies
</a> are provided that
53 produce different, interesting results for graph layout algorithms. The
<a
54 href=
"#square_topology">square topology
</a> can be used for normal
55 display of graphs or distributing vertices for parallel computation on
56 a process array, for instance. Other topologies, such as the
<a
57 href=
"#sphere_topology">sphere topology
</a> (or N-dimensional
<a
58 href=
"#ball_topology">ball topology
</a>) make sense for different
59 problems, whereas the
<a href=
"#heart_topology">heart topology
</a> is
60 just plain fun. One can also
<a href=
"#topology-concept">define a
61 topology
</a> to suit other particular needs.
<br>
63 <a name=
"topologies"><h3>Topologies
</h3></a>
64 A topology is a description of a space on which layout can be
65 performed. Some common two, three, and multidimensional topologies
66 are provided, or you may create your own so long as it meets the
67 requirements of the
<a href=
"#topology-concept">Topology concept
</a>.
69 <a name=
"topology-concept"><h4>Topology Concept
</h4></a> Let
70 <tt>Topology
</tt> be a model of the Topology concept and let
71 <tt>space
</tt> be an object of type
<tt>Topology
</tt>.
<tt>p1
</tt> and
72 <tt>p2
</tt> are objects of associated type
<tt>point_type
</tt> (see
73 below). The following expressions must be valid:
82 <td><tt>Topology::point_type
</tt></td>
84 <td>The type of points in the space.
</td>
87 <td><tt>space.random_point()
</tt></td>
89 <td>Returns a random point (usually uniformly distributed) within
93 <td><tt>space.distance(p1, p2)
</tt></td>
95 <td>Get a quantity representing the distance between
<tt>p1
</tt>
96 and
<tt>p2
</tt> using a path going completely inside the space.
97 This only needs to have the same
< relation as actual
98 distances, and does not need to satisfy the other properties of a
99 norm in a Banach space.
</td>
102 <td><tt>space.move_position_toward(p1, fraction, p2)
</tt></td>
104 <td>Returns a point that is a fraction of the way from
<tt>p1
</tt>
105 to
<tt>p2
</tt>, moving along a
"line" in the space according to
106 the distance measure.
<tt>fraction
</tt> is a
<tt>double
</tt>
107 between
0 and
1, inclusive.
</td>
111 <a name=
"convex_topology"><h3>Class template
<tt>convex_topology
</tt></h3></a>
113 <p>Class template
<tt>convex_topology
</tt> implements the basic
114 distance and point movement functions for any convex topology in
115 <tt>Dims
</tt> dimensions. It is not itself a topology, but is intended
116 as a base class that any convex topology can derive from. The derived
117 topology need only provide a suitable
<tt>random_point
</tt> function
118 that returns a random point within the space.
121 template
<std::size_t Dims
>
122 class convex_topology
127 double
& operator[](std::size_t i) {return values[i];}
128 const double
& operator[](std::size_t i) const {return values[i];}
135 typedef point point_type;
137 double distance(point a, point b) const;
138 point move_position_toward(point a, double fraction, point b) const;
142 <a name=
"hypercube_topology"><h3>Class template
<tt>hypercube_topology
</tt></h3></a>
144 <p>Class template
<tt>hypercube_topology
</tt> implements a
145 <tt>Dims
</tt>-dimensional hypercube. It is a convex topology whose
146 points are drawn from a random number generator of type
147 <tt>RandomNumberGenerator
</tt>. The
<tt>hypercube_topology
</tt> can
148 be constructed with a given random number generator; if omitted, a
149 new, default-constructed random number generator will be used. The
150 resulting layout will be contained within the hypercube, whose sides
151 measure
2*
<tt>scaling
</tt> long (points will fall in the range
152 [-
<tt>scaling
</tt>,
<tt>scaling
</tt>] in each dimension).
155 template
<std::size_t Dims, typename RandomNumberGenerator = minstd_rand
>
156 class hypercube_topology : public
<a href=
"#convex_topology">convex_topology
</a><Dims
>
159 explicit hypercube_topology(double scaling =
1.0);
160 hypercube_topology(RandomNumberGenerator
& gen, double scaling =
1.0);
161 point_type random_point() const;
165 <a name=
"square_topology"><h3>Class template
<tt>square_topology
</tt></h3></a>
167 <p>Class template
<tt>square_topology
</tt> is a two-dimensional
171 template
<typename RandomNumberGenerator = minstd_rand
>
172 class square_topology : public
<a href=
"#hypercube_topology">hypercube_topology
</a><2, RandomNumberGenerator
>
175 explicit square_topology(double scaling =
1.0);
176 square_topology(RandomNumberGenerator
& gen, double scaling =
1.0);
180 <a name=
"cube_topology"><h3>Class template
<tt>cube_topology
</tt></h3></a>
182 <p>Class template
<tt>cube_topology
</tt> is a three-dimensional
186 template
<typename RandomNumberGenerator = minstd_rand
>
187 class cube_topology : public
<a href=
"#hypercube_topology">hypercube_topology
</a><3, RandomNumberGenerator
>
190 explicit cube_topology(double scaling =
1.0);
191 cube_topology(RandomNumberGenerator
& gen, double scaling =
1.0);
195 <a name=
"ball_topology"><h3>Class template
<tt>ball_topology
</tt></h3></a>
197 <p>Class template
<tt>ball_topology
</tt> implements a
198 <tt>Dims
</tt>-dimensional ball. It is a convex topology whose points
199 are drawn from a random number generator of type
200 <tt>RandomNumberGenerator
</tt> but reside inside the ball. The
201 <tt>ball_topology
</tt> can be constructed with a given random number
202 generator; if omitted, a new, default-constructed random number
203 generator will be used. The resulting layout will be contained within
204 the ball with the given
<tt>radius
</tt>.
207 template
<std::size_t Dims, typename RandomNumberGenerator = minstd_rand
>
208 class ball_topology : public
<a href=
"#convex_topology">convex_topology
</a><Dims
>
211 explicit ball_topology(double radius =
1.0);
212 ball_topology(RandomNumberGenerator
& gen, double radius =
1.0);
213 point_type random_point() const;
217 <a name=
"circle_topology"><h3>Class template
<tt>circle_topology
</tt></h3></a>
219 <p>Class template
<tt>circle_topology
</tt> is a two-dimensional
223 template
<typename RandomNumberGenerator = minstd_rand
>
224 class circle_topology : public
<a href=
"#ball_topology">ball_topology
</a><2, RandomNumberGenerator
>
227 explicit circle_topology(double radius =
1.0);
228 circle_topology(RandomNumberGenerator
& gen, double radius =
1.0);
232 <a name=
"sphere_topology"><h3>Class template
<tt>sphere_topology
</tt></h3></a>
234 <p>Class template
<tt>sphere_topology
</tt> is a three-dimensional
238 template
<typename RandomNumberGenerator = minstd_rand
>
239 class sphere_topology : public
<a href=
"#ball_topology">ball_topology
</a><3, RandomNumberGenerator
>
242 explicit sphere_topology(double radius =
1.0);
243 sphere_topology(RandomNumberGenerator
& gen, double radius =
1.0);
247 <a name=
"heart_topology"><h3>Class template
<tt>heart_topology
</tt></h3></a>
249 <p>Class template
<tt>heart_topology
</tt> is topology in the shape of
250 a heart. It serves as an example of a non-convex, nontrivial topology
254 template
<typename RandomNumberGenerator = minstd_rand
>
258 typedef
<em>unspecified
</em> point_type;
261 heart_topology(RandomNumberGenerator
& gen);
262 point_type random_point() const;
263 double distance(point_type a, point_type b) const;
264 point_type move_position_toward(point_type a, double fraction, point_type b) const;
272 <TD nowrap
>Copyright
© 2004,
2010 Trustees of Indiana University
</TD><TD>
273 Jeremiah Willcock, Indiana University (
<script language=
"Javascript">address(
"osl.iu.edu",
"jewillco")
</script>)
<br>
274 <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>
275 <A HREF=
"http://www.osl.iu.edu/~lums">Andrew Lumsdaine
</A>,
276 Indiana University (
<script language=
"Javascript">address(
"osl.iu.edu",
"lums")
</script>)