Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-07-01 08:17:17

0001 // Copyright 2009 The Trustees of Indiana University.
0002 
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 
0007 //  Authors: Jeremiah Willcock
0008 //           Douglas Gregor
0009 //           Andrew Lumsdaine
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 // Classes and concepts to represent points in a space, with distance and move
0025 // operations (used for Gurson-Atun layout), plus other things like bounding
0026 // boxes used for other layout algorithms.
0027 
0028 namespace boost
0029 {
0030 
0031 /***********************************************************
0032  * Topologies                                              *
0033  ***********************************************************/
0034 template < std::size_t Dims > class convex_topology
0035 {
0036 public: // For VisualAge C++
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: // For VisualAge C++
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         // Exact properties of the distance are not important, as long as
0161         // < on what this returns matches real distances; l_2 is used because
0162         // Fruchterman-Reingold also uses this code and it relies on l_2.
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     // Heart is defined as the union of three shapes:
0558     // Square w/ corners (+-1000, -1000), (0, 0), (0, -2000)
0559     // Circle centered at (-500, -500) radius 500*sqrt(2)
0560     // Circle centered at (500, -500) radius 500*sqrt(2)
0561     // Bounding box (-1000, -2000) - (1000, 500*(sqrt(2) - 1))
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; // Bottom
0591         if (p[1] <= -1000)
0592             return true; // Diagonal of square
0593         if (boost::math::hypot(p[0] - -500, p[1] - -500)
0594             <= 500. * boost::math::constants::root_two< double >())
0595             return true; // Left circle
0596         if (boost::math::hypot(p[0] - 500, p[1] - -500)
0597             <= 500. * boost::math::constants::root_two< double >())
0598             return true; // Right circle
0599         return false;
0600     }
0601 
0602     bool segment_within_heart(point p1, point p2) const
0603     {
0604         // Assumes that p1 and p2 are within the heart
0605         if ((p1[0] < 0) == (p2[0] < 0))
0606             return true; // Same side of symmetry line
0607         if (p1[0] == p2[0])
0608             return true; // Vertical
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; // Crosses between circles
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     // Not going to provide clipping to bounding region or distance from
0651     // boundary
0652 
0653     double distance(point a, point b) const
0654     {
0655         if (segment_within_heart(a, b))
0656         {
0657             // Straight line
0658             return boost::math::hypot(b[0] - a[0], b[1] - a[1]);
0659         }
0660         else
0661         {
0662             // Straight line bending around (0, 0)
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             // Straight line
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 } // namespace boost
0701 
0702 #endif // BOOST_GRAPH_TOPOLOGY_HPP