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 /*********************************************************** 30 * Topologies * 31 ***********************************************************/ 32 template < std::size_t Dims > 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 { 52 for (std::size_t i = 0; i < Dims; ++i) 53 values[i] = 0.; 54 } operator []boost::convex_topology::point_difference55 double& operator[](std::size_t i) { return values[i]; } operator []boost::convex_topology::point_difference56 const double& operator[](std::size_t i) const { return values[i]; } 57 operator +(const point_difference & a,const point_difference & b)58 friend point_difference operator+( 59 const point_difference& a, const point_difference& b) 60 { 61 point_difference result; 62 for (std::size_t i = 0; i < Dims; ++i) 63 result[i] = a[i] + b[i]; 64 return result; 65 } 66 operator +=(point_difference & a,const point_difference & b)67 friend point_difference& operator+=( 68 point_difference& a, const point_difference& b) 69 { 70 for (std::size_t i = 0; i < Dims; ++i) 71 a[i] += b[i]; 72 return a; 73 } 74 operator -(const point_difference & a)75 friend point_difference operator-(const point_difference& a) 76 { 77 point_difference result; 78 for (std::size_t i = 0; i < Dims; ++i) 79 result[i] = -a[i]; 80 return result; 81 } 82 operator -(const point_difference & a,const point_difference & b)83 friend point_difference operator-( 84 const point_difference& a, const point_difference& b) 85 { 86 point_difference result; 87 for (std::size_t i = 0; i < Dims; ++i) 88 result[i] = a[i] - b[i]; 89 return result; 90 } 91 operator -=(point_difference & a,const point_difference & b)92 friend point_difference& operator-=( 93 point_difference& a, const point_difference& b) 94 { 95 for (std::size_t i = 0; i < Dims; ++i) 96 a[i] -= b[i]; 97 return a; 98 } 99 operator *(const point_difference & a,const point_difference & b)100 friend point_difference operator*( 101 const point_difference& a, const point_difference& b) 102 { 103 point_difference result; 104 for (std::size_t i = 0; i < Dims; ++i) 105 result[i] = a[i] * b[i]; 106 return result; 107 } 108 operator *(const point_difference & a,double b)109 friend point_difference operator*(const point_difference& a, double b) 110 { 111 point_difference result; 112 for (std::size_t i = 0; i < Dims; ++i) 113 result[i] = a[i] * b; 114 return result; 115 } 116 operator *(double a,const point_difference & b)117 friend point_difference operator*(double a, const point_difference& b) 118 { 119 point_difference result; 120 for (std::size_t i = 0; i < Dims; ++i) 121 result[i] = a * b[i]; 122 return result; 123 } 124 operator /(const point_difference & a,const point_difference & b)125 friend point_difference operator/( 126 const point_difference& a, const point_difference& b) 127 { 128 point_difference result; 129 for (std::size_t i = 0; i < Dims; ++i) 130 result[i] = (b[i] == 0.) ? 0. : a[i] / b[i]; 131 return result; 132 } 133 dot(const point_difference & a,const point_difference & b)134 friend double dot(const point_difference& a, const point_difference& b) 135 { 136 double result = 0; 137 for (std::size_t i = 0; i < Dims; ++i) 138 result += a[i] * b[i]; 139 return result; 140 } 141 142 private: 143 double values[Dims]; 144 }; 145 146 public: 147 typedef point point_type; 148 typedef point_difference point_difference_type; 149 distance(point a,point b) const150 double distance(point a, point b) const 151 { 152 double dist = 0.; 153 for (std::size_t i = 0; i < Dims; ++i) 154 { 155 double diff = b[i] - a[i]; 156 dist = boost::math::hypot(dist, diff); 157 } 158 // Exact properties of the distance are not important, as long as 159 // < on what this returns matches real distances; l_2 is used because 160 // Fruchterman-Reingold also uses this code and it relies on l_2. 161 return dist; 162 } 163 move_position_toward(point a,double fraction,point b) const164 point move_position_toward(point a, double fraction, point b) const 165 { 166 point result; 167 for (std::size_t i = 0; i < Dims; ++i) 168 result[i] = a[i] + (b[i] - a[i]) * fraction; 169 return result; 170 } 171 difference(point a,point b) const172 point_difference difference(point a, point b) const 173 { 174 point_difference result; 175 for (std::size_t i = 0; i < Dims; ++i) 176 result[i] = a[i] - b[i]; 177 return result; 178 } 179 adjust(point a,point_difference delta) const180 point adjust(point a, point_difference delta) const 181 { 182 point result; 183 for (std::size_t i = 0; i < Dims; ++i) 184 result[i] = a[i] + delta[i]; 185 return result; 186 } 187 pointwise_min(point a,point b) const188 point pointwise_min(point a, point b) const 189 { 190 BOOST_USING_STD_MIN(); 191 point result; 192 for (std::size_t i = 0; i < Dims; ++i) 193 result[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION(a[i], b[i]); 194 return result; 195 } 196 pointwise_max(point a,point b) const197 point pointwise_max(point a, point b) const 198 { 199 BOOST_USING_STD_MAX(); 200 point result; 201 for (std::size_t i = 0; i < Dims; ++i) 202 result[i] = max BOOST_PREVENT_MACRO_SUBSTITUTION(a[i], b[i]); 203 return result; 204 } 205 norm(point_difference delta) const206 double norm(point_difference delta) const 207 { 208 double n = 0.; 209 for (std::size_t i = 0; i < Dims; ++i) 210 n = boost::math::hypot(n, delta[i]); 211 return n; 212 } 213 volume(point_difference delta) const214 double volume(point_difference delta) const 215 { 216 double n = 1.; 217 for (std::size_t i = 0; i < Dims; ++i) 218 n *= delta[i]; 219 return n; 220 } 221 }; 222 223 template < std::size_t Dims, typename RandomNumberGenerator = minstd_rand > 224 class hypercube_topology : public convex_topology< Dims > 225 { 226 typedef uniform_01< RandomNumberGenerator, double > rand_t; 227 228 public: 229 typedef typename convex_topology< Dims >::point_type point_type; 230 typedef typename convex_topology< Dims >::point_difference_type 231 point_difference_type; 232 hypercube_topology(double scaling=1.0)233 explicit hypercube_topology(double scaling = 1.0) 234 : gen_ptr(new RandomNumberGenerator) 235 , rand(new rand_t(*gen_ptr)) 236 , scaling(scaling) 237 { 238 } 239 hypercube_topology(RandomNumberGenerator & gen,double scaling=1.0)240 hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0) 241 : gen_ptr(), rand(new rand_t(gen)), scaling(scaling) 242 { 243 } 244 random_point() const245 point_type random_point() const 246 { 247 point_type p; 248 for (std::size_t i = 0; i < Dims; ++i) 249 p[i] = (*rand)() * scaling; 250 return p; 251 } 252 bound(point_type a) const253 point_type bound(point_type a) const 254 { 255 BOOST_USING_STD_MIN(); 256 BOOST_USING_STD_MAX(); 257 point_type p; 258 for (std::size_t i = 0; i < Dims; ++i) 259 p[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION( 260 scaling, max BOOST_PREVENT_MACRO_SUBSTITUTION(-scaling, a[i])); 261 return p; 262 } 263 distance_from_boundary(point_type a) const264 double distance_from_boundary(point_type a) const 265 { 266 BOOST_USING_STD_MIN(); 267 BOOST_USING_STD_MAX(); 268 #ifndef BOOST_NO_STDC_NAMESPACE 269 using std::abs; 270 #endif 271 BOOST_STATIC_ASSERT(Dims >= 1); 272 double dist = abs(scaling - a[0]); 273 for (std::size_t i = 1; i < Dims; ++i) 274 dist = min BOOST_PREVENT_MACRO_SUBSTITUTION( 275 dist, abs(scaling - a[i])); 276 return dist; 277 } 278 center() const279 point_type center() const 280 { 281 point_type result; 282 for (std::size_t i = 0; i < Dims; ++i) 283 result[i] = scaling * .5; 284 return result; 285 } 286 origin() const287 point_type origin() const 288 { 289 point_type result; 290 for (std::size_t i = 0; i < Dims; ++i) 291 result[i] = 0; 292 return result; 293 } 294 extent() const295 point_difference_type extent() const 296 { 297 point_difference_type result; 298 for (std::size_t i = 0; i < Dims; ++i) 299 result[i] = scaling; 300 return result; 301 } 302 303 private: 304 shared_ptr< RandomNumberGenerator > gen_ptr; 305 shared_ptr< rand_t > rand; 306 double scaling; 307 }; 308 309 template < typename RandomNumberGenerator = minstd_rand > 310 class square_topology : public hypercube_topology< 2, RandomNumberGenerator > 311 { 312 typedef hypercube_topology< 2, RandomNumberGenerator > inherited; 313 314 public: square_topology(double scaling=1.0)315 explicit square_topology(double scaling = 1.0) : inherited(scaling) {} 316 square_topology(RandomNumberGenerator & gen,double scaling=1.0)317 square_topology(RandomNumberGenerator& gen, double scaling = 1.0) 318 : inherited(gen, scaling) 319 { 320 } 321 }; 322 323 template < typename RandomNumberGenerator = minstd_rand > 324 class rectangle_topology : public convex_topology< 2 > 325 { 326 typedef uniform_01< RandomNumberGenerator, double > rand_t; 327 328 public: rectangle_topology(double left,double top,double right,double bottom)329 rectangle_topology(double left, double top, double right, double bottom) 330 : gen_ptr(new RandomNumberGenerator) 331 , rand(new rand_t(*gen_ptr)) 332 , left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(left, right)) 333 , top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(top, bottom)) 334 , right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION(left, right)) 335 , bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION(top, bottom)) 336 { 337 } 338 rectangle_topology(RandomNumberGenerator & gen,double left,double top,double right,double bottom)339 rectangle_topology(RandomNumberGenerator& gen, double left, double top, 340 double right, double bottom) 341 : gen_ptr() 342 , rand(new rand_t(gen)) 343 , left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(left, right)) 344 , top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(top, bottom)) 345 , right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION(left, right)) 346 , bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION(top, bottom)) 347 { 348 } 349 350 typedef typename convex_topology< 2 >::point_type point_type; 351 typedef typename convex_topology< 2 >::point_difference_type 352 point_difference_type; 353 random_point() const354 point_type random_point() const 355 { 356 point_type p; 357 p[0] = (*rand)() * (right - left) + left; 358 p[1] = (*rand)() * (bottom - top) + top; 359 return p; 360 } 361 bound(point_type a) const362 point_type bound(point_type a) const 363 { 364 BOOST_USING_STD_MIN(); 365 BOOST_USING_STD_MAX(); 366 point_type p; 367 p[0] = min BOOST_PREVENT_MACRO_SUBSTITUTION( 368 right, max BOOST_PREVENT_MACRO_SUBSTITUTION(left, a[0])); 369 p[1] = min BOOST_PREVENT_MACRO_SUBSTITUTION( 370 bottom, max BOOST_PREVENT_MACRO_SUBSTITUTION(top, a[1])); 371 return p; 372 } 373 distance_from_boundary(point_type a) const374 double distance_from_boundary(point_type a) const 375 { 376 BOOST_USING_STD_MIN(); 377 BOOST_USING_STD_MAX(); 378 #ifndef BOOST_NO_STDC_NAMESPACE 379 using std::abs; 380 #endif 381 double dist = abs(left - a[0]); 382 dist = min BOOST_PREVENT_MACRO_SUBSTITUTION(dist, abs(right - a[0])); 383 dist = min BOOST_PREVENT_MACRO_SUBSTITUTION(dist, abs(top - a[1])); 384 dist = min BOOST_PREVENT_MACRO_SUBSTITUTION(dist, abs(bottom - a[1])); 385 return dist; 386 } 387 center() const388 point_type center() const 389 { 390 point_type result; 391 result[0] = (left + right) / 2.; 392 result[1] = (top + bottom) / 2.; 393 return result; 394 } 395 origin() const396 point_type origin() const 397 { 398 point_type result; 399 result[0] = left; 400 result[1] = top; 401 return result; 402 } 403 extent() const404 point_difference_type extent() const 405 { 406 point_difference_type result; 407 result[0] = right - left; 408 result[1] = bottom - top; 409 return result; 410 } 411 412 private: 413 shared_ptr< RandomNumberGenerator > gen_ptr; 414 shared_ptr< rand_t > rand; 415 double left, top, right, bottom; 416 }; 417 418 template < typename RandomNumberGenerator = minstd_rand > 419 class cube_topology : public hypercube_topology< 3, RandomNumberGenerator > 420 { 421 typedef hypercube_topology< 3, RandomNumberGenerator > inherited; 422 423 public: cube_topology(double scaling=1.0)424 explicit cube_topology(double scaling = 1.0) : inherited(scaling) {} 425 cube_topology(RandomNumberGenerator & gen,double scaling=1.0)426 cube_topology(RandomNumberGenerator& gen, double scaling = 1.0) 427 : inherited(gen, scaling) 428 { 429 } 430 }; 431 432 template < std::size_t Dims, typename RandomNumberGenerator = minstd_rand > 433 class ball_topology : public convex_topology< Dims > 434 { 435 typedef uniform_01< RandomNumberGenerator, double > rand_t; 436 437 public: 438 typedef typename convex_topology< Dims >::point_type point_type; 439 typedef typename convex_topology< Dims >::point_difference_type 440 point_difference_type; 441 ball_topology(double radius=1.0)442 explicit ball_topology(double radius = 1.0) 443 : gen_ptr(new RandomNumberGenerator) 444 , rand(new rand_t(*gen_ptr)) 445 , radius(radius) 446 { 447 } 448 ball_topology(RandomNumberGenerator & gen,double radius=1.0)449 ball_topology(RandomNumberGenerator& gen, double radius = 1.0) 450 : gen_ptr(), rand(new rand_t(gen)), radius(radius) 451 { 452 } 453 random_point() const454 point_type random_point() const 455 { 456 point_type p; 457 double dist_sum; 458 do 459 { 460 dist_sum = 0.0; 461 for (std::size_t i = 0; i < Dims; ++i) 462 { 463 double x = (*rand)() * 2 * radius - radius; 464 p[i] = x; 465 dist_sum += x * x; 466 } 467 } while (dist_sum > radius * radius); 468 return p; 469 } 470 bound(point_type a) const471 point_type bound(point_type a) const 472 { 473 BOOST_USING_STD_MIN(); 474 BOOST_USING_STD_MAX(); 475 double r = 0.; 476 for (std::size_t i = 0; i < Dims; ++i) 477 r = boost::math::hypot(r, a[i]); 478 if (r <= radius) 479 return a; 480 double scaling_factor = radius / r; 481 point_type p; 482 for (std::size_t i = 0; i < Dims; ++i) 483 p[i] = a[i] * scaling_factor; 484 return p; 485 } 486 distance_from_boundary(point_type a) const487 double distance_from_boundary(point_type a) const 488 { 489 double r = 0.; 490 for (std::size_t i = 0; i < Dims; ++i) 491 r = boost::math::hypot(r, a[i]); 492 return radius - r; 493 } 494 center() const495 point_type center() const 496 { 497 point_type result; 498 for (std::size_t i = 0; i < Dims; ++i) 499 result[i] = 0; 500 return result; 501 } 502 origin() const503 point_type origin() const 504 { 505 point_type result; 506 for (std::size_t i = 0; i < Dims; ++i) 507 result[i] = -radius; 508 return result; 509 } 510 extent() const511 point_difference_type extent() const 512 { 513 point_difference_type result; 514 for (std::size_t i = 0; i < Dims; ++i) 515 result[i] = 2. * radius; 516 return result; 517 } 518 519 private: 520 shared_ptr< RandomNumberGenerator > gen_ptr; 521 shared_ptr< rand_t > rand; 522 double radius; 523 }; 524 525 template < typename RandomNumberGenerator = minstd_rand > 526 class circle_topology : public ball_topology< 2, RandomNumberGenerator > 527 { 528 typedef ball_topology< 2, RandomNumberGenerator > inherited; 529 530 public: circle_topology(double radius=1.0)531 explicit circle_topology(double radius = 1.0) : inherited(radius) {} 532 circle_topology(RandomNumberGenerator & gen,double radius=1.0)533 circle_topology(RandomNumberGenerator& gen, double radius = 1.0) 534 : inherited(gen, radius) 535 { 536 } 537 }; 538 539 template < typename RandomNumberGenerator = minstd_rand > 540 class sphere_topology : public ball_topology< 3, RandomNumberGenerator > 541 { 542 typedef ball_topology< 3, RandomNumberGenerator > inherited; 543 544 public: sphere_topology(double radius=1.0)545 explicit sphere_topology(double radius = 1.0) : inherited(radius) {} 546 sphere_topology(RandomNumberGenerator & gen,double radius=1.0)547 sphere_topology(RandomNumberGenerator& gen, double radius = 1.0) 548 : inherited(gen, radius) 549 { 550 } 551 }; 552 553 template < typename RandomNumberGenerator = minstd_rand > class heart_topology 554 { 555 // Heart is defined as the union of three shapes: 556 // Square w/ corners (+-1000, -1000), (0, 0), (0, -2000) 557 // Circle centered at (-500, -500) radius 500*sqrt(2) 558 // Circle centered at (500, -500) radius 500*sqrt(2) 559 // Bounding box (-1000, -2000) - (1000, 500*(sqrt(2) - 1)) 560 561 struct point 562 { pointboost::heart_topology::point563 point() 564 { 565 values[0] = 0.0; 566 values[1] = 0.0; 567 } pointboost::heart_topology::point568 point(double x, double y) 569 { 570 values[0] = x; 571 values[1] = y; 572 } 573 operator []boost::heart_topology::point574 double& operator[](std::size_t i) { return values[i]; } operator []boost::heart_topology::point575 double operator[](std::size_t i) const { return values[i]; } 576 577 private: 578 double values[2]; 579 }; 580 in_heart(point p) const581 bool in_heart(point p) const 582 { 583 #ifndef BOOST_NO_STDC_NAMESPACE 584 using std::abs; 585 #endif 586 587 if (p[1] < abs(p[0]) - 2000) 588 return false; // Bottom 589 if (p[1] <= -1000) 590 return true; // Diagonal of square 591 if (boost::math::hypot(p[0] - -500, p[1] - -500) 592 <= 500. * boost::math::constants::root_two< double >()) 593 return true; // Left circle 594 if (boost::math::hypot(p[0] - 500, p[1] - -500) 595 <= 500. * boost::math::constants::root_two< double >()) 596 return true; // Right circle 597 return false; 598 } 599 segment_within_heart(point p1,point p2) const600 bool segment_within_heart(point p1, point p2) const 601 { 602 // Assumes that p1 and p2 are within the heart 603 if ((p1[0] < 0) == (p2[0] < 0)) 604 return true; // Same side of symmetry line 605 if (p1[0] == p2[0]) 606 return true; // Vertical 607 double slope = (p2[1] - p1[1]) / (p2[0] - p1[0]); 608 double intercept = p1[1] - p1[0] * slope; 609 if (intercept > 0) 610 return false; // Crosses between circles 611 return true; 612 } 613 614 typedef uniform_01< RandomNumberGenerator, double > rand_t; 615 616 public: 617 typedef point point_type; 618 heart_topology()619 heart_topology() 620 : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)) 621 { 622 } 623 heart_topology(RandomNumberGenerator & gen)624 heart_topology(RandomNumberGenerator& gen) 625 : gen_ptr(), rand(new rand_t(gen)) 626 { 627 } 628 random_point() const629 point random_point() const 630 { 631 point result; 632 do 633 { 634 result[0] = (*rand)() 635 * (1000 636 + 1000 * boost::math::constants::root_two< double >()) 637 - (500 + 500 * boost::math::constants::root_two< double >()); 638 result[1] = (*rand)() 639 * (2000 640 + 500 641 * (boost::math::constants::root_two< double >() 642 - 1)) 643 - 2000; 644 } while (!in_heart(result)); 645 return result; 646 } 647 648 // Not going to provide clipping to bounding region or distance from 649 // boundary 650 distance(point a,point b) const651 double distance(point a, point b) const 652 { 653 if (segment_within_heart(a, b)) 654 { 655 // Straight line 656 return boost::math::hypot(b[0] - a[0], b[1] - a[1]); 657 } 658 else 659 { 660 // Straight line bending around (0, 0) 661 return boost::math::hypot(a[0], a[1]) 662 + boost::math::hypot(b[0], b[1]); 663 } 664 } 665 move_position_toward(point a,double fraction,point b) const666 point move_position_toward(point a, double fraction, point b) const 667 { 668 if (segment_within_heart(a, b)) 669 { 670 // Straight line 671 return point(a[0] + (b[0] - a[0]) * fraction, 672 a[1] + (b[1] - a[1]) * fraction); 673 } 674 else 675 { 676 double distance_to_point_a = boost::math::hypot(a[0], a[1]); 677 double distance_to_point_b = boost::math::hypot(b[0], b[1]); 678 double location_of_point = distance_to_point_a 679 / (distance_to_point_a + distance_to_point_b); 680 if (fraction < location_of_point) 681 return point(a[0] * (1 - fraction / location_of_point), 682 a[1] * (1 - fraction / location_of_point)); 683 else 684 return point(b[0] 685 * ((fraction - location_of_point) 686 / (1 - location_of_point)), 687 b[1] 688 * ((fraction - location_of_point) 689 / (1 - location_of_point))); 690 } 691 } 692 693 private: 694 shared_ptr< RandomNumberGenerator > gen_ptr; 695 shared_ptr< rand_t > rand; 696 }; 697 698 } // namespace boost 699 700 #endif // BOOST_GRAPH_TOPOLOGY_HPP 701