Я пытаюсь улучшить алгоритм силового ориентированного размещения (для ориентированного графа). Базовый алгоритм работает, т.е. выполняется условие isStable в следующем коде, и алгоритм завершается, но ребра и узлы могут перекрываться. Поэтому я хочу добавить фиктивную вершину в середине ребер (как на следующем рисунке), которая должна решить эту проблему, так как фиктивная вершина заставит ребро отталкивать другие ребра и узлы.
Я добавил метод addDummies, который для каждого ребра, которое не является петлей, добавляет узел. Я назвал добавленные узлы midNodes.
Затем на каждой итерации (метод итерации) я устанавливаю положение midNodes по центру ребра. Остальное - старый алгоритм.
Я получаю лучшую компоновку без наложения ребер, но конечное условие никогда не выполняется, и, кроме того, рисунок не так хорош, как средние узлы, образующие своего рода "пончик" вокруг центрального узла, как вы можете видеть на изображении ниже ( средние узлы внутри красного круга)
Я ищу подробное описание алгоритма, который использует фиктивные узлы по краям, или для любого предложения, чтобы заставить алгоритм завершаться и иметь лучшие рисунки (я хотел бы, чтобы средние узлы не отталкивали другие узлы к внешней области)
Должен ли я также добавить новые ребра из средних узлов к старым узлам?
Решением может быть изменение условия isStable, но это число обычно гарантирует, что график правильно выстроен, поэтому я бы не хотел его трогать.
Изменение: я использую следующий код таким образом
var layouter = new Graph.Layout.Spring();
while !(layouter.isStable()) {
layouter.iterate(1);
}
Ниже приводится выдержка из текущего кода
Graph.Layout.Spring = function() {
this.maxRepulsiveForceDistance = 10;
this.maxRepulsiveForceDistanceQ = this.maxRepulsiveForceDistance * this.maxRepulsiveForceDistance;
this.k = 2.5;
this.k2 = this.k * this.k;
this.c = 0.01;
this.maxVertexMovement = 0.2;
this.damping = 0.7;
};
Graph.Layout.Spring.prototype = {
resetForUpdate : function() {
this.addDummies();
this.currentIteration = 0;
this.resetVelocities();
},
reset : function() {
this.pastIterations = 0;
this.currentIteration = 0;
this.layoutPrepare();
this.resetForUpdate();
},
isStable: function() {
var nARR= this.graph.nodeArray;
var i = nARR.length -1;
do {
var vel = nARR[i].velocity;
var vx = vel.x;
var vy = vel.y;
var v = vx*vx+vy*vy;
if (v > 0.0002) {
return false;
}
} while (i--);
return true;
},
addDummies: function() {
for (e in this.graph.edges) {
var edge = this.graph.edges[e];
var s = edge.source;
var t = edge.target;
var id = s.id+"#"+t.id;
console.log("adding ", id);
if (!this.graph.nodes[id]) {
if (s.id != t.id) {
this.graph.addNode(id, "");
var node = this.graph.nodes[id];
node.dummy = true;
node.fx = 0;
node.fy = 0;
node.next1id = s.id;
node.next2id = t.id;
node.velocity = {
x: 0,
y: 0
};
}
}
}
},
layoutPrepare : function() {
for ( var i = 0; i < this.graph.nodeArray.length; ++i) {
var node = this.graph.nodeArray[i];
var x = -1+Math.random()*2;
var y = -1+Math.random()*2;
node.layoutPosX = x;
node.layoutPosY = y;
node.fx = 0;
node.fy = 0;
node.velocity = {
x: 0,
y: 0
};
}
},
resetVelocities: function() {
for ( var i = 0; i < this.graph.nodeArray.length; ++i) {
var node = this.graph.nodeArray[i];
node.velocity = {
x: 0,
y: 0
};
}
},
iterate: function(iterations) {
var SQRT = Math.sqrt;
var RAND = Math.random;
var maxRFQ = this.maxRepulsiveForceDistanceQ;
var l_k2 = this.k2;
var it = iterations-1,
i, j, node1, node2;
var L_GRAPH = this.graph;
var L_EDGES = L_GRAPH.edges;
var nodeArray = L_GRAPH.nodeArray;
var L_NLEN = nodeArray.length;
/*
* addition: update midnodes position
*/
for (e in L_GRAPH.edges) {
var edge = L_GRAPH.edges[e];
var s = edge.source;
var t = edge.target;
if (s != t) {
var id = s.id+"#"+t.id;
var midNode = L_GRAPH.nodes[id];
if (midNode) {
var dx = s.layoutPosX - t.layoutPosX;
var dy = s.layoutPosY - t.layoutPosY;
midNode.layoutPosX = s.layoutPosX - dx/2;
midNode.layoutPosY = s.layoutPosY - dy/2;
}
}
}
/*
* repulsive
*/
do {
for (i = 0; i < L_NLEN; ++i) {
node1 = nodeArray[i];
for (j = i+1; j < L_NLEN; ++j) {
node2 = nodeArray[j];
// per cappio
if (node1 === node2)
continue;
var dx = node2.layoutPosX - node1.layoutPosX;
var dy = node2.layoutPosY - node1.layoutPosY;
var d2 = dx * dx + dy * dy;
if (d2 < 0.001) {
dx = 0.1 * RAND() + 0.1;
dy = 0.1 * RAND() + 0.1;
d2 = dx * dx + dy * dy;
}
if (d2 < maxRFQ) {
var d = SQRT(d2);
var f = 2*(l_k2 / d2);
var xx = f * dx / d;
var yy = f * dy / d;
node2.fx += xx;
node2.fy += yy;
node1.fx -= xx;
node1.fy -= yy;
}
} // for j
} // for i
/*
* Attractive
*/
i = (L_EDGES.length)-1;
if (i >= 0) {
do {
var edge = L_EDGES[i];
var node1 = edge.source;
var node2 = edge.target;
// evita self-force, che cmq andrebbe a zero
if (node1 === node2)
continue;
var dx = node2.layoutPosX - node1.layoutPosX;
var dy = node2.layoutPosY - node1.layoutPosY;
var d2 = dx * dx + dy * dy;
if (d2 < 0.01) {
dx = 0.1 * RAND() + 0.1;
dy = 0.1 * RAND() + 0.1;
d2 = dx * dx + dy * dy;
}
d = SQRT(d2);
var f = (l_k2-d2)/l_k2;
var n2d = node2.edges.length;
if (n2d > 2) {
n2d = 2;
}
var n1d = node1.edges.length;
if (n1d > 2) {
n1d = 2;
}
var xcomp = f * dx/d;
var ycomp = f * dy/d;
node2.fx += xcomp / n2d;
node2.fy += ycomp / n2d;
node1.fx -= xcomp / n1d;
node1.fy -= ycomp / n1d;
} while (i--);
} // if i>=0
/*
* Move by the given force
*/
var max = this.maxVertexMovement;
var d = this.damping;
var c = this.c;
var i = L_NLEN-1;
do {
var node = nodeArray[i];
var xmove,
ymove;
var v = node.velocity;
v.x = v.x * d + node.fx * c;
v.y = v.y * d + node.fy * c;
xmove = v.x;
ymove = v.y;
if (xmove > max)
xmove = max;
else if (xmove < -max)
xmove = -max;
if (ymove > max)
ymove = max;
else if (ymove < -max)
ymove = -max;
if (node.isNailed !== undefined) {
v.x = 0;
v.y = 0;
} else {
v.x = xmove;
v.y = ymove;
node.layoutPosX += xmove;
node.layoutPosY += ymove;
}
node.fx = 0;
node.fy = 0;
} while (i--);
} while (it--);
},
