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); pointboost::convex_topology::point38 point() { } operator []boost::convex_topology::point39 double& operator[](std::size_t i) {return values[i];} operator []boost::convex_topology::point40 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); point_differenceboost::convex_topology::point_difference50 point_difference() { 51 for (std::size_t i = 0; i < Dims; ++i) values[i] = 0.; 52 } operator []boost::convex_topology::point_difference53 double& operator[](std::size_t i) {return values[i];} operator []boost::convex_topology::point_difference54 const double& operator[](std::size_t i) const {return values[i];} 55 operator +(const point_difference & a,const point_difference & b)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 operator +=(point_difference & a,const point_difference & b)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 operator -(const point_difference & a)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 operator -(const point_difference & a,const point_difference & b)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 operator -=(point_difference & a,const point_difference & b)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 operator *(const point_difference & a,const point_difference & b)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 operator *(const point_difference & a,double b)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 operator *(double a,const point_difference & b)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 operator /(const point_difference & a,const point_difference & b)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 dot(const point_difference & a,const point_difference & b)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 distance(point a,point b) const132 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(dist, 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 move_position_toward(point a,double fraction,point b) const145 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 difference(point a,point b) const153 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 adjust(point a,point_difference delta) const160 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 pointwise_min(point a,point b) const167 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 pointwise_max(point a,point b) const175 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 norm(point_difference delta) const183 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 volume(point_difference delta) const190 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 hypercube_topology(double scaling=1.0)209 explicit hypercube_topology(double scaling = 1.0) 210 : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)), 211 scaling(scaling) 212 { } 213 hypercube_topology(RandomNumberGenerator & gen,double scaling=1.0)214 hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0) 215 : gen_ptr(), rand(new rand_t(gen)), scaling(scaling) { } 216 random_point() const217 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 bound(point_type a) const225 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 distance_from_boundary(point_type a) const235 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 center() const249 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 origin() const256 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 extent() const263 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: square_topology(double scaling=1.0)282 explicit square_topology(double scaling = 1.0) : inherited(scaling) { } 283 square_topology(RandomNumberGenerator & gen,double scaling=1.0)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: rectangle_topology(double left,double top,double right,double bottom)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)) { } 300 rectangle_topology(RandomNumberGenerator & gen,double left,double top,double right,double 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)) { } 307 308 typedef typename convex_topology<2>::point_type point_type; 309 typedef typename convex_topology<2>::point_difference_type point_difference_type; 310 random_point() const311 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 bound(point_type a) const319 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 distance_from_boundary(point_type a) const329 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 center() const343 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 origin() const350 point_type origin() const { 351 point_type result; 352 result[0] = left; 353 result[1] = top; 354 return result; 355 } 356 extent() const357 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: cube_topology(double scaling=1.0)376 explicit cube_topology(double scaling = 1.0) : inherited(scaling) { } 377 cube_topology(RandomNumberGenerator & gen,double scaling=1.0)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 ball_topology(double radius=1.0)392 explicit ball_topology(double radius = 1.0) 393 : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)), 394 radius(radius) 395 { } 396 ball_topology(RandomNumberGenerator & gen,double radius=1.0)397 ball_topology(RandomNumberGenerator& gen, double radius = 1.0) 398 : gen_ptr(), rand(new rand_t(gen)), radius(radius) { } 399 random_point() const400 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 bound(point_type a) const415 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 distance_from_boundary(point_type a) const430 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 center() const438 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 origin() const445 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 extent() const452 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: circle_topology(double radius=1.0)471 explicit circle_topology(double radius = 1.0) : inherited(radius) { } 472 circle_topology(RandomNumberGenerator & gen,double radius=1.0)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: sphere_topology(double radius=1.0)483 explicit sphere_topology(double radius = 1.0) : inherited(radius) { } 484 sphere_topology(RandomNumberGenerator & gen,double radius=1.0)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 { pointboost::heart_topology::point500 point() { values[0] = 0.0; values[1] = 0.0; } pointboost::heart_topology::point501 point(double x, double y) { values[0] = x; values[1] = y; } 502 operator []boost::heart_topology::point503 double& operator[](std::size_t i) { return values[i]; } operator []boost::heart_topology::point504 double operator[](std::size_t i) const { return values[i]; } 505 506 private: 507 double values[2]; 508 }; 509 in_heart(point p) const510 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 segment_within_heart(point p1,point p2) const525 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 heart_topology()541 heart_topology() 542 : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)) { } 543 heart_topology(RandomNumberGenerator & gen)544 heart_topology(RandomNumberGenerator& gen) 545 : gen_ptr(), rand(new rand_t(gen)) { } 546 random_point() const547 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(result)); 554 return result; 555 } 556 557 // Not going to provide clipping to bounding region or distance from boundary 558 distance(point a,point b) const559 double distance(point a, point b) const 560 { 561 if (segment_within_heart(a, 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 move_position_toward(point a,double fraction,point b) const570 point move_position_toward(point a, double fraction, point b) const 571 { 572 if (segment_within_heart(a, 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