File indexing completed on 2025-07-01 08:17:17
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010 #ifndef BOOST_GRAPH_TOPOLOGY_HPP
0011 #define BOOST_GRAPH_TOPOLOGY_HPP
0012
0013 #include <boost/algorithm/minmax.hpp>
0014 #include <boost/config.hpp> // For BOOST_STATIC_CONSTANT
0015 #include <boost/config/no_tr1/cmath.hpp>
0016 #include <boost/math/constants/constants.hpp> // For root_two
0017 #include <boost/math/special_functions/hypot.hpp>
0018 #include <boost/random/uniform_01.hpp>
0019 #include <boost/random/linear_congruential.hpp>
0020 #include <boost/shared_ptr.hpp>
0021
0022 #include <cmath>
0023
0024
0025
0026
0027
0028 namespace boost
0029 {
0030
0031
0032
0033
0034 template < std::size_t Dims > class convex_topology
0035 {
0036 public:
0037 struct point
0038 {
0039 BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims);
0040 point() {}
0041 double& operator[](std::size_t i) { return values[i]; }
0042 const double& operator[](std::size_t i) const { return values[i]; }
0043
0044 private:
0045 double values[Dims];
0046 };
0047
0048 public:
0049 struct point_difference
0050 {
0051 BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims);
0052 point_difference()
0053 {
0054 for (std::size_t i = 0; i < Dims; ++i)
0055 values[i] = 0.;
0056 }
0057 double& operator[](std::size_t i) { return values[i]; }
0058 const double& operator[](std::size_t i) const { return values[i]; }
0059
0060 friend point_difference operator+(
0061 const point_difference& a, const point_difference& b)
0062 {
0063 point_difference result;
0064 for (std::size_t i = 0; i < Dims; ++i)
0065 result[i] = a[i] + b[i];
0066 return result;
0067 }
0068
0069 friend point_difference& operator+=(
0070 point_difference& a, const point_difference& b)
0071 {
0072 for (std::size_t i = 0; i < Dims; ++i)
0073 a[i] += b[i];
0074 return a;
0075 }
0076
0077 friend point_difference operator-(const point_difference& a)
0078 {
0079 point_difference result;
0080 for (std::size_t i = 0; i < Dims; ++i)
0081 result[i] = -a[i];
0082 return result;
0083 }
0084
0085 friend point_difference operator-(
0086 const point_difference& a, const point_difference& b)
0087 {
0088 point_difference result;
0089 for (std::size_t i = 0; i < Dims; ++i)
0090 result[i] = a[i] - b[i];
0091 return result;
0092 }
0093
0094 friend point_difference& operator-=(
0095 point_difference& a, const point_difference& b)
0096 {
0097 for (std::size_t i = 0; i < Dims; ++i)
0098 a[i] -= b[i];
0099 return a;
0100 }
0101
0102 friend point_difference operator*(
0103 const point_difference& a, const point_difference& b)
0104 {
0105 point_difference result;
0106 for (std::size_t i = 0; i < Dims; ++i)
0107 result[i] = a[i] * b[i];
0108 return result;
0109 }
0110
0111 friend point_difference operator*(const point_difference& a, double b)
0112 {
0113 point_difference result;
0114 for (std::size_t i = 0; i < Dims; ++i)
0115 result[i] = a[i] * b;
0116 return result;
0117 }
0118
0119 friend point_difference operator*(double a, const point_difference& b)
0120 {
0121 point_difference result;
0122 for (std::size_t i = 0; i < Dims; ++i)
0123 result[i] = a * b[i];
0124 return result;
0125 }
0126
0127 friend point_difference operator/(
0128 const point_difference& a, const point_difference& b)
0129 {
0130 point_difference result;
0131 for (std::size_t i = 0; i < Dims; ++i)
0132 result[i] = (b[i] == 0.) ? 0. : a[i] / b[i];
0133 return result;
0134 }
0135
0136 friend double dot(const point_difference& a, const point_difference& b)
0137 {
0138 double result = 0;
0139 for (std::size_t i = 0; i < Dims; ++i)
0140 result += a[i] * b[i];
0141 return result;
0142 }
0143
0144 private:
0145 double values[Dims];
0146 };
0147
0148 public:
0149 typedef point point_type;
0150 typedef point_difference point_difference_type;
0151
0152 double distance(point a, point b) const
0153 {
0154 double dist = 0.;
0155 for (std::size_t i = 0; i < Dims; ++i)
0156 {
0157 double diff = b[i] - a[i];
0158 dist = boost::math::hypot(dist, diff);
0159 }
0160
0161
0162
0163 return dist;
0164 }
0165
0166 point move_position_toward(point a, double fraction, point b) const
0167 {
0168 point result;
0169 for (std::size_t i = 0; i < Dims; ++i)
0170 result[i] = a[i] + (b[i] - a[i]) * fraction;
0171 return result;
0172 }
0173
0174 point_difference difference(point a, point b) const
0175 {
0176 point_difference result;
0177 for (std::size_t i = 0; i < Dims; ++i)
0178 result[i] = a[i] - b[i];
0179 return result;
0180 }
0181
0182 point adjust(point a, point_difference delta) const
0183 {
0184 point result;
0185 for (std::size_t i = 0; i < Dims; ++i)
0186 result[i] = a[i] + delta[i];
0187 return result;
0188 }
0189
0190 point pointwise_min(point a, point b) const
0191 {
0192 BOOST_USING_STD_MIN();
0193 point result;
0194 for (std::size_t i = 0; i < Dims; ++i)
0195 result[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION(a[i], b[i]);
0196 return result;
0197 }
0198
0199 point pointwise_max(point a, point b) const
0200 {
0201 BOOST_USING_STD_MAX();
0202 point result;
0203 for (std::size_t i = 0; i < Dims; ++i)
0204 result[i] = max BOOST_PREVENT_MACRO_SUBSTITUTION(a[i], b[i]);
0205 return result;
0206 }
0207
0208 double norm(point_difference delta) const
0209 {
0210 double n = 0.;
0211 for (std::size_t i = 0; i < Dims; ++i)
0212 n = boost::math::hypot(n, delta[i]);
0213 return n;
0214 }
0215
0216 double volume(point_difference delta) const
0217 {
0218 double n = 1.;
0219 for (std::size_t i = 0; i < Dims; ++i)
0220 n *= delta[i];
0221 return n;
0222 }
0223 };
0224
0225 template < std::size_t Dims, typename RandomNumberGenerator = minstd_rand >
0226 class hypercube_topology : public convex_topology< Dims >
0227 {
0228 typedef uniform_01< RandomNumberGenerator, double > rand_t;
0229
0230 public:
0231 typedef typename convex_topology< Dims >::point_type point_type;
0232 typedef typename convex_topology< Dims >::point_difference_type
0233 point_difference_type;
0234
0235 explicit hypercube_topology(double scaling = 1.0)
0236 : gen_ptr(new RandomNumberGenerator)
0237 , rand(new rand_t(*gen_ptr))
0238 , scaling(scaling)
0239 {
0240 }
0241
0242 hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
0243 : gen_ptr(), rand(new rand_t(gen)), scaling(scaling)
0244 {
0245 }
0246
0247 point_type random_point() const
0248 {
0249 point_type p;
0250 for (std::size_t i = 0; i < Dims; ++i)
0251 p[i] = (*rand)() * scaling;
0252 return p;
0253 }
0254
0255 point_type bound(point_type a) const
0256 {
0257 BOOST_USING_STD_MIN();
0258 BOOST_USING_STD_MAX();
0259 point_type p;
0260 for (std::size_t i = 0; i < Dims; ++i)
0261 p[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION(
0262 scaling, max BOOST_PREVENT_MACRO_SUBSTITUTION(-scaling, a[i]));
0263 return p;
0264 }
0265
0266 double distance_from_boundary(point_type a) const
0267 {
0268 BOOST_USING_STD_MIN();
0269 BOOST_USING_STD_MAX();
0270 #ifndef BOOST_NO_STDC_NAMESPACE
0271 using std::abs;
0272 #endif
0273 BOOST_STATIC_ASSERT(Dims >= 1);
0274 double dist = abs(scaling - a[0]);
0275 for (std::size_t i = 1; i < Dims; ++i)
0276 dist = min BOOST_PREVENT_MACRO_SUBSTITUTION(
0277 dist, abs(scaling - a[i]));
0278 return dist;
0279 }
0280
0281 point_type center() const
0282 {
0283 point_type result;
0284 for (std::size_t i = 0; i < Dims; ++i)
0285 result[i] = scaling * .5;
0286 return result;
0287 }
0288
0289 point_type origin() const
0290 {
0291 point_type result;
0292 for (std::size_t i = 0; i < Dims; ++i)
0293 result[i] = 0;
0294 return result;
0295 }
0296
0297 point_difference_type extent() const
0298 {
0299 point_difference_type result;
0300 for (std::size_t i = 0; i < Dims; ++i)
0301 result[i] = scaling;
0302 return result;
0303 }
0304
0305 private:
0306 shared_ptr< RandomNumberGenerator > gen_ptr;
0307 shared_ptr< rand_t > rand;
0308 double scaling;
0309 };
0310
0311 template < typename RandomNumberGenerator = minstd_rand >
0312 class square_topology : public hypercube_topology< 2, RandomNumberGenerator >
0313 {
0314 typedef hypercube_topology< 2, RandomNumberGenerator > inherited;
0315
0316 public:
0317 explicit square_topology(double scaling = 1.0) : inherited(scaling) {}
0318
0319 square_topology(RandomNumberGenerator& gen, double scaling = 1.0)
0320 : inherited(gen, scaling)
0321 {
0322 }
0323 };
0324
0325 template < typename RandomNumberGenerator = minstd_rand >
0326 class rectangle_topology : public convex_topology< 2 >
0327 {
0328 typedef uniform_01< RandomNumberGenerator, double > rand_t;
0329
0330 public:
0331 rectangle_topology(double left, double top, double right, double bottom)
0332 : gen_ptr(new RandomNumberGenerator)
0333 , rand(new rand_t(*gen_ptr))
0334 , left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(left, right))
0335 , top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(top, bottom))
0336 , right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION(left, right))
0337 , bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION(top, bottom))
0338 {
0339 }
0340
0341 rectangle_topology(RandomNumberGenerator& gen, double left, double top,
0342 double right, double bottom)
0343 : gen_ptr()
0344 , rand(new rand_t(gen))
0345 , left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(left, right))
0346 , top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(top, bottom))
0347 , right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION(left, right))
0348 , bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION(top, bottom))
0349 {
0350 }
0351
0352 typedef typename convex_topology< 2 >::point_type point_type;
0353 typedef typename convex_topology< 2 >::point_difference_type
0354 point_difference_type;
0355
0356 point_type random_point() const
0357 {
0358 point_type p;
0359 p[0] = (*rand)() * (right - left) + left;
0360 p[1] = (*rand)() * (bottom - top) + top;
0361 return p;
0362 }
0363
0364 point_type bound(point_type a) const
0365 {
0366 BOOST_USING_STD_MIN();
0367 BOOST_USING_STD_MAX();
0368 point_type p;
0369 p[0] = min BOOST_PREVENT_MACRO_SUBSTITUTION(
0370 right, max BOOST_PREVENT_MACRO_SUBSTITUTION(left, a[0]));
0371 p[1] = min BOOST_PREVENT_MACRO_SUBSTITUTION(
0372 bottom, max BOOST_PREVENT_MACRO_SUBSTITUTION(top, a[1]));
0373 return p;
0374 }
0375
0376 double distance_from_boundary(point_type a) const
0377 {
0378 BOOST_USING_STD_MIN();
0379 BOOST_USING_STD_MAX();
0380 #ifndef BOOST_NO_STDC_NAMESPACE
0381 using std::abs;
0382 #endif
0383 double dist = abs(left - a[0]);
0384 dist = min BOOST_PREVENT_MACRO_SUBSTITUTION(dist, abs(right - a[0]));
0385 dist = min BOOST_PREVENT_MACRO_SUBSTITUTION(dist, abs(top - a[1]));
0386 dist = min BOOST_PREVENT_MACRO_SUBSTITUTION(dist, abs(bottom - a[1]));
0387 return dist;
0388 }
0389
0390 point_type center() const
0391 {
0392 point_type result;
0393 result[0] = (left + right) / 2.;
0394 result[1] = (top + bottom) / 2.;
0395 return result;
0396 }
0397
0398 point_type origin() const
0399 {
0400 point_type result;
0401 result[0] = left;
0402 result[1] = top;
0403 return result;
0404 }
0405
0406 point_difference_type extent() const
0407 {
0408 point_difference_type result;
0409 result[0] = right - left;
0410 result[1] = bottom - top;
0411 return result;
0412 }
0413
0414 private:
0415 shared_ptr< RandomNumberGenerator > gen_ptr;
0416 shared_ptr< rand_t > rand;
0417 double left, top, right, bottom;
0418 };
0419
0420 template < typename RandomNumberGenerator = minstd_rand >
0421 class cube_topology : public hypercube_topology< 3, RandomNumberGenerator >
0422 {
0423 typedef hypercube_topology< 3, RandomNumberGenerator > inherited;
0424
0425 public:
0426 explicit cube_topology(double scaling = 1.0) : inherited(scaling) {}
0427
0428 cube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
0429 : inherited(gen, scaling)
0430 {
0431 }
0432 };
0433
0434 template < std::size_t Dims, typename RandomNumberGenerator = minstd_rand >
0435 class ball_topology : public convex_topology< Dims >
0436 {
0437 typedef uniform_01< RandomNumberGenerator, double > rand_t;
0438
0439 public:
0440 typedef typename convex_topology< Dims >::point_type point_type;
0441 typedef typename convex_topology< Dims >::point_difference_type
0442 point_difference_type;
0443
0444 explicit ball_topology(double radius = 1.0)
0445 : gen_ptr(new RandomNumberGenerator)
0446 , rand(new rand_t(*gen_ptr))
0447 , radius(radius)
0448 {
0449 }
0450
0451 ball_topology(RandomNumberGenerator& gen, double radius = 1.0)
0452 : gen_ptr(), rand(new rand_t(gen)), radius(radius)
0453 {
0454 }
0455
0456 point_type random_point() const
0457 {
0458 point_type p;
0459 double dist_sum;
0460 do
0461 {
0462 dist_sum = 0.0;
0463 for (std::size_t i = 0; i < Dims; ++i)
0464 {
0465 double x = (*rand)() * 2 * radius - radius;
0466 p[i] = x;
0467 dist_sum += x * x;
0468 }
0469 } while (dist_sum > radius * radius);
0470 return p;
0471 }
0472
0473 point_type bound(point_type a) const
0474 {
0475 BOOST_USING_STD_MIN();
0476 BOOST_USING_STD_MAX();
0477 double r = 0.;
0478 for (std::size_t i = 0; i < Dims; ++i)
0479 r = boost::math::hypot(r, a[i]);
0480 if (r <= radius)
0481 return a;
0482 double scaling_factor = radius / r;
0483 point_type p;
0484 for (std::size_t i = 0; i < Dims; ++i)
0485 p[i] = a[i] * scaling_factor;
0486 return p;
0487 }
0488
0489 double distance_from_boundary(point_type a) const
0490 {
0491 double r = 0.;
0492 for (std::size_t i = 0; i < Dims; ++i)
0493 r = boost::math::hypot(r, a[i]);
0494 return radius - r;
0495 }
0496
0497 point_type center() const
0498 {
0499 point_type result;
0500 for (std::size_t i = 0; i < Dims; ++i)
0501 result[i] = 0;
0502 return result;
0503 }
0504
0505 point_type origin() const
0506 {
0507 point_type result;
0508 for (std::size_t i = 0; i < Dims; ++i)
0509 result[i] = -radius;
0510 return result;
0511 }
0512
0513 point_difference_type extent() const
0514 {
0515 point_difference_type result;
0516 for (std::size_t i = 0; i < Dims; ++i)
0517 result[i] = 2. * radius;
0518 return result;
0519 }
0520
0521 private:
0522 shared_ptr< RandomNumberGenerator > gen_ptr;
0523 shared_ptr< rand_t > rand;
0524 double radius;
0525 };
0526
0527 template < typename RandomNumberGenerator = minstd_rand >
0528 class circle_topology : public ball_topology< 2, RandomNumberGenerator >
0529 {
0530 typedef ball_topology< 2, RandomNumberGenerator > inherited;
0531
0532 public:
0533 explicit circle_topology(double radius = 1.0) : inherited(radius) {}
0534
0535 circle_topology(RandomNumberGenerator& gen, double radius = 1.0)
0536 : inherited(gen, radius)
0537 {
0538 }
0539 };
0540
0541 template < typename RandomNumberGenerator = minstd_rand >
0542 class sphere_topology : public ball_topology< 3, RandomNumberGenerator >
0543 {
0544 typedef ball_topology< 3, RandomNumberGenerator > inherited;
0545
0546 public:
0547 explicit sphere_topology(double radius = 1.0) : inherited(radius) {}
0548
0549 sphere_topology(RandomNumberGenerator& gen, double radius = 1.0)
0550 : inherited(gen, radius)
0551 {
0552 }
0553 };
0554
0555 template < typename RandomNumberGenerator = minstd_rand > class heart_topology
0556 {
0557
0558
0559
0560
0561
0562
0563 struct point
0564 {
0565 point()
0566 {
0567 values[0] = 0.0;
0568 values[1] = 0.0;
0569 }
0570 point(double x, double y)
0571 {
0572 values[0] = x;
0573 values[1] = y;
0574 }
0575
0576 double& operator[](std::size_t i) { return values[i]; }
0577 double operator[](std::size_t i) const { return values[i]; }
0578
0579 private:
0580 double values[2];
0581 };
0582
0583 bool in_heart(point p) const
0584 {
0585 #ifndef BOOST_NO_STDC_NAMESPACE
0586 using std::abs;
0587 #endif
0588
0589 if (p[1] < abs(p[0]) - 2000)
0590 return false;
0591 if (p[1] <= -1000)
0592 return true;
0593 if (boost::math::hypot(p[0] - -500, p[1] - -500)
0594 <= 500. * boost::math::constants::root_two< double >())
0595 return true;
0596 if (boost::math::hypot(p[0] - 500, p[1] - -500)
0597 <= 500. * boost::math::constants::root_two< double >())
0598 return true;
0599 return false;
0600 }
0601
0602 bool segment_within_heart(point p1, point p2) const
0603 {
0604
0605 if ((p1[0] < 0) == (p2[0] < 0))
0606 return true;
0607 if (p1[0] == p2[0])
0608 return true;
0609 double slope = (p2[1] - p1[1]) / (p2[0] - p1[0]);
0610 double intercept = p1[1] - p1[0] * slope;
0611 if (intercept > 0)
0612 return false;
0613 return true;
0614 }
0615
0616 typedef uniform_01< RandomNumberGenerator, double > rand_t;
0617
0618 public:
0619 typedef point point_type;
0620
0621 heart_topology()
0622 : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr))
0623 {
0624 }
0625
0626 heart_topology(RandomNumberGenerator& gen)
0627 : gen_ptr(), rand(new rand_t(gen))
0628 {
0629 }
0630
0631 point random_point() const
0632 {
0633 point result;
0634 do
0635 {
0636 result[0] = (*rand)()
0637 * (1000
0638 + 1000 * boost::math::constants::root_two< double >())
0639 - (500 + 500 * boost::math::constants::root_two< double >());
0640 result[1] = (*rand)()
0641 * (2000
0642 + 500
0643 * (boost::math::constants::root_two< double >()
0644 - 1))
0645 - 2000;
0646 } while (!in_heart(result));
0647 return result;
0648 }
0649
0650
0651
0652
0653 double distance(point a, point b) const
0654 {
0655 if (segment_within_heart(a, b))
0656 {
0657
0658 return boost::math::hypot(b[0] - a[0], b[1] - a[1]);
0659 }
0660 else
0661 {
0662
0663 return boost::math::hypot(a[0], a[1])
0664 + boost::math::hypot(b[0], b[1]);
0665 }
0666 }
0667
0668 point move_position_toward(point a, double fraction, point b) const
0669 {
0670 if (segment_within_heart(a, b))
0671 {
0672
0673 return point(a[0] + (b[0] - a[0]) * fraction,
0674 a[1] + (b[1] - a[1]) * fraction);
0675 }
0676 else
0677 {
0678 double distance_to_point_a = boost::math::hypot(a[0], a[1]);
0679 double distance_to_point_b = boost::math::hypot(b[0], b[1]);
0680 double location_of_point = distance_to_point_a
0681 / (distance_to_point_a + distance_to_point_b);
0682 if (fraction < location_of_point)
0683 return point(a[0] * (1 - fraction / location_of_point),
0684 a[1] * (1 - fraction / location_of_point));
0685 else
0686 return point(b[0]
0687 * ((fraction - location_of_point)
0688 / (1 - location_of_point)),
0689 b[1]
0690 * ((fraction - location_of_point)
0691 / (1 - location_of_point)));
0692 }
0693 }
0694
0695 private:
0696 shared_ptr< RandomNumberGenerator > gen_ptr;
0697 shared_ptr< rand_t > rand;
0698 };
0699
0700 }
0701
0702 #endif