开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
anetmodel.cc
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：21k
源码类别：

通讯编程

开发平台：

Visual C++

anetmodel.cc：源码内容
  1. /*
  2.  * Network model with automatic layout
  3.  *
  4.  * Layout code from nem by Elan Amir
  5.  *
  6.  * $Header: /cvsroot/nsnam/nam-1/anetmodel.cc,v 1.25 2000/11/12 23:19:39 mehringe Exp $
  7.  */
  9. #include <stdlib.h>
  10. #include <math.h>
  11. #include <float.h>
  13. #include "random.h"
  14. #include "view.h"
  15. #include "netview.h"
  16. #include "animation.h"
  17. #include "queue.h"
  18. #include "edge.h"
  19. #include "node.h"
  20. #include "agent.h"
  21. #include "sincos.h"
  22. #include "state.h"
  23. #include "packet.h"
  24. #include "anetmodel.h"
  26. class AutoNetworkModelClass : public TclClass {
  27. public:
  28. AutoNetworkModelClass() : TclClass("NetworkModel/Auto") {}
  29. TclObject* create(int argc, const char*const* argv) {
  30. if (argc < 5) 
  31. return 0;
  32. return (new AutoNetModel(argv[4]));
  33. }
  34. } autonetworkmodel_class;
  36. int AutoNetModel::AUTO_ITERATIONS_ = 1;
  37. int AutoNetModel::INCR_ITERATIONS_ = 200;
  38. int AutoNetModel::RANDOM_SEED_ = 1;
  39. int AutoNetModel::recalc_ = 1;
  40. double AutoNetModel::INIT_TEMP_ = 0.30; // follow Elan's 
  41. double AutoNetModel::MINX_ = 0.0; 
  42. double AutoNetModel::MAXX_ = 1.0;
  43. double AutoNetModel::MINY_ = 0.0;
  44. double AutoNetModel::MAXY_ = 1.0;
  46. AutoNetModel::AutoNetModel(const char *animator) : NetModel(animator)
  47. {
  48. iterations_ = AUTO_ITERATIONS_;
  49. bind("KCa_", &kca_);
  50. bind("KCr_", &kcr_);
  51. bind("Recalc_", &recalc_);
  52. bind("INCR_ITERATIONS_", &INCR_ITERATIONS_);
  53. bind("AUTO_ITERATIONS_", &AUTO_ITERATIONS_);
  54. bind("RANDOM_SEED_", &RANDOM_SEED_);
  55. }
  57. AutoNetModel::~AutoNetModel()
  58. {
  59. }
  61. int AutoNetModel::command(int argc, const char *const *argv)
  62. {
  63. if (argc == 2) {
  64. if (strcmp(argv[1], "layout") == 0) {
  65. /*
  66.  * <net> layout
  67.  * compute layout using Elan's nem
  68.  */
  69. layout();
  70. return (TCL_OK);
  71. }
  72. if (strcmp(argv[1], "relayout") == 0) {
  73. relayout();
  74. return (TCL_OK);
  75. }
  76. if (strcmp(argv[1], "reset") == 0) {
  77. reset_layout();
  78. return (TCL_OK);
  79. }
  80. } 
  81. return (NetModel::command(argc, argv));
  82. }
  84. void AutoNetModel::reset_layout() 
  85. {
  86. Node *n;
  87. Edge *e;
  89. initEmbedding();
  90. for (n = nodes_; n != 0; n = n->next_)
  91. for (e = n->links(); e != 0; e = e->next_)
  92. e->unmark();
  93. scale_estimate();
  94. placeEverything();
  95. for (View *p = views_; p != 0; p = p->next_)
  96. if ((p->width() > 0) && (p->height() > 0)) {
  97. p->redrawModel();
  98. p->draw();
  99. }
  100. }
  102. void AutoNetModel::initEmbedding() 
  103. {
  104. Node *n;
  105. double maxx, maxy;
  107. Random::seed_heuristically();
  109. maxx = MINX_ + (MAXX_-MINX_) * 0.4;
  110. maxy = MINY_ + (MAXY_-MINY_) * 0.4;
  112. // randomize nodes' position within square [(0,0), (1,1)]
  113. for (nNodes_ = 0, n = nodes_; n != 0; n = n->next_, nNodes_++) {
  114. n->place(Random::uniform(MINX_, maxx),
  115.  Random::uniform(MINY_, maxy));
  116. }
  117. //optk_ = kc_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes);
  118. optka_ = kca_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
  119. optkr_ = kcr_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
  120. temp_ = INIT_TEMP_;
  121. }
  123. void AutoNetModel::placeEverything()
  124. {
  125. Node *n; 
  126. // Should re-initialize nymin_ and nymax_
  127. nymin_ = FLT_MAX;
  128. nymax_ = -FLT_MAX;
  129. for (n = nodes_; n != 0; n = n->next_) {
  130. for (Edge *e = n->links(); e != 0; e = e->next_)
  131. placeEdge(e, n);
  132. placeAllAgents(n);
  133. if (nymin_ > n->y())
  134. nymin_ = n->y();
  135. if (nymax_ < n->y())
  136. nymax_ = n->y();
  137. }
  138. // Place all routes
  139. for (n = nodes_; n != 0; n = n->next_) {
  140. n->clear_routes();
  141. n->place_all_routes();
  142. }
  143. }
  145. // do more passes
  146. void AutoNetModel::relayout()
  147. {
  148. Node *n;
  149. Edge *e;
  150. temp_ = INIT_TEMP_;
  151. for (n = nodes_; n != 0; n = n->next_)
  152. for (e = n->links(); e != 0; e = e->next_)
  153. e->unmark();
  155. //weigh_subtrees();
  156. //bifucate_graph();
  158. // in case that the two constants changed
  159. optka_ = kca_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
  160. optkr_ = kcr_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
  162. for (int i = 0; i < 100; i++) {
  163.   //alternate doses of vigorous shaking and letting it settle a little
  164.           //seem to work best.
  165.         if ((i==0)||(i==60)) temp_ = INIT_TEMP_;
  166.         if ((i==50)||(i==70)) temp_ = INIT_TEMP_/4.0;
  168.         if ((i<50)||((i>=60)&&(i<70)))
  169. {
  170.   embed_phase1();
  171. }
  172. else
  173. {
  174.   embed_phase2();
  175. }
  176. for (n = nodes_; n != 0; n = n->next_)
  177. for (e = n->links(); e != 0; e = e->next_)
  178. e->unmark();
  179. scale_estimate();
  180. placeEverything();
  181. for (View *p = views_; p != 0; p = p->next_)
  182. if ((p->width() > 0) && (p->height() > 0)) {
  183. // XXX assume this means tk has been 
  184. // initialized
  185. p->redrawModel();
  186. p->draw();
  187. }
  188. }
  190. }
  192. // do several passes of embedding
  193. void AutoNetModel::layout()
  194. {
  195. initEmbedding();
  196. for (int i = 0; i < iterations_; i++) {
  197. embed_phase2();
  198. }
  200. scale_estimate(); // find node size after layout
  201. placeEverything();
  202. }
  204. void AutoNetModel::cool()
  205. {
  206. if (temp_ > 0.001)
  207. temp_ *= 0.95;
  208. else 
  209. temp_ = 0.001;
  210. }
  212. void AutoNetModel::placeAllAgents(Node *src) const
  213. {
  214. // clear all marks and clear all angles
  215. for (Agent *a = src->agents(); a != NULL; a = a->next()) {
  216. a->mark(0), a->angle(NO_ANGLE);
  217. placeAgent(a, src);
  218. }
  219. }
  221. // we need to use edge length, instead of delay, to estimate scale
  222. void AutoNetModel::scale_estimate()
  223. {
  224. /* Determine the maximum link delay. */
  225. double emax = 0., emean = 0., dist;
  226. Node *n;
  227. int edges=0;
  228. for (n = nodes_; n != 0; n = n->next_) {
  229. for (Edge* e = n->links(); e != 0; e = e->next_) {
  230.         edges++;
  231. dist = n->distance(*(e->neighbor()));
  232. emean+=dist;
  233. if (dist > emax)
  234. emax = dist;
  235. }
  236. }
  237. emean/=edges;
  239. /*store this because we need it for monitors*/
  240. node_size_ = node_sizefac_ * emean;
  241. /*
  242.  * Check for missing node or edge sizes. If any are found,
  243.  * compute a reasonable default based on the maximum edge
  244.  * dimension.
  245.  */
  246. for (n = nodes_; n != 0; n = n->next_) {
  247. n->size(node_size_);
  248. for (Edge* e = n->links(); e != 0; e = e->next_)
  249. e->size(.03 * emean);
  250. }
  251. }
  253. // Fruchterman, T.M.J and Reingold, E.M.,
  254. // Graph Drawing by Force-directed Placement,
  255. // Software-Practice and Experience, vol. 21(11), 1129-1164 (Nov. 91)
  256. //
  257. // Do one pass of embedding
  258. void AutoNetModel::embed_phase1()
  259. {
  260. Node *v, *u;
  261. Edge* e;
  262. double dx, dy, mag, f, minn, rx, ry;
  263. /*
  264.  * Randomly jitter everything to try and break out of local minima
  265.          */
  266. for (v = nodes_; v != 0; v = v->next_) {
  267.   v->displace(0., 0.);
  268.   rx=0.1*(MAXX_-MINX_)*
  269.     ((INIT_TEMP_-temp_)/INIT_TEMP_)*
  270.     ((Random::random()&0xffff)/32768.0 - 1.0);
  271.   ry=0.1*(MAXX_-MINX_)*
  272.     ((INIT_TEMP_-temp_)/INIT_TEMP_)*
  273.     ((Random::random()&0xffff)/32768.0 - 1.0);
  274.   v->displace(rx,ry);
  275. }
  276. /*
  277.  * Calculate repulsive forces between all vertices.
  278.  */
  279. for (v = nodes_; v != 0; v = v->next_) {
  280. for (u = nodes_; u != 0; u = u->next_) {
  281. if (u == v) 
  282. continue;
  283. dx = v->x() - u->x();
  284. dy = v->y() - u->y();
  285. if (dx == 0 && dy == 0)
  286. dx = dy = 0.001;
  287. mag = sqrt(dx * dx + dy * dy);
  288. f = REP(mag, optkr_);
  289. v->displace(v->dx() + ((dx / mag) * f),
  290.     v->dy() + ((dy / mag) * f));
  291. }
  292. }
  293. /* 
  294.  * Limit the maximum displacement to the temperature temp;
  295.  * and then prevent from being displaced outside frame.
  296.  */
  297. if (recalc_==1) {
  298.   for (v = nodes_; v != 0; v = v->next_) {
  299.     mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
  300.     double posx = v->x(), posy = v->y();
  301.     if (mag != 0) {
  302.       minn = min(mag, temp_);
  303.       posx += v->dx() / mag * minn;
  304.       posy += v->dy() / mag * minn;
  305.     }
  306.     
  307.     v->place(posx, posy);
  308.     v->displace(0.,0.);
  309.   }
  310. }
  311. /*
  312.  * Calculate attractive forces between neighbors.
  313.  */
  314. for (v = nodes_; v != 0; v = v->next_) {
  315. for (e = v->links(); e != 0; e = e->next_) {
  316. u = e->neighbor();
  317. dx = v->x() - u->x();
  318. dy = v->y() - u->y();
  319. mag = sqrt(dx * dx + dy * dy);
  320. // XXX we consider single direction edge as 
  321. // of single direction attraction. So we only
  322. // attract one node toward the other. If later 
  323. // we have the other edge, the other node will be 
  324. // attracted too.
  325. if (mag >= 0) {
  326. f = ATT(mag, optka_);
  327. v->displace(v->dx() - dx / mag * f,
  328.     v->dy() - dy / mag * f);
  329. }
  330. }
  331. }
  332. /* 
  333.  * Limit the maximum displacement to the temperature temp;
  334.  * and then prevent from being displaced outside frame.
  335.  */
  336. for (v = nodes_; v != 0; v = v->next_) {
  337. mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
  338. double posx = v->x(), posy = v->y();
  339. if (mag != 0) {
  340. minn = min(mag, temp_);
  341. posx += v->dx() / mag * minn;
  342. posy += v->dy() / mag * minn;
  343. }
  345. #if 0
  346. posx = min(MAXX_, max(MINX_, posx));
  347. posy = min(MAXY_, max(MINY_, posy));
  348. #endif
  350. v->place(posx, posy);
  351. #if 0
  352. printf("Position of node %s: (%f, %f)n", 
  353.        v->name(), posx, posy);
  354. #endif
  355. }
  357. /* Cool the temperature */
  358. if (temp_ > 0.001)
  359. temp_ *= 0.95;
  360. else 
  361. temp_ = 0.001;
  363. #if 0
  364. printf("------------------------------n");
  365. #endif
  366. }
  368. void AutoNetModel::embed_phase2()
  369. {
  370. Node *v, *u;
  371. Edge* e;
  372. double dx, dy, mag, f, minn;
  373. /*
  374.  * Calculate repulsive forces between all vertices.
  375.  */
  376. for (v = nodes_; v != 0; v = v->next_) {
  377. //XXX why not 0. as in paper?
  378.         v->displace(0.,0.);
  379. for (u = nodes_; u != 0; u = u->next_) {
  380. if (u == v) 
  381. continue;
  382. dx = v->x() - u->x();
  383. dy = v->y() - u->y();
  384. if (dx == 0 && dy == 0)
  385. dx = dy = 0.001;
  386. mag = sqrt(dx * dx + dy * dy);
  387. f = REP(mag, optkr_);
  388. if (f < 2*u->size()) {
  389.   if (f<temp_)
  390.   {
  391.     f=2*u->size()/(mag/* *temp_*/);
  392.   }
  393.   else 
  394.     f=2*u->size()/mag;
  395. }
  396. v->displace(v->dx() + ((dx / mag) * f),
  397.     v->dy() + ((dy / mag) * f));
  398. }
  399. }
  400. /* 
  401.  * Limit the maximum displacement to the temperature temp;
  402.  * and then prevent from being displaced outside frame.
  403.  */
  404. if (recalc_==1) {
  405.   for (v = nodes_; v != 0; v = v->next_) {
  406.     mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
  407.     double posx = v->x(), posy = v->y();
  408.     if (mag != 0) {
  409.       minn = min(mag, temp_);
  410.       posx += v->dx() / mag * minn;
  411.       posy += v->dy() / mag * minn;
  412.     }
  413.     
  414.     v->place(posx, posy);
  415.     v->displace(0.,0.);
  416.   }
  417. }
  418. /*
  419.  * Calculate attractive forces between neighbors.
  420.  */
  421. for (v = nodes_; v != 0; v = v->next_) {
  422.   //if(v->mass()<=0) continue;
  423. for (e = v->links(); e != 0; e = e->next_) {
  424. u = e->neighbor();
  425. //if(u->mass()<=0) continue;
  426. dx = v->x() - u->x();
  427. dy = v->y() - u->y();
  428. mag = sqrt(dx * dx + dy * dy);
  429. // XXX we consider single direction edge as 
  430. // of single direction attraction. So we only
  431. // attract one node toward the other. If later 
  432. // we have the other edge, the other node will be 
  433. // attracted too.
  434. if (mag >= ((INIT_TEMP_-temp_)/INIT_TEMP_)*(e->length()+(v->size()+u->size())*0.75)) {
  435. f = ATT2(mag, optka_);
  436. v->displace(v->dx() - dx / mag * f,
  437.     v->dy() - dy / mag * f);
  438. }
  439. }
  440. }
  441. /* 
  442.  * Limit the maximum displacement to the temperature temp;
  443.  * and then prevent from being displaced outside frame.
  444.  */
  445. for (v = nodes_; v != 0; v = v->next_) {
  446.   //if(v->mass()<=0) continue;
  447. mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
  448. double posx = v->x(), posy = v->y();
  449. if (mag != 0) {
  450. minn = min(mag, temp_);
  451. posx += v->dx() * minn / mag;
  452. posy += v->dy() * minn / mag;
  453. }
  455. #if 0
  456. posx = min(MAXX_, max(MINX_, posx));
  457. posy = min(MAXY_, max(MINY_, posy));
  458. #endif
  460. v->place(posx, posy);
  461. #if 0
  462. printf("Position of node %s: (%f, %f)n", 
  463.        v->name(), posx, posy);
  464. #endif
  465. }
  467. /* Cool the temperature */
  468.         if (temp_ > 0.001)
  469.                 temp_ *= 0.95;
  470.         else
  471.                 temp_ = 0.001;
  473. #if 0
  474. printf("------------------------------n");
  475. #endif
  476. }
  479. // packet handling stuff. use new packet
  480. void AutoNetModel::handle(const TraceEvent& e, double now, int direction)
  481. {
  482. switch (e.tt) {
  483. case 'a':
  484. {
  485. NetModel::handle(e, now, direction);
  486. // recalculate bounding box so that all agents will be within
  487. // view
  488. for (View *v = views_; v != 0; v = v->next_)
  489. v->redrawModel();
  490. break;
  491. }
  492. default:
  493. NetModel::handle(e, now, direction);
  494. break;
  495. }
  496. }
  498. void AutoNetModel::bifucate_graph()
  499. {
  500.     Node *n, *m;
  501.     for (n = nodes_; n != 0; n = n->next_) {
  502.       if (n->mass()<=0) continue;
  503.       int remaining=0;
  504.       for (m = nodes_; m != 0; m = m->next_) {
  505. if (m->mass()>0) remaining++;
  506. m->mark(0);
  507.       }
  508.       int depth=0;
  509.       int result=2;
  510.       while((result!=0)&&(result!=1))
  511.       {
  512. depth++;
  513. for (m = nodes_; m != 0; m = m->next_) {
  514.   if (m->mass()>0) {
  515.     m->mark(0);
  516.     m->color("black");
  517.   }
  518. }
  519. result=mark_to_depth(n, depth);
  520. printf("depth: %d result: %dn", depth, result);
  521.       }
  522.       if (result==1) {
  523. int ctr=0;
  524. for (m = nodes_; m != 0; m = m->next_) {
  525.   if (m->marked()==1) ctr++;
  526. }
  527. printf("remaining: %d ctr: %dn", remaining, ctr);
  528. if ((remaining-ctr>1)&&(ctr>1)&&(ctr<remaining/2))
  529. {
  530.   printf("success!n");
  531.   for (m = nodes_; m != 0; m = m->next_) {
  532.     if (m->marked()==1)
  533.     {
  534.       m->mass(-1);
  535.       m->color("blue");
  536.     }
  537.   }
  538. }
  539.       } else {
  540. printf("failed at depth %d!n", depth);
  541.       }
  542.     }
  543. }
  545. int AutoNetModel::mark_to_depth(Node *n, int depth)
  546. {
  547.   int sum=0;
  548.   if (depth==0) {
  549.     n->mark(2);
  550.     return 1;
  551.   }
  552.   if (n->marked()==2) sum--;
  553.   n->mark(1);
  556.   for(Edge *e = n->links(); e != 0; e = e->next_)
  557.   {
  558.     Node *dst=e->neighbor();
  559.     if ((dst->mass()>0)&&(dst->marked()==0))
  560.       sum+=mark_to_depth(dst, depth-1);
  561.   }
  562.   return sum;
  563. }
  565. void AutoNetModel::weigh_subtrees()
  566. {
  567.   Node *n, *dst, *newdst;
  568.   Edge* e;
  569.   int nodes=0;
  570.   for (n = nodes_; n != 0; n = n->next_) {
  571.     n->mass(1);
  572.   }
  573.   for (n = nodes_; n != 0; n = n->next_) {
  574.     int ctr=0;
  575.     for (e = n->links(); e != 0; e = e->next_)
  576.       ctr++;
  577.     if (ctr==1)
  578.     {
  579.       dst=n->links()->neighbor();
  580.       dst->mass(2);
  581.       n->mass(0);
  582.       n->color("green");
  583.       nodes++;
  584.     }
  585.     while(ctr==1) {
  586.       ctr=0;
  587.       for (e = dst->links(); e != 0; e = e->next_)
  588. if (e->neighbor()->mass()==1) ctr++;
  589.       if (ctr==1)
  590.       {
  591. for (e = dst->links(); e != 0; e = e->next_)
  592.   if (e->neighbor()->mass()==1) {
  593.     newdst=e->neighbor();
  594.     newdst->mass(1+dst->mass());
  595.     dst->mass(0);
  596.     dst->color("red");
  597.     nodes++;
  598.     dst=newdst;
  599.     break;
  600.   }
  601.       }
  602.     }
  603.   }
  604.   printf("massless nodes: %dn", nodes);
  605.   nodes=0;
  606.   for (n = nodes_; n != 0; n = n->next_) {
  607.     if (n->mass()==0) {
  608.       nodes++;
  609.       n->color("grey");
  610.     }
  611.   }
  612.   printf("massless nodes: %dn", nodes);
  613. }
  614.     
  616. void AutoNetModel::place_subtrees()
  617. {
  618.   Node *n, *dst;
  619.   Edge* e;
  620.   double angle;
  621.   int nodes=0, did_something=1;
  622.   double comx=0.0, comy=0.0, x, y;
  623.   for (n = nodes_; n != 0; n = n->next_) {
  624.     if (n->mass()!=0)
  625.     {
  626.       comx+=n->x();
  627.       comy+=n->y();
  628.       nodes++;
  629.     }
  630.   }
  631.   comx/=nodes;
  632.   comy/=nodes;
  633.   printf("com at %.2f,%.2fn", comx, comy);
  634.   while (did_something) {
  635.     did_something=0;
  636.     for (n = nodes_; n != 0; n = n->next_) {
  637.       if (n->mass()==0)
  638.       {
  639. for (e = n->links(); e != 0; e = e->next_)
  640.   if (e->neighbor()->mass()>0)
  641.   {
  642.     dst=e->neighbor();
  643.     n->mass(1);
  644.     n->color("green");
  645.     x=dst->x();
  646.     y=dst->y();
  647.     if (y-comy!=0)
  648.       angle=atan((x-comx)/(y-comy));
  649.     else
  650.       angle=0;
  651.     if (y-comy>0)
  652.       angle+=M_PI;
  653.     n->place(x-2*n->size()*sin(angle), 
  654.      y-2*n->size()*cos(angle));
  655.     did_something=1;
  656.     break;
  657.   }
  658.       }
  659.     }
  660.   }
  661. }
  664. //------------------------------------------------------------------
  665. //  The following is a big hack and I hope it works
  666. //
  667. //  - It is being done to speed up the layout of realtime dynamic nodes
  668. //    by only laying out that node and not the others
  669. //  - These procedures should be integrated into the main relayout 
  670. //    procedure when time permits 
  671. //------------------------------------------------------------------
  673. //------------------------------------------------------------------
  674. //
  675. //------------------------------------------------------------------
  676. void AutoNetModel::relayoutNode(Node *v) {
  677.   Node *n;
  678.   Edge *e;
  679.   temp_ = INIT_TEMP_;
  680.   for (n = nodes_; n != 0; n = n->next_)
  681.     for (e = n->links(); e != 0; e = e->next_)
  682.       e->unmark();
  684. // in case that the two constants changed
  685. optka_ = kca_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
  686. optkr_ = kcr_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
  688.   for (int i = 0; i < 100; i++) {
  689.     // alternate doses of vigorous shaking and letting it settle a little
  690.     // seem to work best.
  691.     if ((i==0)||(i==60))
  692.        temp_ = INIT_TEMP_;
  693.     if ((i==50)||(i==70))
  694.        temp_ = INIT_TEMP_/4.0;
  696.     if ((i < 50) || ((i >= 60) && (i < 70))) {
  697.       embed_phase1(v);
  698.     } else {
  699.   embed_phase2(v);
  700. }
  701. for (n = nodes_; n != 0; n = n->next_)
  702. for (e = n->links(); e != 0; e = e->next_)
  703. e->unmark();
  704. scale_estimate();
  705. placeEverything();
  706. }
  707. }
  709. //------------------------------------------------------------------
  710. //
  711. //------------------------------------------------------------------
  712. void AutoNetModel::embed_phase1(Node *v) {
  713. Node *u;
  714. Edge* e;
  715. double dx, dy, mag, f, minn, rx, ry;
  716. /*
  717.  * Randomly jitter everything to try and break out of local minima
  718.    */
  719. v->displace(0., 0.);
  720. rx = 0.1 * (MAXX_-MINX_) *
  721.       ((INIT_TEMP_-temp_)/INIT_TEMP_) *
  722.       ((Random::random()&0xffff)/32768.0 - 1.0);
  723.   ry = 0.1 * (MAXX_-MINX_) *
  724.        ((INIT_TEMP_-temp_)/INIT_TEMP_) *
  725.        ((Random::random()&0xffff)/32768.0 - 1.0);
  726.   v->displace(rx,ry);
  727. /*
  728.  * Calculate repulsive forces between all vertices.
  729.  */
  730. for (u = nodes_; u != 0; u = u->next_) {
  731.    if (u == v) 
  732.       continue;
  733.    dx = v->x() - u->x();
  734.    dy = v->y() - u->y();
  735.    if (dx == 0 && dy == 0)
  736.      dx = dy = 0.001;
  737.    mag = sqrt(dx * dx + dy * dy);
  738.    f = REP(mag, optkr_);
  739.      v->displace(v->dx() + ((dx / mag) * f),
  740.                  v->dy() + ((dy / mag) * f));
  741. }
  742. /* 
  743.  * Limit the maximum displacement to the temperature temp;
  744.  * and then prevent from being displaced outside frame.
  745.  */
  746. if (recalc_ == 1) {
  747.    mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
  748.    double posx = v->x(), posy = v->y();
  749.    if (mag != 0) {
  750.       minn = min(mag, temp_);
  751.       posx += v->dx() / mag * minn;
  752.       posy += v->dy() / mag * minn;
  753.    }
  754.     
  755.    v->place(posx, posy);
  756.    v->displace(0.,0.);
  757. }
  758. /*
  759.  * Calculate attractive forces between neighbors.
  760.  */
  761. for (e = v->links(); e != 0; e = e->next_) {
  762.    u = e->neighbor();
  763.    dx = v->x() - u->x();
  764.    dy = v->y() - u->y();
  765.    mag = sqrt(dx * dx + dy * dy);
  766.    // XXX we consider single direction edge as 
  767.    // of single direction attraction. So we only
  768.    // attract one node toward the other. If later 
  769.    // we have the other edge, the other node will be 
  770.    // attracted too.
  771.    if (mag >= 0) {
  772.       f = ATT(mag, optka_);
  773.       v->displace(v->dx() - dx / mag * f,
  774.   v->dy() - dy / mag * f);
  775.    }
  776. }
  777. /* 
  778.  * Limit the maximum displacement to the temperature temp;
  779.  * and then prevent from being displaced outside frame.
  780.  */
  781. mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
  782. double posx = v->x(), posy = v->y();
  783. if (mag != 0) {
  784.    minn = min(mag, temp_);
  785.    posx += v->dx() / mag * minn;
  786.    posy += v->dy() / mag * minn;
  787. }
  789. v->place(posx, posy);
  791. /* Cool the temperature */
  792. if (temp_ > 0.001)
  793. temp_ *= 0.95;
  794. else 
  795. temp_ = 0.001;
  796. }
  798. //------------------------------------------------------------------
  799. //
  800. //------------------------------------------------------------------
  801. void AutoNetModel::embed_phase2(Node *v) {
  802. Node *u;
  803. Edge* e;
  804. double dx, dy, mag, f, minn;
  805. /*
  806.  * Calculate repulsive forces between all vertices.
  807.  */
  808. //XXX why not 0. as in paper?
  809. v->displace(0.,0.);
  810. for (u = nodes_; u != 0; u = u->next_) {
  811.    if (u == v) 
  812.       continue;
  813.    dx = v->x() - u->x();
  814.    dy = v->y() - u->y();
  815.    if (dx == 0 && dy == 0)
  816.       dx = dy = 0.001;
  817.    mag = sqrt(dx * dx + dy * dy);
  818.    f = REP(mag, optkr_);
  819.    if (f < 2*u->size()) {
  820.       if (f<temp_) {
  821.       f=2*u->size()/(mag/* *temp_*/);
  822.     } else { 
  823.       f=2*u->size()/mag;
  824.         }
  825.    }
  826.    v->displace(v->dx() + ((dx / mag) * f),
  827.        v->dy() + ((dy / mag) * f));
  828. }
  829. /* 
  830.  * Limit the maximum displacement to the temperature temp;
  831.  * and then prevent from being displaced outside frame.
  832.  */
  833. if (recalc_==1) {
  834.    mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
  835.    double posx = v->x(), posy = v->y();
  836.    if (mag != 0) {
  837.       minn = min(mag, temp_);
  838.       posx += v->dx() / mag * minn;
  839.       posy += v->dy() / mag * minn;
  840.    }
  841.    
  842.    v->place(posx, posy);
  843.    v->displace(0.,0.);
  844. }
  845. /*
  846.  * Calculate attractive forces between neighbors.
  847.  */
  848. for (e = v->links(); e != 0; e = e->next_) {
  849.    u = e->neighbor();
  850.    //if(u->mass()<=0) continue;
  851.    dx = v->x() - u->x();
  852.    dy = v->y() - u->y();
  853.    mag = sqrt(dx * dx + dy * dy);
  854.    // XXX we consider single direction edge as 
  855.    // of single direction attraction. So we only
  856.    // attract one node toward the other. If later 
  857.    // we have the other edge, the other node will be 
  858.    // attracted too.
  859.    if (mag >= ((INIT_TEMP_-temp_)/INIT_TEMP_) * 
  860.                  (e->length()+(v->size()+u->size()) *
  861.                  0.75)) {
  862.       f = ATT2(mag, optka_);
  863.       v->displace(v->dx() - dx / mag * f,
  864.   v->dy() - dy / mag * f);
  865.    }
  866. }
  867. /* 
  868.  * Limit the maximum displacement to the temperature temp;
  869.  * and then prevent from being displaced outside frame.
  870.  */
  871. mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
  872. double posx = v->x(), posy = v->y();
  873. if (mag != 0) {
  874.    minn = min(mag, temp_);
  875.    posx += v->dx() * minn / mag;
  876.    posy += v->dy() * minn / mag;
  877. }
  879. v->place(posx, posy);
  881. /* Cool the temperature */
  882.         if (temp_ > 0.001)
  883.                 temp_ *= 0.95;
  884.         else
  885.                 temp_ = 0.001;
  887. }