How to make a force directed layout with no node-edge overlapping
I'm trying to make better a force directed layout algorithm (for a directed graph)
The base algorithm works, i.e. the isStable condition in the following code is met and the algorithm ends, but edges and nodes can overlap. So I want to add some dummy vertex in the middle of the edges (as in the following image) that should solve this problem, as the dummy vertex would make the edge repel other edges and nodes.
I added the addDummies method, which for each edge which is not a loop adds a node.
I called the added nodes the midNodes.
Then at each iteration (iterate method) I set the position of the midNodes to be at the middle of the edge.
The rest is the old algorithm.
I obtain a better layout with no edge overlapped, but the end condition is never met and, moreover, the drawing is not so good as the midNodes form a sort of "donut" around the central node as you can see from the image below (midNodes are inside the red circle)
I'm looking for a detailed description of an algorithm which uses dummy nodes on the edges or for any suggestion to make the algorithm terminate and have better drawings (I'd like the midNodes not to repel the other nodes towards the outer area)
Should I add also new edges from the midNodes to the old nodes?
A solution could be to change the isStable condition, but that number generally assures me the graph is correctly laid out, so I'd like not to touch it.
Edit: I use the following code in this way
var layouter = new Graph.Layout.Spring();
while !(layouter.isStable()) {
layouter.iterate(1);
}
The following is an excerpt of the current code
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--);
},
javascript algorithm graph force-layout graph-layout
add a comment |
I'm trying to make better a force directed layout algorithm (for a directed graph)
The base algorithm works, i.e. the isStable condition in the following code is met and the algorithm ends, but edges and nodes can overlap. So I want to add some dummy vertex in the middle of the edges (as in the following image) that should solve this problem, as the dummy vertex would make the edge repel other edges and nodes.
I added the addDummies method, which for each edge which is not a loop adds a node.
I called the added nodes the midNodes.
Then at each iteration (iterate method) I set the position of the midNodes to be at the middle of the edge.
The rest is the old algorithm.
I obtain a better layout with no edge overlapped, but the end condition is never met and, moreover, the drawing is not so good as the midNodes form a sort of "donut" around the central node as you can see from the image below (midNodes are inside the red circle)
I'm looking for a detailed description of an algorithm which uses dummy nodes on the edges or for any suggestion to make the algorithm terminate and have better drawings (I'd like the midNodes not to repel the other nodes towards the outer area)
Should I add also new edges from the midNodes to the old nodes?
A solution could be to change the isStable condition, but that number generally assures me the graph is correctly laid out, so I'd like not to touch it.
Edit: I use the following code in this way
var layouter = new Graph.Layout.Spring();
while !(layouter.isStable()) {
layouter.iterate(1);
}
The following is an excerpt of the current code
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--);
},
javascript algorithm graph force-layout graph-layout
1
Is there a reason that you don't want to use existing force-directed drawing solutions?
– meowgoesthedog
Nov 27 '18 at 14:37
I don't know whether existing force-directed drawing solutions support edge-node repulsion, however I'm building a visualization system and I'd like to learn how to do these things. I'm also interested in existing solutions if they support edge-node repulsion and they are open source
– cdarwin
Nov 27 '18 at 14:51
1
Instead of adding a mid-point node you can directly use the distance from a node to a nearby edge to compute a secondary repulsion force. However this can still lead to edges crossing each other.
– meowgoesthedog
Nov 27 '18 at 14:59
1
Thank you. It is just from yesterday that indeed I'm thinking about a solution like the one you propose. It is a bit more complex than my original one, however more powerfull. The problem of edge crossing I think is a much more difficult one, I'm only interested in node-edge repulsion
– cdarwin
Nov 27 '18 at 15:05
1
I actually think it would be simpler, because 1) you don't have to create those phantom midpoint nodes, and 2) they have to be treated as special cases anyway (e.g. they can intersect while the actual nodes cannot), but I guess that's subjective. I'll try to make a test implementation as soon as I'm free.
– meowgoesthedog
Nov 27 '18 at 15:10
add a comment |
I'm trying to make better a force directed layout algorithm (for a directed graph)
The base algorithm works, i.e. the isStable condition in the following code is met and the algorithm ends, but edges and nodes can overlap. So I want to add some dummy vertex in the middle of the edges (as in the following image) that should solve this problem, as the dummy vertex would make the edge repel other edges and nodes.
I added the addDummies method, which for each edge which is not a loop adds a node.
I called the added nodes the midNodes.
Then at each iteration (iterate method) I set the position of the midNodes to be at the middle of the edge.
The rest is the old algorithm.
I obtain a better layout with no edge overlapped, but the end condition is never met and, moreover, the drawing is not so good as the midNodes form a sort of "donut" around the central node as you can see from the image below (midNodes are inside the red circle)
I'm looking for a detailed description of an algorithm which uses dummy nodes on the edges or for any suggestion to make the algorithm terminate and have better drawings (I'd like the midNodes not to repel the other nodes towards the outer area)
Should I add also new edges from the midNodes to the old nodes?
A solution could be to change the isStable condition, but that number generally assures me the graph is correctly laid out, so I'd like not to touch it.
Edit: I use the following code in this way
var layouter = new Graph.Layout.Spring();
while !(layouter.isStable()) {
layouter.iterate(1);
}
The following is an excerpt of the current code
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--);
},
javascript algorithm graph force-layout graph-layout
I'm trying to make better a force directed layout algorithm (for a directed graph)
The base algorithm works, i.e. the isStable condition in the following code is met and the algorithm ends, but edges and nodes can overlap. So I want to add some dummy vertex in the middle of the edges (as in the following image) that should solve this problem, as the dummy vertex would make the edge repel other edges and nodes.
I added the addDummies method, which for each edge which is not a loop adds a node.
I called the added nodes the midNodes.
Then at each iteration (iterate method) I set the position of the midNodes to be at the middle of the edge.
The rest is the old algorithm.
I obtain a better layout with no edge overlapped, but the end condition is never met and, moreover, the drawing is not so good as the midNodes form a sort of "donut" around the central node as you can see from the image below (midNodes are inside the red circle)
I'm looking for a detailed description of an algorithm which uses dummy nodes on the edges or for any suggestion to make the algorithm terminate and have better drawings (I'd like the midNodes not to repel the other nodes towards the outer area)
Should I add also new edges from the midNodes to the old nodes?
A solution could be to change the isStable condition, but that number generally assures me the graph is correctly laid out, so I'd like not to touch it.
Edit: I use the following code in this way
var layouter = new Graph.Layout.Spring();
while !(layouter.isStable()) {
layouter.iterate(1);
}
The following is an excerpt of the current code
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--);
},
javascript algorithm graph force-layout graph-layout
javascript algorithm graph force-layout graph-layout
edited Nov 23 '18 at 21:35
cdarwin
asked Nov 21 '18 at 15:17
cdarwincdarwin
1,52772952
1,52772952
1
Is there a reason that you don't want to use existing force-directed drawing solutions?
– meowgoesthedog
Nov 27 '18 at 14:37
I don't know whether existing force-directed drawing solutions support edge-node repulsion, however I'm building a visualization system and I'd like to learn how to do these things. I'm also interested in existing solutions if they support edge-node repulsion and they are open source
– cdarwin
Nov 27 '18 at 14:51
1
Instead of adding a mid-point node you can directly use the distance from a node to a nearby edge to compute a secondary repulsion force. However this can still lead to edges crossing each other.
– meowgoesthedog
Nov 27 '18 at 14:59
1
Thank you. It is just from yesterday that indeed I'm thinking about a solution like the one you propose. It is a bit more complex than my original one, however more powerfull. The problem of edge crossing I think is a much more difficult one, I'm only interested in node-edge repulsion
– cdarwin
Nov 27 '18 at 15:05
1
I actually think it would be simpler, because 1) you don't have to create those phantom midpoint nodes, and 2) they have to be treated as special cases anyway (e.g. they can intersect while the actual nodes cannot), but I guess that's subjective. I'll try to make a test implementation as soon as I'm free.
– meowgoesthedog
Nov 27 '18 at 15:10
add a comment |
1
Is there a reason that you don't want to use existing force-directed drawing solutions?
– meowgoesthedog
Nov 27 '18 at 14:37
I don't know whether existing force-directed drawing solutions support edge-node repulsion, however I'm building a visualization system and I'd like to learn how to do these things. I'm also interested in existing solutions if they support edge-node repulsion and they are open source
– cdarwin
Nov 27 '18 at 14:51
1
Instead of adding a mid-point node you can directly use the distance from a node to a nearby edge to compute a secondary repulsion force. However this can still lead to edges crossing each other.
– meowgoesthedog
Nov 27 '18 at 14:59
1
Thank you. It is just from yesterday that indeed I'm thinking about a solution like the one you propose. It is a bit more complex than my original one, however more powerfull. The problem of edge crossing I think is a much more difficult one, I'm only interested in node-edge repulsion
– cdarwin
Nov 27 '18 at 15:05
1
I actually think it would be simpler, because 1) you don't have to create those phantom midpoint nodes, and 2) they have to be treated as special cases anyway (e.g. they can intersect while the actual nodes cannot), but I guess that's subjective. I'll try to make a test implementation as soon as I'm free.
– meowgoesthedog
Nov 27 '18 at 15:10
1
1
Is there a reason that you don't want to use existing force-directed drawing solutions?
– meowgoesthedog
Nov 27 '18 at 14:37
Is there a reason that you don't want to use existing force-directed drawing solutions?
– meowgoesthedog
Nov 27 '18 at 14:37
I don't know whether existing force-directed drawing solutions support edge-node repulsion, however I'm building a visualization system and I'd like to learn how to do these things. I'm also interested in existing solutions if they support edge-node repulsion and they are open source
– cdarwin
Nov 27 '18 at 14:51
I don't know whether existing force-directed drawing solutions support edge-node repulsion, however I'm building a visualization system and I'd like to learn how to do these things. I'm also interested in existing solutions if they support edge-node repulsion and they are open source
– cdarwin
Nov 27 '18 at 14:51
1
1
Instead of adding a mid-point node you can directly use the distance from a node to a nearby edge to compute a secondary repulsion force. However this can still lead to edges crossing each other.
– meowgoesthedog
Nov 27 '18 at 14:59
Instead of adding a mid-point node you can directly use the distance from a node to a nearby edge to compute a secondary repulsion force. However this can still lead to edges crossing each other.
– meowgoesthedog
Nov 27 '18 at 14:59
1
1
Thank you. It is just from yesterday that indeed I'm thinking about a solution like the one you propose. It is a bit more complex than my original one, however more powerfull. The problem of edge crossing I think is a much more difficult one, I'm only interested in node-edge repulsion
– cdarwin
Nov 27 '18 at 15:05
Thank you. It is just from yesterday that indeed I'm thinking about a solution like the one you propose. It is a bit more complex than my original one, however more powerfull. The problem of edge crossing I think is a much more difficult one, I'm only interested in node-edge repulsion
– cdarwin
Nov 27 '18 at 15:05
1
1
I actually think it would be simpler, because 1) you don't have to create those phantom midpoint nodes, and 2) they have to be treated as special cases anyway (e.g. they can intersect while the actual nodes cannot), but I guess that's subjective. I'll try to make a test implementation as soon as I'm free.
– meowgoesthedog
Nov 27 '18 at 15:10
I actually think it would be simpler, because 1) you don't have to create those phantom midpoint nodes, and 2) they have to be treated as special cases anyway (e.g. they can intersect while the actual nodes cannot), but I guess that's subjective. I'll try to make a test implementation as soon as I'm free.
– meowgoesthedog
Nov 27 '18 at 15:10
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53415160%2fhow-to-make-a-force-directed-layout-with-no-node-edge-overlapping%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53415160%2fhow-to-make-a-force-directed-layout-with-no-node-edge-overlapping%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Is there a reason that you don't want to use existing force-directed drawing solutions?
– meowgoesthedog
Nov 27 '18 at 14:37
I don't know whether existing force-directed drawing solutions support edge-node repulsion, however I'm building a visualization system and I'd like to learn how to do these things. I'm also interested in existing solutions if they support edge-node repulsion and they are open source
– cdarwin
Nov 27 '18 at 14:51
1
Instead of adding a mid-point node you can directly use the distance from a node to a nearby edge to compute a secondary repulsion force. However this can still lead to edges crossing each other.
– meowgoesthedog
Nov 27 '18 at 14:59
1
Thank you. It is just from yesterday that indeed I'm thinking about a solution like the one you propose. It is a bit more complex than my original one, however more powerfull. The problem of edge crossing I think is a much more difficult one, I'm only interested in node-edge repulsion
– cdarwin
Nov 27 '18 at 15:05
1
I actually think it would be simpler, because 1) you don't have to create those phantom midpoint nodes, and 2) they have to be treated as special cases anyway (e.g. they can intersect while the actual nodes cannot), but I guess that's subjective. I'll try to make a test implementation as soon as I'm free.
– meowgoesthedog
Nov 27 '18 at 15:10