1 | // Copyright 2009 The Trustees of Indiana University. |
2 | |
3 | // Distributed under the Boost Software License, Version 1.0. |
4 | // (See accompanying file LICENSE_1_0.txt or copy at |
5 | // http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | // Authors: Jeremiah Willcock |
8 | // Douglas Gregor |
9 | // Andrew Lumsdaine |
10 | #ifndef BOOST_GRAPH_TOPOLOGY_HPP |
11 | #define BOOST_GRAPH_TOPOLOGY_HPP |
12 | |
13 | #include <boost/config/no_tr1/cmath.hpp> |
14 | #include <cmath> |
15 | #include <boost/random/uniform_01.hpp> |
16 | #include <boost/random/linear_congruential.hpp> |
17 | #include <boost/math/constants/constants.hpp> // For root_two |
18 | #include <boost/algorithm/minmax.hpp> |
19 | #include <boost/config.hpp> // For BOOST_STATIC_CONSTANT |
20 | #include <boost/math/special_functions/hypot.hpp> |
21 | |
22 | // Classes and concepts to represent points in a space, with distance and move |
23 | // operations (used for Gurson-Atun layout), plus other things like bounding |
24 | // boxes used for other layout algorithms. |
25 | |
26 | namespace boost { |
27 | |
28 | /*********************************************************** |
29 | * Topologies * |
30 | ***********************************************************/ |
31 | template<std::size_t Dims> |
32 | class convex_topology |
33 | { |
34 | public: // For VisualAge C++ |
35 | struct point |
36 | { |
37 | BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims); |
38 | point() { } |
39 | double& operator[](std::size_t i) {return values[i];} |
40 | const double& operator[](std::size_t i) const {return values[i];} |
41 | |
42 | private: |
43 | double values[Dims]; |
44 | }; |
45 | |
46 | public: // For VisualAge C++ |
47 | struct point_difference |
48 | { |
49 | BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims); |
50 | point_difference() { |
51 | for (std::size_t i = 0; i < Dims; ++i) values[i] = 0.; |
52 | } |
53 | double& operator[](std::size_t i) {return values[i];} |
54 | const double& operator[](std::size_t i) const {return values[i];} |
55 | |
56 | friend point_difference operator+(const point_difference& a, const point_difference& b) { |
57 | point_difference result; |
58 | for (std::size_t i = 0; i < Dims; ++i) |
59 | result[i] = a[i] + b[i]; |
60 | return result; |
61 | } |
62 | |
63 | friend point_difference& operator+=(point_difference& a, const point_difference& b) { |
64 | for (std::size_t i = 0; i < Dims; ++i) |
65 | a[i] += b[i]; |
66 | return a; |
67 | } |
68 | |
69 | friend point_difference operator-(const point_difference& a) { |
70 | point_difference result; |
71 | for (std::size_t i = 0; i < Dims; ++i) |
72 | result[i] = -a[i]; |
73 | return result; |
74 | } |
75 | |
76 | friend point_difference operator-(const point_difference& a, const point_difference& b) { |
77 | point_difference result; |
78 | for (std::size_t i = 0; i < Dims; ++i) |
79 | result[i] = a[i] - b[i]; |
80 | return result; |
81 | } |
82 | |
83 | friend point_difference& operator-=(point_difference& a, const point_difference& b) { |
84 | for (std::size_t i = 0; i < Dims; ++i) |
85 | a[i] -= b[i]; |
86 | return a; |
87 | } |
88 | |
89 | friend point_difference operator*(const point_difference& a, const point_difference& b) { |
90 | point_difference result; |
91 | for (std::size_t i = 0; i < Dims; ++i) |
92 | result[i] = a[i] * b[i]; |
93 | return result; |
94 | } |
95 | |
96 | friend point_difference operator*(const point_difference& a, double b) { |
97 | point_difference result; |
98 | for (std::size_t i = 0; i < Dims; ++i) |
99 | result[i] = a[i] * b; |
100 | return result; |
101 | } |
102 | |
103 | friend point_difference operator*(double a, const point_difference& b) { |
104 | point_difference result; |
105 | for (std::size_t i = 0; i < Dims; ++i) |
106 | result[i] = a * b[i]; |
107 | return result; |
108 | } |
109 | |
110 | friend point_difference operator/(const point_difference& a, const point_difference& b) { |
111 | point_difference result; |
112 | for (std::size_t i = 0; i < Dims; ++i) |
113 | result[i] = (b[i] == 0.) ? 0. : a[i] / b[i]; |
114 | return result; |
115 | } |
116 | |
117 | friend double dot(const point_difference& a, const point_difference& b) { |
118 | double result = 0; |
119 | for (std::size_t i = 0; i < Dims; ++i) |
120 | result += a[i] * b[i]; |
121 | return result; |
122 | } |
123 | |
124 | private: |
125 | double values[Dims]; |
126 | }; |
127 | |
128 | public: |
129 | typedef point point_type; |
130 | typedef point_difference point_difference_type; |
131 | |
132 | double distance(point a, point b) const |
133 | { |
134 | double dist = 0.; |
135 | for (std::size_t i = 0; i < Dims; ++i) { |
136 | double diff = b[i] - a[i]; |
137 | dist = boost::math::hypot(x: dist, y: diff); |
138 | } |
139 | // Exact properties of the distance are not important, as long as |
140 | // < on what this returns matches real distances; l_2 is used because |
141 | // Fruchterman-Reingold also uses this code and it relies on l_2. |
142 | return dist; |
143 | } |
144 | |
145 | point move_position_toward(point a, double fraction, point b) const |
146 | { |
147 | point result; |
148 | for (std::size_t i = 0; i < Dims; ++i) |
149 | result[i] = a[i] + (b[i] - a[i]) * fraction; |
150 | return result; |
151 | } |
152 | |
153 | point_difference difference(point a, point b) const { |
154 | point_difference result; |
155 | for (std::size_t i = 0; i < Dims; ++i) |
156 | result[i] = a[i] - b[i]; |
157 | return result; |
158 | } |
159 | |
160 | point adjust(point a, point_difference delta) const { |
161 | point result; |
162 | for (std::size_t i = 0; i < Dims; ++i) |
163 | result[i] = a[i] + delta[i]; |
164 | return result; |
165 | } |
166 | |
167 | point pointwise_min(point a, point b) const { |
168 | BOOST_USING_STD_MIN(); |
169 | point result; |
170 | for (std::size_t i = 0; i < Dims; ++i) |
171 | result[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]); |
172 | return result; |
173 | } |
174 | |
175 | point pointwise_max(point a, point b) const { |
176 | BOOST_USING_STD_MAX(); |
177 | point result; |
178 | for (std::size_t i = 0; i < Dims; ++i) |
179 | result[i] = max BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]); |
180 | return result; |
181 | } |
182 | |
183 | double norm(point_difference delta) const { |
184 | double n = 0.; |
185 | for (std::size_t i = 0; i < Dims; ++i) |
186 | n = boost::math::hypot(n, delta[i]); |
187 | return n; |
188 | } |
189 | |
190 | double volume(point_difference delta) const { |
191 | double n = 1.; |
192 | for (std::size_t i = 0; i < Dims; ++i) |
193 | n *= delta[i]; |
194 | return n; |
195 | } |
196 | |
197 | }; |
198 | |
199 | template<std::size_t Dims, |
200 | typename RandomNumberGenerator = minstd_rand> |
201 | class hypercube_topology : public convex_topology<Dims> |
202 | { |
203 | typedef uniform_01<RandomNumberGenerator, double> rand_t; |
204 | |
205 | public: |
206 | typedef typename convex_topology<Dims>::point_type point_type; |
207 | typedef typename convex_topology<Dims>::point_difference_type point_difference_type; |
208 | |
209 | explicit hypercube_topology(double scaling = 1.0) |
210 | : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)), |
211 | scaling(scaling) |
212 | { } |
213 | |
214 | hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0) |
215 | : gen_ptr(), rand(new rand_t(gen)), scaling(scaling) { } |
216 | |
217 | point_type random_point() const |
218 | { |
219 | point_type p; |
220 | for (std::size_t i = 0; i < Dims; ++i) |
221 | p[i] = (*rand)() * scaling; |
222 | return p; |
223 | } |
224 | |
225 | point_type bound(point_type a) const |
226 | { |
227 | BOOST_USING_STD_MIN(); |
228 | BOOST_USING_STD_MAX(); |
229 | point_type p; |
230 | for (std::size_t i = 0; i < Dims; ++i) |
231 | p[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (scaling, max BOOST_PREVENT_MACRO_SUBSTITUTION (-scaling, a[i])); |
232 | return p; |
233 | } |
234 | |
235 | double distance_from_boundary(point_type a) const |
236 | { |
237 | BOOST_USING_STD_MIN(); |
238 | BOOST_USING_STD_MAX(); |
239 | #ifndef BOOST_NO_STDC_NAMESPACE |
240 | using std::abs; |
241 | #endif |
242 | BOOST_STATIC_ASSERT (Dims >= 1); |
243 | double dist = abs(scaling - a[0]); |
244 | for (std::size_t i = 1; i < Dims; ++i) |
245 | dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(scaling - a[i])); |
246 | return dist; |
247 | } |
248 | |
249 | point_type center() const { |
250 | point_type result; |
251 | for (std::size_t i = 0; i < Dims; ++i) |
252 | result[i] = scaling * .5; |
253 | return result; |
254 | } |
255 | |
256 | point_type origin() const { |
257 | point_type result; |
258 | for (std::size_t i = 0; i < Dims; ++i) |
259 | result[i] = 0; |
260 | return result; |
261 | } |
262 | |
263 | point_difference_type extent() const { |
264 | point_difference_type result; |
265 | for (std::size_t i = 0; i < Dims; ++i) |
266 | result[i] = scaling; |
267 | return result; |
268 | } |
269 | |
270 | private: |
271 | shared_ptr<RandomNumberGenerator> gen_ptr; |
272 | shared_ptr<rand_t> rand; |
273 | double scaling; |
274 | }; |
275 | |
276 | template<typename RandomNumberGenerator = minstd_rand> |
277 | class square_topology : public hypercube_topology<2, RandomNumberGenerator> |
278 | { |
279 | typedef hypercube_topology<2, RandomNumberGenerator> inherited; |
280 | |
281 | public: |
282 | explicit square_topology(double scaling = 1.0) : inherited(scaling) { } |
283 | |
284 | square_topology(RandomNumberGenerator& gen, double scaling = 1.0) |
285 | : inherited(gen, scaling) { } |
286 | }; |
287 | |
288 | template<typename RandomNumberGenerator = minstd_rand> |
289 | class rectangle_topology : public convex_topology<2> |
290 | { |
291 | typedef uniform_01<RandomNumberGenerator, double> rand_t; |
292 | |
293 | public: |
294 | rectangle_topology(double left, double top, double right, double bottom) |
295 | : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)), |
296 | left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (a: left, b: right)), |
297 | top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (a: top, b: bottom)), |
298 | right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (a: left, b: right)), |
299 | bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (a: top, b: bottom)) { } |
300 | |
301 | rectangle_topology(RandomNumberGenerator& gen, double left, double top, double right, double bottom) |
302 | : gen_ptr(), rand(new rand_t(gen)), |
303 | left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (a: left, b: right)), |
304 | top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (a: top, b: bottom)), |
305 | right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (a: left, b: right)), |
306 | bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (a: top, b: bottom)) { } |
307 | |
308 | typedef typename convex_topology<2>::point_type point_type; |
309 | typedef typename convex_topology<2>::point_difference_type point_difference_type; |
310 | |
311 | point_type random_point() const |
312 | { |
313 | point_type p; |
314 | p[0] = (*rand)() * (right - left) + left; |
315 | p[1] = (*rand)() * (bottom - top) + top; |
316 | return p; |
317 | } |
318 | |
319 | point_type bound(point_type a) const |
320 | { |
321 | BOOST_USING_STD_MIN(); |
322 | BOOST_USING_STD_MAX(); |
323 | point_type p; |
324 | p[0] = min BOOST_PREVENT_MACRO_SUBSTITUTION (right, max BOOST_PREVENT_MACRO_SUBSTITUTION (left, a[0])); |
325 | p[1] = min BOOST_PREVENT_MACRO_SUBSTITUTION (bottom, max BOOST_PREVENT_MACRO_SUBSTITUTION (top, a[1])); |
326 | return p; |
327 | } |
328 | |
329 | double distance_from_boundary(point_type a) const |
330 | { |
331 | BOOST_USING_STD_MIN(); |
332 | BOOST_USING_STD_MAX(); |
333 | #ifndef BOOST_NO_STDC_NAMESPACE |
334 | using std::abs; |
335 | #endif |
336 | double dist = abs(left - a[0]); |
337 | dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(right - a[0])); |
338 | dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(top - a[1])); |
339 | dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(bottom - a[1])); |
340 | return dist; |
341 | } |
342 | |
343 | point_type center() const { |
344 | point_type result; |
345 | result[0] = (left + right) / 2.; |
346 | result[1] = (top + bottom) / 2.; |
347 | return result; |
348 | } |
349 | |
350 | point_type origin() const { |
351 | point_type result; |
352 | result[0] = left; |
353 | result[1] = top; |
354 | return result; |
355 | } |
356 | |
357 | point_difference_type extent() const { |
358 | point_difference_type result; |
359 | result[0] = right - left; |
360 | result[1] = bottom - top; |
361 | return result; |
362 | } |
363 | |
364 | private: |
365 | shared_ptr<RandomNumberGenerator> gen_ptr; |
366 | shared_ptr<rand_t> rand; |
367 | double left, top, right, bottom; |
368 | }; |
369 | |
370 | template<typename RandomNumberGenerator = minstd_rand> |
371 | class cube_topology : public hypercube_topology<3, RandomNumberGenerator> |
372 | { |
373 | typedef hypercube_topology<3, RandomNumberGenerator> inherited; |
374 | |
375 | public: |
376 | explicit cube_topology(double scaling = 1.0) : inherited(scaling) { } |
377 | |
378 | cube_topology(RandomNumberGenerator& gen, double scaling = 1.0) |
379 | : inherited(gen, scaling) { } |
380 | }; |
381 | |
382 | template<std::size_t Dims, |
383 | typename RandomNumberGenerator = minstd_rand> |
384 | class ball_topology : public convex_topology<Dims> |
385 | { |
386 | typedef uniform_01<RandomNumberGenerator, double> rand_t; |
387 | |
388 | public: |
389 | typedef typename convex_topology<Dims>::point_type point_type; |
390 | typedef typename convex_topology<Dims>::point_difference_type point_difference_type; |
391 | |
392 | explicit ball_topology(double radius = 1.0) |
393 | : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)), |
394 | radius(radius) |
395 | { } |
396 | |
397 | ball_topology(RandomNumberGenerator& gen, double radius = 1.0) |
398 | : gen_ptr(), rand(new rand_t(gen)), radius(radius) { } |
399 | |
400 | point_type random_point() const |
401 | { |
402 | point_type p; |
403 | double dist_sum; |
404 | do { |
405 | dist_sum = 0.0; |
406 | for (std::size_t i = 0; i < Dims; ++i) { |
407 | double x = (*rand)() * 2*radius - radius; |
408 | p[i] = x; |
409 | dist_sum += x * x; |
410 | } |
411 | } while (dist_sum > radius*radius); |
412 | return p; |
413 | } |
414 | |
415 | point_type bound(point_type a) const |
416 | { |
417 | BOOST_USING_STD_MIN(); |
418 | BOOST_USING_STD_MAX(); |
419 | double r = 0.; |
420 | for (std::size_t i = 0; i < Dims; ++i) |
421 | r = boost::math::hypot(r, a[i]); |
422 | if (r <= radius) return a; |
423 | double scaling_factor = radius / r; |
424 | point_type p; |
425 | for (std::size_t i = 0; i < Dims; ++i) |
426 | p[i] = a[i] * scaling_factor; |
427 | return p; |
428 | } |
429 | |
430 | double distance_from_boundary(point_type a) const |
431 | { |
432 | double r = 0.; |
433 | for (std::size_t i = 0; i < Dims; ++i) |
434 | r = boost::math::hypot(r, a[i]); |
435 | return radius - r; |
436 | } |
437 | |
438 | point_type center() const { |
439 | point_type result; |
440 | for (std::size_t i = 0; i < Dims; ++i) |
441 | result[i] = 0; |
442 | return result; |
443 | } |
444 | |
445 | point_type origin() const { |
446 | point_type result; |
447 | for (std::size_t i = 0; i < Dims; ++i) |
448 | result[i] = -radius; |
449 | return result; |
450 | } |
451 | |
452 | point_difference_type extent() const { |
453 | point_difference_type result; |
454 | for (std::size_t i = 0; i < Dims; ++i) |
455 | result[i] = 2. * radius; |
456 | return result; |
457 | } |
458 | |
459 | private: |
460 | shared_ptr<RandomNumberGenerator> gen_ptr; |
461 | shared_ptr<rand_t> rand; |
462 | double radius; |
463 | }; |
464 | |
465 | template<typename RandomNumberGenerator = minstd_rand> |
466 | class circle_topology : public ball_topology<2, RandomNumberGenerator> |
467 | { |
468 | typedef ball_topology<2, RandomNumberGenerator> inherited; |
469 | |
470 | public: |
471 | explicit circle_topology(double radius = 1.0) : inherited(radius) { } |
472 | |
473 | circle_topology(RandomNumberGenerator& gen, double radius = 1.0) |
474 | : inherited(gen, radius) { } |
475 | }; |
476 | |
477 | template<typename RandomNumberGenerator = minstd_rand> |
478 | class sphere_topology : public ball_topology<3, RandomNumberGenerator> |
479 | { |
480 | typedef ball_topology<3, RandomNumberGenerator> inherited; |
481 | |
482 | public: |
483 | explicit sphere_topology(double radius = 1.0) : inherited(radius) { } |
484 | |
485 | sphere_topology(RandomNumberGenerator& gen, double radius = 1.0) |
486 | : inherited(gen, radius) { } |
487 | }; |
488 | |
489 | template<typename RandomNumberGenerator = minstd_rand> |
490 | class heart_topology |
491 | { |
492 | // Heart is defined as the union of three shapes: |
493 | // Square w/ corners (+-1000, -1000), (0, 0), (0, -2000) |
494 | // Circle centered at (-500, -500) radius 500*sqrt(2) |
495 | // Circle centered at (500, -500) radius 500*sqrt(2) |
496 | // Bounding box (-1000, -2000) - (1000, 500*(sqrt(2) - 1)) |
497 | |
498 | struct point |
499 | { |
500 | point() { values[0] = 0.0; values[1] = 0.0; } |
501 | point(double x, double y) { values[0] = x; values[1] = y; } |
502 | |
503 | double& operator[](std::size_t i) { return values[i]; } |
504 | double operator[](std::size_t i) const { return values[i]; } |
505 | |
506 | private: |
507 | double values[2]; |
508 | }; |
509 | |
510 | bool in_heart(point p) const |
511 | { |
512 | #ifndef BOOST_NO_STDC_NAMESPACE |
513 | using std::abs; |
514 | #endif |
515 | |
516 | if (p[1] < abs(p[0]) - 2000) return false; // Bottom |
517 | if (p[1] <= -1000) return true; // Diagonal of square |
518 | if (boost::math::hypot(p[0] - -500, p[1] - -500) <= 500. * boost::math::constants::root_two<double>()) |
519 | return true; // Left circle |
520 | if (boost::math::hypot(p[0] - 500, p[1] - -500) <= 500. * boost::math::constants::root_two<double>()) |
521 | return true; // Right circle |
522 | return false; |
523 | } |
524 | |
525 | bool segment_within_heart(point p1, point p2) const |
526 | { |
527 | // Assumes that p1 and p2 are within the heart |
528 | if ((p1[0] < 0) == (p2[0] < 0)) return true; // Same side of symmetry line |
529 | if (p1[0] == p2[0]) return true; // Vertical |
530 | double slope = (p2[1] - p1[1]) / (p2[0] - p1[0]); |
531 | double intercept = p1[1] - p1[0] * slope; |
532 | if (intercept > 0) return false; // Crosses between circles |
533 | return true; |
534 | } |
535 | |
536 | typedef uniform_01<RandomNumberGenerator, double> rand_t; |
537 | |
538 | public: |
539 | typedef point point_type; |
540 | |
541 | heart_topology() |
542 | : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)) { } |
543 | |
544 | heart_topology(RandomNumberGenerator& gen) |
545 | : gen_ptr(), rand(new rand_t(gen)) { } |
546 | |
547 | point random_point() const |
548 | { |
549 | point result; |
550 | do { |
551 | result[0] = (*rand)() * (1000 + 1000 * boost::math::constants::root_two<double>()) - (500 + 500 * boost::math::constants::root_two<double>()); |
552 | result[1] = (*rand)() * (2000 + 500 * (boost::math::constants::root_two<double>() - 1)) - 2000; |
553 | } while (!in_heart(p: result)); |
554 | return result; |
555 | } |
556 | |
557 | // Not going to provide clipping to bounding region or distance from boundary |
558 | |
559 | double distance(point a, point b) const |
560 | { |
561 | if (segment_within_heart(p1: a, p2: b)) { |
562 | // Straight line |
563 | return boost::math::hypot(b[0] - a[0], b[1] - a[1]); |
564 | } else { |
565 | // Straight line bending around (0, 0) |
566 | return boost::math::hypot(a[0], a[1]) + boost::math::hypot(b[0], b[1]); |
567 | } |
568 | } |
569 | |
570 | point move_position_toward(point a, double fraction, point b) const |
571 | { |
572 | if (segment_within_heart(p1: a, p2: b)) { |
573 | // Straight line |
574 | return point(a[0] + (b[0] - a[0]) * fraction, |
575 | a[1] + (b[1] - a[1]) * fraction); |
576 | } else { |
577 | double distance_to_point_a = boost::math::hypot(a[0], a[1]); |
578 | double distance_to_point_b = boost::math::hypot(b[0], b[1]); |
579 | double location_of_point = distance_to_point_a / |
580 | (distance_to_point_a + distance_to_point_b); |
581 | if (fraction < location_of_point) |
582 | return point(a[0] * (1 - fraction / location_of_point), |
583 | a[1] * (1 - fraction / location_of_point)); |
584 | else |
585 | return point( |
586 | b[0] * ((fraction - location_of_point) / (1 - location_of_point)), |
587 | b[1] * ((fraction - location_of_point) / (1 - location_of_point))); |
588 | } |
589 | } |
590 | |
591 | private: |
592 | shared_ptr<RandomNumberGenerator> gen_ptr; |
593 | shared_ptr<rand_t> rand; |
594 | }; |
595 | |
596 | } // namespace boost |
597 | |
598 | #endif // BOOST_GRAPH_TOPOLOGY_HPP |
599 | |