/*
* 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;
}
syntax highlighted by Code2HTML, v. 0.9.1