]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <HTML> |
2 | <!-- | |
3 | Copyright (c) 2004, 2010 Trustees of Indiana University | |
4 | ||
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) | |
8 | --> | |
9 | <Head> | |
10 | <Title>Boost Graph Library: Topologies for Graph Drawing</Title> | |
11 | <script language="JavaScript" type="text/JavaScript"> | |
12 | <!-- | |
13 | function address(host, user) { | |
14 | var atchar = '@'; | |
15 | var thingy = user+atchar+host; | |
16 | thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>'; | |
17 | document.write(thingy); | |
18 | } | |
19 | //--> | |
20 | </script> | |
21 | </head> | |
22 | ||
23 | ||
24 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
25 | ALINK="#ff0000"> | |
26 | <IMG SRC="../../../boost.png" | |
27 | ALT="C++ Boost" width="277" height="86"> | |
28 | ||
29 | <BR Clear> | |
30 | ||
31 | <H1> | |
32 | Topologies for Graph Drawing | |
33 | </H1> | |
34 | ||
35 | <P> | |
36 | ||
37 | <h3>Synopsis</h3> | |
38 | ||
39 | <pre> | |
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>; | |
48 | </pre> | |
49 | ||
50 | <h3>Summary</h3> | |
51 | ||
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> | |
62 | ||
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>. | |
68 | ||
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: | |
74 | ||
75 | <table border="1"> | |
76 | <tr> | |
77 | <th>Expression</th> | |
78 | <th>Type</th> | |
79 | <th>Description</th> | |
80 | </tr> | |
81 | <tr> | |
82 | <td><tt>Topology::point_type</tt></td> | |
83 | <td>type</td> | |
84 | <td>The type of points in the space.</td> | |
85 | </tr> | |
86 | <tr> | |
87 | <td><tt>space.random_point()</tt></td> | |
88 | <td>point_type</td> | |
89 | <td>Returns a random point (usually uniformly distributed) within | |
90 | the space.</td> | |
91 | </tr> | |
92 | <tr> | |
93 | <td><tt>space.distance(p1, p2)</tt></td> | |
94 | <td>double</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> | |
100 | </tr> | |
101 | <tr> | |
102 | <td><tt>space.move_position_toward(p1, fraction, p2)</tt></td> | |
103 | <td>point_type</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> | |
108 | </tr> | |
109 | </table> | |
110 | ||
111 | <a name="convex_topology"><h3>Class template <tt>convex_topology</tt></h3></a> | |
112 | ||
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. | |
119 | ||
120 | <pre> | |
121 | template<std::size_t Dims> | |
122 | class convex_topology | |
123 | { | |
124 | struct point | |
125 | { | |
126 | point() { } | |
127 | double& operator[](std::size_t i) {return values[i];} | |
128 | const double& operator[](std::size_t i) const {return values[i];} | |
129 | ||
130 | private: | |
131 | double values[Dims]; | |
132 | }; | |
133 | ||
134 | public: | |
135 | typedef point point_type; | |
136 | ||
137 | double distance(point a, point b) const; | |
138 | point move_position_toward(point a, double fraction, point b) const; | |
139 | }; | |
140 | </pre> | |
141 | ||
142 | <a name="hypercube_topology"><h3>Class template <tt>hypercube_topology</tt></h3></a> | |
143 | ||
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). | |
153 | ||
154 | <pre> | |
155 | template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand> | |
156 | class hypercube_topology : public <a href="#convex_topology">convex_topology</a><Dims> | |
157 | { | |
158 | public: | |
159 | explicit hypercube_topology(double scaling = 1.0); | |
160 | hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0); | |
161 | point_type random_point() const; | |
162 | }; | |
163 | </pre> | |
164 | ||
165 | <a name="square_topology"><h3>Class template <tt>square_topology</tt></h3></a> | |
166 | ||
167 | <p>Class template <tt>square_topology</tt> is a two-dimensional | |
168 | hypercube topology. | |
169 | ||
170 | <pre> | |
171 | template<typename RandomNumberGenerator = minstd_rand> | |
172 | class square_topology : public <a href="#hypercube_topology">hypercube_topology</a><2, RandomNumberGenerator> | |
173 | { | |
174 | public: | |
175 | explicit square_topology(double scaling = 1.0); | |
176 | square_topology(RandomNumberGenerator& gen, double scaling = 1.0); | |
177 | }; | |
178 | </pre> | |
179 | ||
180 | <a name="cube_topology"><h3>Class template <tt>cube_topology</tt></h3></a> | |
181 | ||
182 | <p>Class template <tt>cube_topology</tt> is a three-dimensional | |
183 | hypercube topology. | |
184 | ||
185 | <pre> | |
186 | template<typename RandomNumberGenerator = minstd_rand> | |
187 | class cube_topology : public <a href="#hypercube_topology">hypercube_topology</a><3, RandomNumberGenerator> | |
188 | { | |
189 | public: | |
190 | explicit cube_topology(double scaling = 1.0); | |
191 | cube_topology(RandomNumberGenerator& gen, double scaling = 1.0); | |
192 | }; | |
193 | </pre> | |
194 | ||
195 | <a name="ball_topology"><h3>Class template <tt>ball_topology</tt></h3></a> | |
196 | ||
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>. | |
205 | ||
206 | <pre> | |
207 | template<std::size_t Dims, typename RandomNumberGenerator = minstd_rand> | |
208 | class ball_topology : public <a href="#convex_topology">convex_topology</a><Dims> | |
209 | { | |
210 | public: | |
211 | explicit ball_topology(double radius = 1.0); | |
212 | ball_topology(RandomNumberGenerator& gen, double radius = 1.0); | |
213 | point_type random_point() const; | |
214 | }; | |
215 | </pre> | |
216 | ||
217 | <a name="circle_topology"><h3>Class template <tt>circle_topology</tt></h3></a> | |
218 | ||
219 | <p>Class template <tt>circle_topology</tt> is a two-dimensional | |
220 | ball topology. | |
221 | ||
222 | <pre> | |
223 | template<typename RandomNumberGenerator = minstd_rand> | |
224 | class circle_topology : public <a href="#ball_topology">ball_topology</a><2, RandomNumberGenerator> | |
225 | { | |
226 | public: | |
227 | explicit circle_topology(double radius = 1.0); | |
228 | circle_topology(RandomNumberGenerator& gen, double radius = 1.0); | |
229 | }; | |
230 | </pre> | |
231 | ||
232 | <a name="sphere_topology"><h3>Class template <tt>sphere_topology</tt></h3></a> | |
233 | ||
234 | <p>Class template <tt>sphere_topology</tt> is a three-dimensional | |
235 | ball topology. | |
236 | ||
237 | <pre> | |
238 | template<typename RandomNumberGenerator = minstd_rand> | |
239 | class sphere_topology : public <a href="#ball_topology">ball_topology</a><3, RandomNumberGenerator> | |
240 | { | |
241 | public: | |
242 | explicit sphere_topology(double radius = 1.0); | |
243 | sphere_topology(RandomNumberGenerator& gen, double radius = 1.0); | |
244 | }; | |
245 | </pre> | |
246 | ||
247 | <a name="heart_topology"><h3>Class template <tt>heart_topology</tt></h3></a> | |
248 | ||
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 | |
251 | for layout. | |
252 | ||
253 | <pre> | |
254 | template<typename RandomNumberGenerator = minstd_rand> | |
255 | class heart_topology | |
256 | { | |
257 | public: | |
258 | typedef <em>unspecified</em> point_type; | |
259 | ||
260 | heart_topology(); | |
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; | |
265 | }; | |
266 | </pre> | |
267 | ||
268 | <br> | |
269 | <HR> | |
270 | <TABLE> | |
271 | <TR valign=top> | |
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>) | |
277 | </TD></TR></TABLE> | |
278 | ||
279 | </BODY> | |
280 | </HTML> |