HybridOptimizer.cpp [plain text]
#include "dynadag/DynaDAG.h"
namespace DynaDAG {
#ifdef DOUBLE_MEDIANS
#define med_type double
#define cvt_med
#define med_eq(m1,m2) (fabs(m1-m2)<0.25)
#else
#define med_type int
#define cvt_med ROUND
#define med_eq(m1,m2) (m1==m2)
#endif
struct MedianOptimizer {
Config &config;
UpDown m_dir;
int m_strength;
MedianOptimizer(Config &config) : config(config),m_dir(DOWN),m_strength(0) {}
int improve(DDModel::Node *n) {
Rank *rank = config.ranking.GetRank(DDd(n).rank);
if(MValExists(n,m_dir)) {
med_type nm = cvt_med(MVal(n,m_dir));
int i;
DDModel::Node *l = 0;
for(i = DDd(n).order-1;i!=-1;--i) {
DDModel::Node *v = rank->order[i];
if(MValExists(v,m_dir)) {
med_type lm = cvt_med(MVal(v,m_dir));
if(nm<lm || (med_eq(nm,lm) && m_strength)) {
l = v;
if(m_strength>1)
continue;
}
break;
}
}
if(l)
return DDd(l).order;
DDModel::Node *r = 0;
for(i = DDd(n).order+1;i!=rank->order.size(); ++i) {
DDModel::Node *v = rank->order[i];
if(MValExists(v,m_dir)) {
med_type rm = cvt_med(MVal(v,m_dir));
if(nm>rm || (med_eq(nm,rm) && m_strength)) {
r = v;
if(m_strength>1)
continue;
}
break;
}
}
if(r)
return DDd(r).order+1;
}
return -1;
}
};
struct SiftingOptimizer {
Config &config;
SiftMatrix matrix;
int m_strength;
SiftingOptimizer(Config &config) : config(config),matrix(config),m_strength(0) {}
int improve(DDModel::Node *n) {
int r = DDd(n).rank;
Rank *rank = config.ranking.GetRank(r);
int numcross=0,min=0,what=-1;
int o;
numcross = min = 0;
for(o = DDd(n).order+1; o!=rank->order.size(); ++o) {
DDModel::Node *x = rank->order[o];
numcross += matrix.allCrossings(x,n)-matrix.allCrossings(n,x);
if(numcross<min || (m_strength==1 && numcross==0 && what==-1) || (m_strength==2 && numcross==min)) {
min = numcross;
what = o+1;
}
}
numcross = 0;
for(o = DDd(n).order-1; o>=0; --o) {
DDModel::Node *x = rank->order[o];
numcross += matrix.allCrossings(n,x)-matrix.allCrossings(x,n);
if(numcross<min || (m_strength==1 && numcross==0 && what==-1) || (m_strength==2 && numcross==min)) {
min = numcross;
what = o;
}
}
return what;
}
void move(DDModel::Node *n,int where) {
Rank *rank = config.ranking.GetRank(DDd(n).rank);
matrix.move(n,where==rank->order.size()?0:rank->order[where]);
}
};
template<class Iter,class Optimizer,class OptState>
void optim(Config &config,Iter begin,Iter end, Optimizer *opt, OptState *state) {
for(Iter ni = begin; ni!=end; ++ni) {
int where = opt->improve(*ni);
if(where!=-1) {
state->move(*ni,where);
int r = DDd(*ni).rank,o = DDd(*ni).order;
config.RemoveNode(*ni);
config.InstallAtOrder(*ni,r,where>o?where-1:where);
}
}
}
struct RankLess {
bool operator()(DDModel::Node *u,DDModel::Node *v) {
if(DDd(u).rank == DDd(v).rank)
return DDd(u).order < DDd(v).order;
return DDd(u).rank < DDd(v).rank;
}
};
#define TIRE 5
void HybridOptimizer::Reorder(Layout &nodes,Layout &edges) {
NodeV optimOrder;
getCrossoptModelNodes(nodes,edges,optimOrder);
if(optimOrder.empty())
return;
sort(optimOrder.begin(),optimOrder.end(),RankLess());
loops.Field(r_crossopt,"model nodes for crossopt",optimOrder.size());
loops.Field(r_crossopt,"total model nodes",optimOrder.front()->g->nodes().size());
MedianOptimizer median(config);
SiftingOptimizer sifting(config);
Config::Ranks backup = config.ranking;
sifting.matrix.m_light = true;
sifting.matrix.recompute();
int best = sifting.matrix.total();
loops.Field(r_crossopt,"crossings before crossopt",best);
int passes = 24,pass=0,score;
while(pass<passes && best) {
int tired = 0;
while(pass<passes && tired<TIRE) {
median.m_strength = pass%4<2;
sifting.m_strength = !median.m_strength;
if(pass%2) {
median.m_dir = UP;
optim(config,optimOrder.begin(),optimOrder.end(),&median,&sifting);
int s2 = sifting.matrix.total();
do {
score = s2;
optim(config,optimOrder.begin(),optimOrder.end(),&sifting,&sifting);
}
while((s2 = sifting.matrix.total())<score);
}
else {
median.m_dir = DOWN;
optim(config,optimOrder.rbegin(),optimOrder.rend(),&median,&sifting);
int s2 = sifting.matrix.total();
do {
score = s2;
optim(config,optimOrder.rbegin(),optimOrder.rend(),&sifting,&sifting);
}
while((s2 = sifting.matrix.total())<score);
}
score = sifting.matrix.total();
if(reportEnabled(r_crossopt)) {
char buf[10];
sprintf(buf,"crossings pass %d",pass);
loops.Field(r_crossopt,buf,score);
}
if(score<best) {
backup = config.ranking;
best = score;
tired = 0;
}
else
tired++;
pass++;
}
if(score>best || tired==TIRE) {
config.Restore(backup);
sifting.matrix.recompute();
}
}
if(score>=best)
config.Restore(backup);
loops.Field(r_crossopt,"model edge crossings",best);
sifting.matrix.m_light = false;
sifting.matrix.recompute();
score = sifting.matrix.total();
loops.Field(r_crossopt,"weighted crossings before heavy pass",score);
if(score<NODECROSS_PENALTY) {
loops.Field(r_crossopt,"weighted crossings after heavy pass",-1);
return;
}
pass = 0;
passes = 4;
sifting.m_strength = 1;
bool improved;
do {
improved = false;
backup = config.ranking;
optim(config,optimOrder.begin(),optimOrder.end(),&sifting,&sifting);
int down = sifting.matrix.total();
Config::Ranks backup2 = config.ranking;
config.Restore(backup);
sifting.matrix.recompute();
optim(config,optimOrder.rbegin(),optimOrder.rend(),&sifting,&sifting);
int up = sifting.matrix.total();
if(down<score && down<up) {
config.Restore(backup2);
sifting.matrix.recompute();
score = down;
improved = true;
}
else if(up<score) {
score = up;
improved = true;
}
}
while(improved);
loops.Field(r_crossopt,"weighted crossings after heavy pass",score);
assert(score<NODECROSS_PENALTY*NODECROSS_PENALTY);
}
double HybridOptimizer::Reopt(DDModel::Node *n,UpDown dir) {
return DDd(n).cur.x;
}
}