1 // Copyright 2009 The Trustees of Indiana University.
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)
7 // Authors: Jeremiah Willcock
10 #ifndef BOOST_GRAPH_TOPOLOGY_HPP
11 #define BOOST_GRAPH_TOPOLOGY_HPP
13 #include <boost/config/no_tr1/cmath.hpp>
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>
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.
28 /***********************************************************
30 ***********************************************************/
31 template<std::size_t Dims>
34 public: // For VisualAge C++
37 BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims);
39 double& operator[](std::size_t i) {return values[i];}
40 const double& operator[](std::size_t i) const {return values[i];}
46 public: // For VisualAge C++
47 struct point_difference
49 BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims);
51 for (std::size_t i = 0; i < Dims; ++i) values[i] = 0.;
53 double& operator[](std::size_t i) {return values[i];}
54 const double& operator[](std::size_t i) const {return values[i];}
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];
63 friend point_difference& operator+=(point_difference& a, const point_difference& b) {
64 for (std::size_t i = 0; i < Dims; ++i)
69 friend point_difference operator-(const point_difference& a) {
70 point_difference result;
71 for (std::size_t i = 0; i < Dims; ++i)
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];
83 friend point_difference& operator-=(point_difference& a, const point_difference& b) {
84 for (std::size_t i = 0; i < Dims; ++i)
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];
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)
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];
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];
117 friend double dot(const point_difference& a, const point_difference& b) {
119 for (std::size_t i = 0; i < Dims; ++i)
120 result += a[i] * b[i];
129 typedef point point_type;
130 typedef point_difference point_difference_type;
132 double distance(point a, point b) const
135 for (std::size_t i = 0; i < Dims; ++i) {
136 double diff = b[i] - a[i];
137 dist = boost::math::hypot(dist, diff);
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.
145 point move_position_toward(point a, double fraction, point b) const
148 for (std::size_t i = 0; i < Dims; ++i)
149 result[i] = a[i] + (b[i] - a[i]) * fraction;
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];
160 point adjust(point a, point_difference delta) const {
162 for (std::size_t i = 0; i < Dims; ++i)
163 result[i] = a[i] + delta[i];
167 point pointwise_min(point a, point b) const {
168 BOOST_USING_STD_MIN();
170 for (std::size_t i = 0; i < Dims; ++i)
171 result[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]);
175 point pointwise_max(point a, point b) const {
176 BOOST_USING_STD_MAX();
178 for (std::size_t i = 0; i < Dims; ++i)
179 result[i] = max BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]);
183 double norm(point_difference delta) const {
185 for (std::size_t i = 0; i < Dims; ++i)
186 n = boost::math::hypot(n, delta[i]);
190 double volume(point_difference delta) const {
192 for (std::size_t i = 0; i < Dims; ++i)
199 template<std::size_t Dims,
200 typename RandomNumberGenerator = minstd_rand>
201 class hypercube_topology : public convex_topology<Dims>
203 typedef uniform_01<RandomNumberGenerator, double> rand_t;
206 typedef typename convex_topology<Dims>::point_type point_type;
207 typedef typename convex_topology<Dims>::point_difference_type point_difference_type;
209 explicit hypercube_topology(double scaling = 1.0)
210 : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
214 hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
215 : gen_ptr(), rand(new rand_t(gen)), scaling(scaling) { }
217 point_type random_point() const
220 for (std::size_t i = 0; i < Dims; ++i)
221 p[i] = (*rand)() * scaling;
225 point_type bound(point_type a) const
227 BOOST_USING_STD_MIN();
228 BOOST_USING_STD_MAX();
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]));
235 double distance_from_boundary(point_type a) const
237 BOOST_USING_STD_MIN();
238 BOOST_USING_STD_MAX();
239 #ifndef BOOST_NO_STDC_NAMESPACE
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]));
249 point_type center() const {
251 for (std::size_t i = 0; i < Dims; ++i)
252 result[i] = scaling * .5;
256 point_type origin() const {
258 for (std::size_t i = 0; i < Dims; ++i)
263 point_difference_type extent() const {
264 point_difference_type result;
265 for (std::size_t i = 0; i < Dims; ++i)
271 shared_ptr<RandomNumberGenerator> gen_ptr;
272 shared_ptr<rand_t> rand;
276 template<typename RandomNumberGenerator = minstd_rand>
277 class square_topology : public hypercube_topology<2, RandomNumberGenerator>
279 typedef hypercube_topology<2, RandomNumberGenerator> inherited;
282 explicit square_topology(double scaling = 1.0) : inherited(scaling) { }
284 square_topology(RandomNumberGenerator& gen, double scaling = 1.0)
285 : inherited(gen, scaling) { }
288 template<typename RandomNumberGenerator = minstd_rand>
289 class rectangle_topology : public convex_topology<2>
291 typedef uniform_01<RandomNumberGenerator, double> rand_t;
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 (left, right)),
297 top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)),
298 right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
299 bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)) { }
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 (left, right)),
304 top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)),
305 right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
306 bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)) { }
308 typedef typename convex_topology<2>::point_type point_type;
309 typedef typename convex_topology<2>::point_difference_type point_difference_type;
311 point_type random_point() const
314 p[0] = (*rand)() * (right - left) + left;
315 p[1] = (*rand)() * (bottom - top) + top;
319 point_type bound(point_type a) const
321 BOOST_USING_STD_MIN();
322 BOOST_USING_STD_MAX();
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]));
329 double distance_from_boundary(point_type a) const
331 BOOST_USING_STD_MIN();
332 BOOST_USING_STD_MAX();
333 #ifndef BOOST_NO_STDC_NAMESPACE
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]));
343 point_type center() const {
345 result[0] = (left + right) / 2.;
346 result[1] = (top + bottom) / 2.;
350 point_type origin() const {
357 point_difference_type extent() const {
358 point_difference_type result;
359 result[0] = right - left;
360 result[1] = bottom - top;
365 shared_ptr<RandomNumberGenerator> gen_ptr;
366 shared_ptr<rand_t> rand;
367 double left, top, right, bottom;
370 template<typename RandomNumberGenerator = minstd_rand>
371 class cube_topology : public hypercube_topology<3, RandomNumberGenerator>
373 typedef hypercube_topology<3, RandomNumberGenerator> inherited;
376 explicit cube_topology(double scaling = 1.0) : inherited(scaling) { }
378 cube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
379 : inherited(gen, scaling) { }
382 template<std::size_t Dims,
383 typename RandomNumberGenerator = minstd_rand>
384 class ball_topology : public convex_topology<Dims>
386 typedef uniform_01<RandomNumberGenerator, double> rand_t;
389 typedef typename convex_topology<Dims>::point_type point_type;
390 typedef typename convex_topology<Dims>::point_difference_type point_difference_type;
392 explicit ball_topology(double radius = 1.0)
393 : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
397 ball_topology(RandomNumberGenerator& gen, double radius = 1.0)
398 : gen_ptr(), rand(new rand_t(gen)), radius(radius) { }
400 point_type random_point() const
406 for (std::size_t i = 0; i < Dims; ++i) {
407 double x = (*rand)() * 2*radius - radius;
411 } while (dist_sum > radius*radius);
415 point_type bound(point_type a) const
417 BOOST_USING_STD_MIN();
418 BOOST_USING_STD_MAX();
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;
425 for (std::size_t i = 0; i < Dims; ++i)
426 p[i] = a[i] * scaling_factor;
430 double distance_from_boundary(point_type a) const
433 for (std::size_t i = 0; i < Dims; ++i)
434 r = boost::math::hypot(r, a[i]);
438 point_type center() const {
440 for (std::size_t i = 0; i < Dims; ++i)
445 point_type origin() const {
447 for (std::size_t i = 0; i < Dims; ++i)
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;
460 shared_ptr<RandomNumberGenerator> gen_ptr;
461 shared_ptr<rand_t> rand;
465 template<typename RandomNumberGenerator = minstd_rand>
466 class circle_topology : public ball_topology<2, RandomNumberGenerator>
468 typedef ball_topology<2, RandomNumberGenerator> inherited;
471 explicit circle_topology(double radius = 1.0) : inherited(radius) { }
473 circle_topology(RandomNumberGenerator& gen, double radius = 1.0)
474 : inherited(gen, radius) { }
477 template<typename RandomNumberGenerator = minstd_rand>
478 class sphere_topology : public ball_topology<3, RandomNumberGenerator>
480 typedef ball_topology<3, RandomNumberGenerator> inherited;
483 explicit sphere_topology(double radius = 1.0) : inherited(radius) { }
485 sphere_topology(RandomNumberGenerator& gen, double radius = 1.0)
486 : inherited(gen, radius) { }
489 template<typename RandomNumberGenerator = minstd_rand>
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))
500 point() { values[0] = 0.0; values[1] = 0.0; }
501 point(double x, double y) { values[0] = x; values[1] = y; }
503 double& operator[](std::size_t i) { return values[i]; }
504 double operator[](std::size_t i) const { return values[i]; }
510 bool in_heart(point p) const
512 #ifndef BOOST_NO_STDC_NAMESPACE
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
525 bool segment_within_heart(point p1, point p2) const
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
536 typedef uniform_01<RandomNumberGenerator, double> rand_t;
539 typedef point point_type;
542 : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)) { }
544 heart_topology(RandomNumberGenerator& gen)
545 : gen_ptr(), rand(new rand_t(gen)) { }
547 point random_point() const
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(result));
557 // Not going to provide clipping to bounding region or distance from boundary
559 double distance(point a, point b) const
561 if (segment_within_heart(a, b)) {
563 return boost::math::hypot(b[0] - a[0], b[1] - a[1]);
565 // Straight line bending around (0, 0)
566 return boost::math::hypot(a[0], a[1]) + boost::math::hypot(b[0], b[1]);
570 point move_position_toward(point a, double fraction, point b) const
572 if (segment_within_heart(a, b)) {
574 return point(a[0] + (b[0] - a[0]) * fraction,
575 a[1] + (b[1] - a[1]) * fraction);
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));
586 b[0] * ((fraction - location_of_point) / (1 - location_of_point)),
587 b[1] * ((fraction - location_of_point) / (1 - location_of_point)));
592 shared_ptr<RandomNumberGenerator> gen_ptr;
593 shared_ptr<rand_t> rand;
598 #endif // BOOST_GRAPH_TOPOLOGY_HPP