Logo Search packages:      
Sourcecode: nam version File versions  Download package

anetmodel.cc

/*
 * Network model with automatic layout
 *
 * Layout code from nem by Elan Amir
 *
 * $Header: /cvsroot/nsnam/nam-1/anetmodel.cc,v 1.25 2000/11/12 23:19:39 mehringe Exp $
 */

#include <stdlib.h>
#include <math.h>
#include <float.h>

#include "random.h"
#include "view.h"
#include "netview.h"
#include "animation.h"
#include "queue.h"
#include "edge.h"
#include "node.h"
#include "agent.h"
#include "sincos.h"
#include "state.h"
#include "packet.h"
#include "anetmodel.h"

class AutoNetworkModelClass : public TclClass {
public:
      AutoNetworkModelClass() : TclClass("NetworkModel/Auto") {}
      TclObject* create(int argc, const char*const* argv) {
            if (argc < 5) 
                  return 0;
            return (new AutoNetModel(argv[4]));
      }
} autonetworkmodel_class;

int AutoNetModel::AUTO_ITERATIONS_ = 1;
int AutoNetModel::INCR_ITERATIONS_ = 200;
int AutoNetModel::RANDOM_SEED_ = 1;
int AutoNetModel::recalc_ = 1;
double AutoNetModel::INIT_TEMP_ = 0.30; // follow Elan's 
double AutoNetModel::MINX_ = 0.0; 
double AutoNetModel::MAXX_ = 1.0;
double AutoNetModel::MINY_ = 0.0;
double AutoNetModel::MAXY_ = 1.0;

AutoNetModel::AutoNetModel(const char *animator) : NetModel(animator)
{
      iterations_ = AUTO_ITERATIONS_;
      bind("KCa_", &kca_);
      bind("KCr_", &kcr_);
      bind("Recalc_", &recalc_);
      bind("INCR_ITERATIONS_", &INCR_ITERATIONS_);
      bind("AUTO_ITERATIONS_", &AUTO_ITERATIONS_);
      bind("RANDOM_SEED_", &RANDOM_SEED_);
}

AutoNetModel::~AutoNetModel()
{
}

int AutoNetModel::command(int argc, const char *const *argv)
{
      if (argc == 2) {
            if (strcmp(argv[1], "layout") == 0) {
                  /*
                   * <net> layout
                   * compute layout using Elan's nem
                   */
                  layout();
                  return (TCL_OK);
            }
            if (strcmp(argv[1], "relayout") == 0) {
                  relayout();
                  return (TCL_OK);
            }
            if (strcmp(argv[1], "reset") == 0) {
                  reset_layout();
                  return (TCL_OK);
            }
      } 
      return (NetModel::command(argc, argv));
}

void AutoNetModel::reset_layout() 
{
      Node *n;
      Edge *e;

      initEmbedding();
      for (n = nodes_; n != 0; n = n->next_)
            for (e = n->links(); e != 0; e = e->next_)
                  e->unmark();
      scale_estimate();
      placeEverything();
      for (View *p = views_; p != 0; p = p->next_)
            if ((p->width() > 0) && (p->height() > 0)) {
                  p->redrawModel();
                  p->draw();
            }
}

void AutoNetModel::initEmbedding() 
{
      Node *n;
      double maxx, maxy;

      Random::seed_heuristically();

      maxx = MINX_ + (MAXX_-MINX_) * 0.4;
      maxy = MINY_ + (MAXY_-MINY_) * 0.4; 

      // randomize nodes' position within square [(0,0), (1,1)]
      for (nNodes_ = 0, n = nodes_; n != 0; n = n->next_, nNodes_++) {
            n->place(Random::uniform(MINX_, maxx),
                   Random::uniform(MINY_, maxy));
      }
      //optk_ = kc_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes);
      optka_ = kca_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
      optkr_ = kcr_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
      temp_ = INIT_TEMP_;
}

void AutoNetModel::placeEverything()
{
      Node *n; 
      // Should re-initialize nymin_ and nymax_
      nymin_ = FLT_MAX;
      nymax_ = -FLT_MAX;
      for (n = nodes_; n != 0; n = n->next_) {
            for (Edge *e = n->links(); e != 0; e = e->next_)
                  placeEdge(e, n);
            placeAllAgents(n);
            if (nymin_ > n->y())
                  nymin_ = n->y();
            if (nymax_ < n->y())
                  nymax_ = n->y();
      }
      // Place all routes
      for (n = nodes_; n != 0; n = n->next_) {
            n->clear_routes();
            n->place_all_routes();
      }
}

// do more passes
void AutoNetModel::relayout()
{
      Node *n;
      Edge *e;
      temp_ = INIT_TEMP_;
      for (n = nodes_; n != 0; n = n->next_)
            for (e = n->links(); e != 0; e = e->next_)
                  e->unmark();

      //weigh_subtrees();
      //bifucate_graph();

      // in case that the two constants changed
      optka_ = kca_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
      optkr_ = kcr_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);

      for (int i = 0; i < 100; i++) {
        //alternate doses of vigorous shaking and letting it settle a little
          //seem to work best.
              if ((i==0)||(i==60)) temp_ = INIT_TEMP_;
              if ((i==50)||(i==70)) temp_ = INIT_TEMP_/4.0;

              if ((i<50)||((i>=60)&&(i<70)))
            {
              embed_phase1();
            }
            else
            {
              embed_phase2();
            }
            for (n = nodes_; n != 0; n = n->next_)
                  for (e = n->links(); e != 0; e = e->next_)
                        e->unmark();
            scale_estimate();
            placeEverything();
            for (View *p = views_; p != 0; p = p->next_)
                  if ((p->width() > 0) && (p->height() > 0)) {
                        // XXX assume this means tk has been 
                        // initialized
                        p->redrawModel();
                        p->draw();
                  }
      }

}

// do several passes of embedding
void AutoNetModel::layout()
{
      initEmbedding();
      for (int i = 0; i < iterations_; i++) {
            embed_phase2();
      }

      scale_estimate(); // find node size after layout
      placeEverything();
}

void AutoNetModel::cool()
{
      if (temp_ > 0.001)
            temp_ *= 0.95;
      else 
            temp_ = 0.001;
}

void AutoNetModel::placeAllAgents(Node *src) const
{
      // clear all marks and clear all angles
      for (Agent *a = src->agents(); a != NULL; a = a->next()) {
            a->mark(0), a->angle(NO_ANGLE);
            placeAgent(a, src);
      }
}

// we need to use edge length, instead of delay, to estimate scale
void AutoNetModel::scale_estimate()
{
      /* Determine the maximum link delay. */
      double emax = 0., emean = 0., dist;
      Node *n;
      int edges=0;
      for (n = nodes_; n != 0; n = n->next_) {
            for (Edge* e = n->links(); e != 0; e = e->next_) {
                    edges++;
                  dist = n->distance(*(e->neighbor()));
                  emean+=dist;
                  if (dist > emax)
                        emax = dist;
            }
      }
      emean/=edges;
      
      /*store this because we need it for monitors*/
      node_size_ = node_sizefac_ * emean;
      /*
       * Check for missing node or edge sizes. If any are found,
       * compute a reasonable default based on the maximum edge
       * dimension.
       */
      for (n = nodes_; n != 0; n = n->next_) {
            n->size(node_size_);
            for (Edge* e = n->links(); e != 0; e = e->next_)
                  e->size(.03 * emean);
      }
}

// Fruchterman, T.M.J and Reingold, E.M.,
// Graph Drawing by Force-directed Placement,
// Software-Practice and Experience, vol. 21(11), 1129-1164 (Nov. 91)
//
// Do one pass of embedding
void AutoNetModel::embed_phase1()
{
      Node *v, *u;      
      Edge* e;
      double dx, dy, mag, f, minn, rx, ry;
      /*
       * Randomly jitter everything to try and break out of local minima
         */
      for (v = nodes_; v != 0; v = v->next_) {
        v->displace(0., 0.);
        rx=0.1*(MAXX_-MINX_)*
          ((INIT_TEMP_-temp_)/INIT_TEMP_)*
          ((Random::random()&0xffff)/32768.0 - 1.0);
        ry=0.1*(MAXX_-MINX_)*
          ((INIT_TEMP_-temp_)/INIT_TEMP_)*
          ((Random::random()&0xffff)/32768.0 - 1.0);
        v->displace(rx,ry);
      }
      /*
       * Calculate repulsive forces between all vertices.
       */
      for (v = nodes_; v != 0; v = v->next_) {
            for (u = nodes_; u != 0; u = u->next_) {
                  if (u == v) 
                        continue;
                  dx = v->x() - u->x();
                  dy = v->y() - u->y();
                  if (dx == 0 && dy == 0)
                        dx = dy = 0.001;
                  mag = sqrt(dx * dx + dy * dy);
                  f = REP(mag, optkr_);
                  v->displace(v->dx() + ((dx / mag) * f),
                            v->dy() + ((dy / mag) * f));
            }
      }
      /* 
       * Limit the maximum displacement to the temperature temp;
       * and then prevent from being displaced outside frame.
       */
      if (recalc_==1) {
        for (v = nodes_; v != 0; v = v->next_) {
          mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
          double posx = v->x(), posy = v->y();
          if (mag != 0) {
            minn = min(mag, temp_);
            posx += v->dx() / mag * minn;
            posy += v->dy() / mag * minn;
          }
          
          v->place(posx, posy);
          v->displace(0.,0.);
        }
      }
      /*
       * Calculate attractive forces between neighbors.
       */
      for (v = nodes_; v != 0; v = v->next_) {
            for (e = v->links(); e != 0; e = e->next_) {
                  u = e->neighbor();
                  dx = v->x() - u->x();
                  dy = v->y() - u->y();
                  mag = sqrt(dx * dx + dy * dy);
                  // XXX we consider single direction edge as 
                  // of single direction attraction. So we only
                  // attract one node toward the other. If later 
                  // we have the other edge, the other node will be 
                  // attracted too.
                  if (mag >= 0) {
                        f = ATT(mag, optka_);
                        v->displace(v->dx() - dx / mag * f,
                                  v->dy() - dy / mag * f);
                  }
            }
      }
      /* 
       * Limit the maximum displacement to the temperature temp;
       * and then prevent from being displaced outside frame.
       */
      for (v = nodes_; v != 0; v = v->next_) {
            mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
            double posx = v->x(), posy = v->y();
            if (mag != 0) {
                  minn = min(mag, temp_);
                  posx += v->dx() / mag * minn;
                  posy += v->dy() / mag * minn;
            }

#if 0
            posx = min(MAXX_, max(MINX_, posx));
            posy = min(MAXY_, max(MINY_, posy));
#endif

            v->place(posx, posy);
#if 0
            printf("Position of node %s: (%f, %f)\n", 
                   v->name(), posx, posy);
#endif
      }

      /* Cool the temperature */
      if (temp_ > 0.001)
            temp_ *= 0.95;
      else 
            temp_ = 0.001;

#if 0
      printf("------------------------------\n");
#endif
}

void AutoNetModel::embed_phase2()
{
      Node *v, *u;      
      Edge* e;
      double dx, dy, mag, f, minn;
      /*
       * Calculate repulsive forces between all vertices.
       */
      for (v = nodes_; v != 0; v = v->next_) {
            //XXX why not 0. as in paper?
              v->displace(0.,0.);
            for (u = nodes_; u != 0; u = u->next_) {
                  if (u == v) 
                        continue;
                  dx = v->x() - u->x();
                  dy = v->y() - u->y();
                  if (dx == 0 && dy == 0)
                        dx = dy = 0.001;
                  mag = sqrt(dx * dx + dy * dy);
                  f = REP(mag, optkr_);
                  if (f < 2*u->size()) {
                    if (f<temp_)
                    {
                      f=2*u->size()/(mag/* *temp_*/);
                    }
                    else 
                      f=2*u->size()/mag;
                  }
                  v->displace(v->dx() + ((dx / mag) * f),
                            v->dy() + ((dy / mag) * f));
            }
      }
      /* 
       * Limit the maximum displacement to the temperature temp;
       * and then prevent from being displaced outside frame.
       */
      if (recalc_==1) {
        for (v = nodes_; v != 0; v = v->next_) {
          mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
          double posx = v->x(), posy = v->y();
          if (mag != 0) {
            minn = min(mag, temp_);
            posx += v->dx() / mag * minn;
            posy += v->dy() / mag * minn;
          }
          
          v->place(posx, posy);
          v->displace(0.,0.);
        }
      }
      /*
       * Calculate attractive forces between neighbors.
       */
      for (v = nodes_; v != 0; v = v->next_) {
        //if(v->mass()<=0) continue;
            for (e = v->links(); e != 0; e = e->next_) {
                  u = e->neighbor();
                  //if(u->mass()<=0) continue;
                  dx = v->x() - u->x();
                  dy = v->y() - u->y();
                  mag = sqrt(dx * dx + dy * dy);
                  // XXX we consider single direction edge as 
                  // of single direction attraction. So we only
                  // attract one node toward the other. If later 
                  // we have the other edge, the other node will be 
                  // attracted too.
                  if (mag >= ((INIT_TEMP_-temp_)/INIT_TEMP_)*(e->length()+(v->size()+u->size())*0.75)) {
                        f = ATT2(mag, optka_);
                        v->displace(v->dx() - dx / mag * f,
                                  v->dy() - dy / mag * f);
                  }
            }
      }
      /* 
       * Limit the maximum displacement to the temperature temp;
       * and then prevent from being displaced outside frame.
       */
      for (v = nodes_; v != 0; v = v->next_) {
        //if(v->mass()<=0) continue;
            mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
            double posx = v->x(), posy = v->y();
            if (mag != 0) {
                  minn = min(mag, temp_);
                  posx += v->dx() * minn / mag;
                  posy += v->dy() * minn / mag;
            }

#if 0
            posx = min(MAXX_, max(MINX_, posx));
            posy = min(MAXY_, max(MINY_, posy));
#endif

            v->place(posx, posy);
#if 0
            printf("Position of node %s: (%f, %f)\n", 
                   v->name(), posx, posy);
#endif
      }

      /* Cool the temperature */
        if (temp_ > 0.001)
                temp_ *= 0.95;
        else
                temp_ = 0.001;

#if 0
      printf("------------------------------\n");
#endif
}


// packet handling stuff. use new packet
void AutoNetModel::handle(const TraceEvent& e, double now, int direction)
{
      switch (e.tt) {
      case 'a':
      {
            NetModel::handle(e, now, direction);
            // recalculate bounding box so that all agents will be within
            // view
            for (View *v = views_; v != 0; v = v->next_)
                  v->redrawModel();
            break;
      }
      default:
            NetModel::handle(e, now, direction);
            break;
      }
}

void AutoNetModel::bifucate_graph()
{
    Node *n, *m;
    for (n = nodes_; n != 0; n = n->next_) {
      if (n->mass()<=0) continue;
      int remaining=0;
      for (m = nodes_; m != 0; m = m->next_) {
      if (m->mass()>0) remaining++;
      m->mark(0);
      }
      int depth=0;
      int result=2;
      while((result!=0)&&(result!=1))
      {
      depth++;
      for (m = nodes_; m != 0; m = m->next_) {
        if (m->mass()>0) {
          m->mark(0);
          m->color("black");
        }
      }
      result=mark_to_depth(n, depth);
      printf("depth: %d result: %d\n", depth, result);
      }
      if (result==1) {
      int ctr=0;
      for (m = nodes_; m != 0; m = m->next_) {
        if (m->marked()==1) ctr++;
      }
      printf("remaining: %d ctr: %d\n", remaining, ctr);
      if ((remaining-ctr>1)&&(ctr>1)&&(ctr<remaining/2))
      {
        printf("success!\n");
        for (m = nodes_; m != 0; m = m->next_) {
          if (m->marked()==1)
          {
            m->mass(-1);
            m->color("blue");
          }
        }
      }
      } else {
      printf("failed at depth %d!\n", depth);
      }
    }
}

int AutoNetModel::mark_to_depth(Node *n, int depth)
{
  int sum=0;
  if (depth==0) {
    n->mark(2);
    return 1;
  }
  if (n->marked()==2) sum--;
  n->mark(1);


  for(Edge *e = n->links(); e != 0; e = e->next_)
  {
    Node *dst=e->neighbor();
    if ((dst->mass()>0)&&(dst->marked()==0))
      sum+=mark_to_depth(dst, depth-1);
  }
  return sum;
}

void AutoNetModel::weigh_subtrees()
{
  Node *n, *dst, *newdst;
  Edge* e;
  int nodes=0;
  for (n = nodes_; n != 0; n = n->next_) {
    n->mass(1);
  }
  for (n = nodes_; n != 0; n = n->next_) {
    int ctr=0;
    for (e = n->links(); e != 0; e = e->next_)
      ctr++;
    if (ctr==1)
    {
      dst=n->links()->neighbor();
      dst->mass(2);
      n->mass(0);
      n->color("green");
      nodes++;
    }
    while(ctr==1) {
      ctr=0;
      for (e = dst->links(); e != 0; e = e->next_)
      if (e->neighbor()->mass()==1) ctr++;
      if (ctr==1)
      {
      for (e = dst->links(); e != 0; e = e->next_)
        if (e->neighbor()->mass()==1) {
          newdst=e->neighbor();
          newdst->mass(1+dst->mass());
          dst->mass(0);
          dst->color("red");
          nodes++;
          dst=newdst;
          break;
        }
      }
    }
  }
  printf("massless nodes: %d\n", nodes);
  nodes=0;
  for (n = nodes_; n != 0; n = n->next_) {
    if (n->mass()==0) {
      nodes++;
      n->color("grey");
    }
  }
  printf("massless nodes: %d\n", nodes);
}
    

void AutoNetModel::place_subtrees()
{
  Node *n, *dst;
  Edge* e;
  double angle;
  int nodes=0, did_something=1;
  double comx=0.0, comy=0.0, x, y;
  for (n = nodes_; n != 0; n = n->next_) {
    if (n->mass()!=0)
    {
      comx+=n->x();
      comy+=n->y();
      nodes++;
    }
  }
  comx/=nodes;
  comy/=nodes;
  printf("com at %.2f,%.2f\n", comx, comy);
  while (did_something) {
    did_something=0;
    for (n = nodes_; n != 0; n = n->next_) {
      if (n->mass()==0)
      {
      for (e = n->links(); e != 0; e = e->next_)
        if (e->neighbor()->mass()>0)
        {
          dst=e->neighbor();
          n->mass(1);
          n->color("green");
          x=dst->x();
          y=dst->y();
          if (y-comy!=0)
            angle=atan((x-comx)/(y-comy));
          else
            angle=0;
          if (y-comy>0)
            angle+=M_PI;
          n->place(x-2*n->size()*sin(angle), 
                 y-2*n->size()*cos(angle));
          did_something=1;
          break;
        }
      }
    }
  }
}


//------------------------------------------------------------------
//  The following is a big hack and I hope it works
//
//  - It is being done to speed up the layout of realtime dynamic nodes
//    by only laying out that node and not the others
//  - These procedures should be integrated into the main relayout 
//    procedure when time permits 
//------------------------------------------------------------------

//------------------------------------------------------------------
//
//------------------------------------------------------------------
void AutoNetModel::relayoutNode(Node *v) {
  Node *n;
  Edge *e;
  temp_ = INIT_TEMP_;
  for (n = nodes_; n != 0; n = n->next_)
    for (e = n->links(); e != 0; e = e->next_)
      e->unmark();

      // in case that the two constants changed
      optka_ = kca_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);
      optkr_ = kcr_ * sqrt((MAXX_-MINX_)*(MAXY_-MINY_) / (double)nNodes_);

  for (int i = 0; i < 100; i++) {
    // alternate doses of vigorous shaking and letting it settle a little
    // seem to work best.
    if ((i==0)||(i==60))
       temp_ = INIT_TEMP_;
    if ((i==50)||(i==70))
       temp_ = INIT_TEMP_/4.0;

    if ((i < 50) || ((i >= 60) && (i < 70))) {
      embed_phase1(v);
    } else {
              embed_phase2(v);
            }
            for (n = nodes_; n != 0; n = n->next_)
                  for (e = n->links(); e != 0; e = e->next_)
                        e->unmark();
            scale_estimate();
            placeEverything();
      }
}

//------------------------------------------------------------------
//
//------------------------------------------------------------------
void AutoNetModel::embed_phase1(Node *v) {
      Node *u;    
      Edge* e;
      double dx, dy, mag, f, minn, rx, ry;
      /*
       * Randomly jitter everything to try and break out of local minima
   */
      v->displace(0., 0.);
      rx = 0.1 * (MAXX_-MINX_) *
      ((INIT_TEMP_-temp_)/INIT_TEMP_) *
      ((Random::random()&0xffff)/32768.0 - 1.0);
  ry = 0.1 * (MAXX_-MINX_) *
       ((INIT_TEMP_-temp_)/INIT_TEMP_) *
       ((Random::random()&0xffff)/32768.0 - 1.0);
  v->displace(rx,ry);
      /*
       * Calculate repulsive forces between all vertices.
       */
      for (u = nodes_; u != 0; u = u->next_) {
         if (u == v) 
            continue;
         dx = v->x() - u->x();
         dy = v->y() - u->y();
         if (dx == 0 && dy == 0)
           dx = dy = 0.001;
         mag = sqrt(dx * dx + dy * dy);
         f = REP(mag, optkr_);
     v->displace(v->dx() + ((dx / mag) * f),
                 v->dy() + ((dy / mag) * f));
      }
      /* 
       * Limit the maximum displacement to the temperature temp;
       * and then prevent from being displaced outside frame.
       */
      if (recalc_ == 1) {
         mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
         double posx = v->x(), posy = v->y();
         if (mag != 0) {
            minn = min(mag, temp_);
            posx += v->dx() / mag * minn;
            posy += v->dy() / mag * minn;
         }
          
         v->place(posx, posy);
         v->displace(0.,0.);
      }
      /*
       * Calculate attractive forces between neighbors.
       */
      for (e = v->links(); e != 0; e = e->next_) {
         u = e->neighbor();
         dx = v->x() - u->x();
         dy = v->y() - u->y();
         mag = sqrt(dx * dx + dy * dy);
         // XXX we consider single direction edge as 
         // of single direction attraction. So we only
         // attract one node toward the other. If later 
         // we have the other edge, the other node will be 
         // attracted too.
         if (mag >= 0) {
            f = ATT(mag, optka_);
            v->displace(v->dx() - dx / mag * f,
                    v->dy() - dy / mag * f);
         }
      }
      /* 
       * Limit the maximum displacement to the temperature temp;
       * and then prevent from being displaced outside frame.
       */
      mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
      double posx = v->x(), posy = v->y();
      if (mag != 0) {
         minn = min(mag, temp_);
         posx += v->dx() / mag * minn;
         posy += v->dy() / mag * minn;
      }

      v->place(posx, posy);

      /* Cool the temperature */
      if (temp_ > 0.001)
            temp_ *= 0.95;
      else 
            temp_ = 0.001;
}

//------------------------------------------------------------------
//
//------------------------------------------------------------------
void AutoNetModel::embed_phase2(Node *v) {
      Node *u;    
      Edge* e;
      double dx, dy, mag, f, minn;
      /*
       * Calculate repulsive forces between all vertices.
       */
      //XXX why not 0. as in paper?
      v->displace(0.,0.);
      for (u = nodes_; u != 0; u = u->next_) {
         if (u == v) 
            continue;
         dx = v->x() - u->x();
         dy = v->y() - u->y();
         if (dx == 0 && dy == 0)
            dx = dy = 0.001;
         mag = sqrt(dx * dx + dy * dy);
         f = REP(mag, optkr_);
         if (f < 2*u->size()) {
            if (f<temp_) {
                  f=2*u->size()/(mag/* *temp_*/);
                } else { 
                  f=2*u->size()/mag;
        }
         }
         v->displace(v->dx() + ((dx / mag) * f),
                   v->dy() + ((dy / mag) * f));
      }
      /* 
       * Limit the maximum displacement to the temperature temp;
       * and then prevent from being displaced outside frame.
       */
      if (recalc_==1) {
         mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
         double posx = v->x(), posy = v->y();
         if (mag != 0) {
            minn = min(mag, temp_);
            posx += v->dx() / mag * minn;
            posy += v->dy() / mag * minn;
         }
         
         v->place(posx, posy);
         v->displace(0.,0.);
      }
      /*
       * Calculate attractive forces between neighbors.
       */
      for (e = v->links(); e != 0; e = e->next_) {
         u = e->neighbor();
         //if(u->mass()<=0) continue;
         dx = v->x() - u->x();
         dy = v->y() - u->y();
         mag = sqrt(dx * dx + dy * dy);
         // XXX we consider single direction edge as 
         // of single direction attraction. So we only
         // attract one node toward the other. If later 
         // we have the other edge, the other node will be 
         // attracted too.
         if (mag >= ((INIT_TEMP_-temp_)/INIT_TEMP_) * 
                 (e->length()+(v->size()+u->size()) *
                 0.75)) {
            f = ATT2(mag, optka_);
            v->displace(v->dx() - dx / mag * f,
                    v->dy() - dy / mag * f);
         }
      }
      /* 
       * Limit the maximum displacement to the temperature temp;
       * and then prevent from being displaced outside frame.
       */
      mag = sqrt(v->dx()*v->dx() + v->dy() * v->dy());
      double posx = v->x(), posy = v->y();
      if (mag != 0) {
         minn = min(mag, temp_);
         posx += v->dx() * minn / mag;
         posy += v->dy() * minn / mag;
      }

      v->place(posx, posy);

      /* Cool the temperature */
        if (temp_ > 0.001)
                temp_ *= 0.95;
        else
                temp_ = 0.001;

}


Generated by  Doxygen 1.6.0   Back to index