9
3

topology.hpp 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598
  1. // Copyright 2009 The Trustees of Indiana University.
  2. // Distributed under the Boost Software License, Version 1.0.
  3. // (See accompanying file LICENSE_1_0.txt or copy at
  4. // http://www.boost.org/LICENSE_1_0.txt)
  5. // Authors: Jeremiah Willcock
  6. // Douglas Gregor
  7. // Andrew Lumsdaine
  8. #ifndef BOOST_GRAPH_TOPOLOGY_HPP
  9. #define BOOST_GRAPH_TOPOLOGY_HPP
  10. #include <boost/config/no_tr1/cmath.hpp>
  11. #include <cmath>
  12. #include <boost/random/uniform_01.hpp>
  13. #include <boost/random/linear_congruential.hpp>
  14. #include <boost/math/constants/constants.hpp> // For root_two
  15. #include <boost/algorithm/minmax.hpp>
  16. #include <boost/config.hpp> // For BOOST_STATIC_CONSTANT
  17. #include <boost/math/special_functions/hypot.hpp>
  18. // Classes and concepts to represent points in a space, with distance and move
  19. // operations (used for Gurson-Atun layout), plus other things like bounding
  20. // boxes used for other layout algorithms.
  21. namespace boost {
  22. /***********************************************************
  23. * Topologies *
  24. ***********************************************************/
  25. template<std::size_t Dims>
  26. class convex_topology
  27. {
  28. public: // For VisualAge C++
  29. struct point
  30. {
  31. BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims);
  32. point() { }
  33. double& operator[](std::size_t i) {return values[i];}
  34. const double& operator[](std::size_t i) const {return values[i];}
  35. private:
  36. double values[Dims];
  37. };
  38. public: // For VisualAge C++
  39. struct point_difference
  40. {
  41. BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims);
  42. point_difference() {
  43. for (std::size_t i = 0; i < Dims; ++i) values[i] = 0.;
  44. }
  45. double& operator[](std::size_t i) {return values[i];}
  46. const double& operator[](std::size_t i) const {return values[i];}
  47. friend point_difference operator+(const point_difference& a, const point_difference& b) {
  48. point_difference result;
  49. for (std::size_t i = 0; i < Dims; ++i)
  50. result[i] = a[i] + b[i];
  51. return result;
  52. }
  53. friend point_difference& operator+=(point_difference& a, const point_difference& b) {
  54. for (std::size_t i = 0; i < Dims; ++i)
  55. a[i] += b[i];
  56. return a;
  57. }
  58. friend point_difference operator-(const point_difference& a) {
  59. point_difference result;
  60. for (std::size_t i = 0; i < Dims; ++i)
  61. result[i] = -a[i];
  62. return result;
  63. }
  64. friend point_difference operator-(const point_difference& a, const point_difference& b) {
  65. point_difference result;
  66. for (std::size_t i = 0; i < Dims; ++i)
  67. result[i] = a[i] - b[i];
  68. return result;
  69. }
  70. friend point_difference& operator-=(point_difference& a, const point_difference& b) {
  71. for (std::size_t i = 0; i < Dims; ++i)
  72. a[i] -= b[i];
  73. return a;
  74. }
  75. friend point_difference operator*(const point_difference& a, const point_difference& b) {
  76. point_difference result;
  77. for (std::size_t i = 0; i < Dims; ++i)
  78. result[i] = a[i] * b[i];
  79. return result;
  80. }
  81. friend point_difference operator*(const point_difference& a, double b) {
  82. point_difference result;
  83. for (std::size_t i = 0; i < Dims; ++i)
  84. result[i] = a[i] * b;
  85. return result;
  86. }
  87. friend point_difference operator*(double a, const point_difference& b) {
  88. point_difference result;
  89. for (std::size_t i = 0; i < Dims; ++i)
  90. result[i] = a * b[i];
  91. return result;
  92. }
  93. friend point_difference operator/(const point_difference& a, const point_difference& b) {
  94. point_difference result;
  95. for (std::size_t i = 0; i < Dims; ++i)
  96. result[i] = (b[i] == 0.) ? 0. : a[i] / b[i];
  97. return result;
  98. }
  99. friend double dot(const point_difference& a, const point_difference& b) {
  100. double result = 0;
  101. for (std::size_t i = 0; i < Dims; ++i)
  102. result += a[i] * b[i];
  103. return result;
  104. }
  105. private:
  106. double values[Dims];
  107. };
  108. public:
  109. typedef point point_type;
  110. typedef point_difference point_difference_type;
  111. double distance(point a, point b) const
  112. {
  113. double dist = 0.;
  114. for (std::size_t i = 0; i < Dims; ++i) {
  115. double diff = b[i] - a[i];
  116. dist = boost::math::hypot(dist, diff);
  117. }
  118. // Exact properties of the distance are not important, as long as
  119. // < on what this returns matches real distances; l_2 is used because
  120. // Fruchterman-Reingold also uses this code and it relies on l_2.
  121. return dist;
  122. }
  123. point move_position_toward(point a, double fraction, point b) const
  124. {
  125. point result;
  126. for (std::size_t i = 0; i < Dims; ++i)
  127. result[i] = a[i] + (b[i] - a[i]) * fraction;
  128. return result;
  129. }
  130. point_difference difference(point a, point b) const {
  131. point_difference result;
  132. for (std::size_t i = 0; i < Dims; ++i)
  133. result[i] = a[i] - b[i];
  134. return result;
  135. }
  136. point adjust(point a, point_difference delta) const {
  137. point result;
  138. for (std::size_t i = 0; i < Dims; ++i)
  139. result[i] = a[i] + delta[i];
  140. return result;
  141. }
  142. point pointwise_min(point a, point b) const {
  143. BOOST_USING_STD_MIN();
  144. point result;
  145. for (std::size_t i = 0; i < Dims; ++i)
  146. result[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]);
  147. return result;
  148. }
  149. point pointwise_max(point a, point b) const {
  150. BOOST_USING_STD_MAX();
  151. point result;
  152. for (std::size_t i = 0; i < Dims; ++i)
  153. result[i] = max BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]);
  154. return result;
  155. }
  156. double norm(point_difference delta) const {
  157. double n = 0.;
  158. for (std::size_t i = 0; i < Dims; ++i)
  159. n = boost::math::hypot(n, delta[i]);
  160. return n;
  161. }
  162. double volume(point_difference delta) const {
  163. double n = 1.;
  164. for (std::size_t i = 0; i < Dims; ++i)
  165. n *= delta[i];
  166. return n;
  167. }
  168. };
  169. template<std::size_t Dims,
  170. typename RandomNumberGenerator = minstd_rand>
  171. class hypercube_topology : public convex_topology<Dims>
  172. {
  173. typedef uniform_01<RandomNumberGenerator, double> rand_t;
  174. public:
  175. typedef typename convex_topology<Dims>::point_type point_type;
  176. typedef typename convex_topology<Dims>::point_difference_type point_difference_type;
  177. explicit hypercube_topology(double scaling = 1.0)
  178. : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
  179. scaling(scaling)
  180. { }
  181. hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
  182. : gen_ptr(), rand(new rand_t(gen)), scaling(scaling) { }
  183. point_type random_point() const
  184. {
  185. point_type p;
  186. for (std::size_t i = 0; i < Dims; ++i)
  187. p[i] = (*rand)() * scaling;
  188. return p;
  189. }
  190. point_type bound(point_type a) const
  191. {
  192. BOOST_USING_STD_MIN();
  193. BOOST_USING_STD_MAX();
  194. point_type p;
  195. for (std::size_t i = 0; i < Dims; ++i)
  196. p[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (scaling, max BOOST_PREVENT_MACRO_SUBSTITUTION (-scaling, a[i]));
  197. return p;
  198. }
  199. double distance_from_boundary(point_type a) const
  200. {
  201. BOOST_USING_STD_MIN();
  202. BOOST_USING_STD_MAX();
  203. #ifndef BOOST_NO_STDC_NAMESPACE
  204. using std::abs;
  205. #endif
  206. BOOST_STATIC_ASSERT (Dims >= 1);
  207. double dist = abs(scaling - a[0]);
  208. for (std::size_t i = 1; i < Dims; ++i)
  209. dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(scaling - a[i]));
  210. return dist;
  211. }
  212. point_type center() const {
  213. point_type result;
  214. for (std::size_t i = 0; i < Dims; ++i)
  215. result[i] = scaling * .5;
  216. return result;
  217. }
  218. point_type origin() const {
  219. point_type result;
  220. for (std::size_t i = 0; i < Dims; ++i)
  221. result[i] = 0;
  222. return result;
  223. }
  224. point_difference_type extent() const {
  225. point_difference_type result;
  226. for (std::size_t i = 0; i < Dims; ++i)
  227. result[i] = scaling;
  228. return result;
  229. }
  230. private:
  231. shared_ptr<RandomNumberGenerator> gen_ptr;
  232. shared_ptr<rand_t> rand;
  233. double scaling;
  234. };
  235. template<typename RandomNumberGenerator = minstd_rand>
  236. class square_topology : public hypercube_topology<2, RandomNumberGenerator>
  237. {
  238. typedef hypercube_topology<2, RandomNumberGenerator> inherited;
  239. public:
  240. explicit square_topology(double scaling = 1.0) : inherited(scaling) { }
  241. square_topology(RandomNumberGenerator& gen, double scaling = 1.0)
  242. : inherited(gen, scaling) { }
  243. };
  244. template<typename RandomNumberGenerator = minstd_rand>
  245. class rectangle_topology : public convex_topology<2>
  246. {
  247. typedef uniform_01<RandomNumberGenerator, double> rand_t;
  248. public:
  249. rectangle_topology(double left, double top, double right, double bottom)
  250. : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
  251. left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
  252. top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)),
  253. right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
  254. bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)) { }
  255. rectangle_topology(RandomNumberGenerator& gen, double left, double top, double right, double bottom)
  256. : gen_ptr(), rand(new rand_t(gen)),
  257. left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
  258. top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)),
  259. right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
  260. bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)) { }
  261. typedef typename convex_topology<2>::point_type point_type;
  262. typedef typename convex_topology<2>::point_difference_type point_difference_type;
  263. point_type random_point() const
  264. {
  265. point_type p;
  266. p[0] = (*rand)() * (right - left) + left;
  267. p[1] = (*rand)() * (bottom - top) + top;
  268. return p;
  269. }
  270. point_type bound(point_type a) const
  271. {
  272. BOOST_USING_STD_MIN();
  273. BOOST_USING_STD_MAX();
  274. point_type p;
  275. p[0] = min BOOST_PREVENT_MACRO_SUBSTITUTION (right, max BOOST_PREVENT_MACRO_SUBSTITUTION (left, a[0]));
  276. p[1] = min BOOST_PREVENT_MACRO_SUBSTITUTION (bottom, max BOOST_PREVENT_MACRO_SUBSTITUTION (top, a[1]));
  277. return p;
  278. }
  279. double distance_from_boundary(point_type a) const
  280. {
  281. BOOST_USING_STD_MIN();
  282. BOOST_USING_STD_MAX();
  283. #ifndef BOOST_NO_STDC_NAMESPACE
  284. using std::abs;
  285. #endif
  286. double dist = abs(left - a[0]);
  287. dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(right - a[0]));
  288. dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(top - a[1]));
  289. dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(bottom - a[1]));
  290. return dist;
  291. }
  292. point_type center() const {
  293. point_type result;
  294. result[0] = (left + right) / 2.;
  295. result[1] = (top + bottom) / 2.;
  296. return result;
  297. }
  298. point_type origin() const {
  299. point_type result;
  300. result[0] = left;
  301. result[1] = top;
  302. return result;
  303. }
  304. point_difference_type extent() const {
  305. point_difference_type result;
  306. result[0] = right - left;
  307. result[1] = bottom - top;
  308. return result;
  309. }
  310. private:
  311. shared_ptr<RandomNumberGenerator> gen_ptr;
  312. shared_ptr<rand_t> rand;
  313. double left, top, right, bottom;
  314. };
  315. template<typename RandomNumberGenerator = minstd_rand>
  316. class cube_topology : public hypercube_topology<3, RandomNumberGenerator>
  317. {
  318. typedef hypercube_topology<3, RandomNumberGenerator> inherited;
  319. public:
  320. explicit cube_topology(double scaling = 1.0) : inherited(scaling) { }
  321. cube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
  322. : inherited(gen, scaling) { }
  323. };
  324. template<std::size_t Dims,
  325. typename RandomNumberGenerator = minstd_rand>
  326. class ball_topology : public convex_topology<Dims>
  327. {
  328. typedef uniform_01<RandomNumberGenerator, double> rand_t;
  329. public:
  330. typedef typename convex_topology<Dims>::point_type point_type;
  331. typedef typename convex_topology<Dims>::point_difference_type point_difference_type;
  332. explicit ball_topology(double radius = 1.0)
  333. : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
  334. radius(radius)
  335. { }
  336. ball_topology(RandomNumberGenerator& gen, double radius = 1.0)
  337. : gen_ptr(), rand(new rand_t(gen)), radius(radius) { }
  338. point_type random_point() const
  339. {
  340. point_type p;
  341. double dist_sum;
  342. do {
  343. dist_sum = 0.0;
  344. for (std::size_t i = 0; i < Dims; ++i) {
  345. double x = (*rand)() * 2*radius - radius;
  346. p[i] = x;
  347. dist_sum += x * x;
  348. }
  349. } while (dist_sum > radius*radius);
  350. return p;
  351. }
  352. point_type bound(point_type a) const
  353. {
  354. BOOST_USING_STD_MIN();
  355. BOOST_USING_STD_MAX();
  356. double r = 0.;
  357. for (std::size_t i = 0; i < Dims; ++i)
  358. r = boost::math::hypot(r, a[i]);
  359. if (r <= radius) return a;
  360. double scaling_factor = radius / r;
  361. point_type p;
  362. for (std::size_t i = 0; i < Dims; ++i)
  363. p[i] = a[i] * scaling_factor;
  364. return p;
  365. }
  366. double distance_from_boundary(point_type a) const
  367. {
  368. double r = 0.;
  369. for (std::size_t i = 0; i < Dims; ++i)
  370. r = boost::math::hypot(r, a[i]);
  371. return radius - r;
  372. }
  373. point_type center() const {
  374. point_type result;
  375. for (std::size_t i = 0; i < Dims; ++i)
  376. result[i] = 0;
  377. return result;
  378. }
  379. point_type origin() const {
  380. point_type result;
  381. for (std::size_t i = 0; i < Dims; ++i)
  382. result[i] = -radius;
  383. return result;
  384. }
  385. point_difference_type extent() const {
  386. point_difference_type result;
  387. for (std::size_t i = 0; i < Dims; ++i)
  388. result[i] = 2. * radius;
  389. return result;
  390. }
  391. private:
  392. shared_ptr<RandomNumberGenerator> gen_ptr;
  393. shared_ptr<rand_t> rand;
  394. double radius;
  395. };
  396. template<typename RandomNumberGenerator = minstd_rand>
  397. class circle_topology : public ball_topology<2, RandomNumberGenerator>
  398. {
  399. typedef ball_topology<2, RandomNumberGenerator> inherited;
  400. public:
  401. explicit circle_topology(double radius = 1.0) : inherited(radius) { }
  402. circle_topology(RandomNumberGenerator& gen, double radius = 1.0)
  403. : inherited(gen, radius) { }
  404. };
  405. template<typename RandomNumberGenerator = minstd_rand>
  406. class sphere_topology : public ball_topology<3, RandomNumberGenerator>
  407. {
  408. typedef ball_topology<3, RandomNumberGenerator> inherited;
  409. public:
  410. explicit sphere_topology(double radius = 1.0) : inherited(radius) { }
  411. sphere_topology(RandomNumberGenerator& gen, double radius = 1.0)
  412. : inherited(gen, radius) { }
  413. };
  414. template<typename RandomNumberGenerator = minstd_rand>
  415. class heart_topology
  416. {
  417. // Heart is defined as the union of three shapes:
  418. // Square w/ corners (+-1000, -1000), (0, 0), (0, -2000)
  419. // Circle centered at (-500, -500) radius 500*sqrt(2)
  420. // Circle centered at (500, -500) radius 500*sqrt(2)
  421. // Bounding box (-1000, -2000) - (1000, 500*(sqrt(2) - 1))
  422. struct point
  423. {
  424. point() { values[0] = 0.0; values[1] = 0.0; }
  425. point(double x, double y) { values[0] = x; values[1] = y; }
  426. double& operator[](std::size_t i) { return values[i]; }
  427. double operator[](std::size_t i) const { return values[i]; }
  428. private:
  429. double values[2];
  430. };
  431. bool in_heart(point p) const
  432. {
  433. #ifndef BOOST_NO_STDC_NAMESPACE
  434. using std::abs;
  435. #endif
  436. if (p[1] < abs(p[0]) - 2000) return false; // Bottom
  437. if (p[1] <= -1000) return true; // Diagonal of square
  438. if (boost::math::hypot(p[0] - -500, p[1] - -500) <= 500. * boost::math::constants::root_two<double>())
  439. return true; // Left circle
  440. if (boost::math::hypot(p[0] - 500, p[1] - -500) <= 500. * boost::math::constants::root_two<double>())
  441. return true; // Right circle
  442. return false;
  443. }
  444. bool segment_within_heart(point p1, point p2) const
  445. {
  446. // Assumes that p1 and p2 are within the heart
  447. if ((p1[0] < 0) == (p2[0] < 0)) return true; // Same side of symmetry line
  448. if (p1[0] == p2[0]) return true; // Vertical
  449. double slope = (p2[1] - p1[1]) / (p2[0] - p1[0]);
  450. double intercept = p1[1] - p1[0] * slope;
  451. if (intercept > 0) return false; // Crosses between circles
  452. return true;
  453. }
  454. typedef uniform_01<RandomNumberGenerator, double> rand_t;
  455. public:
  456. typedef point point_type;
  457. heart_topology()
  458. : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)) { }
  459. heart_topology(RandomNumberGenerator& gen)
  460. : gen_ptr(), rand(new rand_t(gen)) { }
  461. point random_point() const
  462. {
  463. point result;
  464. do {
  465. result[0] = (*rand)() * (1000 + 1000 * boost::math::constants::root_two<double>()) - (500 + 500 * boost::math::constants::root_two<double>());
  466. result[1] = (*rand)() * (2000 + 500 * (boost::math::constants::root_two<double>() - 1)) - 2000;
  467. } while (!in_heart(result));
  468. return result;
  469. }
  470. // Not going to provide clipping to bounding region or distance from boundary
  471. double distance(point a, point b) const
  472. {
  473. if (segment_within_heart(a, b)) {
  474. // Straight line
  475. return boost::math::hypot(b[0] - a[0], b[1] - a[1]);
  476. } else {
  477. // Straight line bending around (0, 0)
  478. return boost::math::hypot(a[0], a[1]) + boost::math::hypot(b[0], b[1]);
  479. }
  480. }
  481. point move_position_toward(point a, double fraction, point b) const
  482. {
  483. if (segment_within_heart(a, b)) {
  484. // Straight line
  485. return point(a[0] + (b[0] - a[0]) * fraction,
  486. a[1] + (b[1] - a[1]) * fraction);
  487. } else {
  488. double distance_to_point_a = boost::math::hypot(a[0], a[1]);
  489. double distance_to_point_b = boost::math::hypot(b[0], b[1]);
  490. double location_of_point = distance_to_point_a /
  491. (distance_to_point_a + distance_to_point_b);
  492. if (fraction < location_of_point)
  493. return point(a[0] * (1 - fraction / location_of_point),
  494. a[1] * (1 - fraction / location_of_point));
  495. else
  496. return point(
  497. b[0] * ((fraction - location_of_point) / (1 - location_of_point)),
  498. b[1] * ((fraction - location_of_point) / (1 - location_of_point)));
  499. }
  500. }
  501. private:
  502. shared_ptr<RandomNumberGenerator> gen_ptr;
  503. shared_ptr<rand_t> rand;
  504. };
  505. } // namespace boost
  506. #endif // BOOST_GRAPH_TOPOLOGY_HPP