How to make a force directed layout with no node-edge overlapping

Question

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--); 
},

Answer 1

What you’re looking for is edge-edge repulsion. I’m looking for that too, I’m not seeing it in any npm packages.

Here’s a link to a paper that has some promising images of what it looks like on page 16 if you’re interested. https://www.researchgate.net/publication/4175452_A_new_force-directed_graph_drawing_method_based_on_edge-edge_repulsion

Answer 2

I would check out vis.js, I've implemented what you are trying to do with that library previously. They have a variety of physics engines that you can use.

If you want to implement it yourself and are stuck, I would recommend digging through the visjs source code for inspiration.

Here is a good example: https://visjs.github.io/vis-network/examples/network/other/configuration.html

Here are the "options" for that visualization.

physics: {
enabled: { boolean: bool },
barnesHut: {
  gravitationalConstant: { number },
  centralGravity: { number },
  springLength: { number },
  springConstant: { number },
  damping: { number },
  avoidOverlap: { number },
  __type__: { object }
},
forceAtlas2Based: {
  gravitationalConstant: { number },
  centralGravity: { number },
  springLength: { number },
  springConstant: { number },
  damping: { number },
  avoidOverlap: { number },
  __type__: { object }
},
repulsion: {
  centralGravity: { number },
  springLength: { number },
  springConstant: { number },
  nodeDistance: { number },
  damping: { number },
  __type__: { object }
},
hierarchicalRepulsion: {
  centralGravity: { number },
  springLength: { number },
  springConstant: { number },
  nodeDistance: { number },
  damping: { number },
  avoidOverlap: { number },
  __type__: { object }
},
maxVelocity: { number },
minVelocity: { number },    // px/s
solver: { string: ['barnesHut', 'repulsion', 'hierarchicalRepulsion', 'forceAtlas2Based'] },
stabilization: {
  enabled: { boolean: bool },
  iterations: { number },   // maximum number of iteration to stabilize
  updateInterval: { number },
  onlyDynamicEdges: { boolean: bool },
  fit: { boolean: bool },
  __type__: { object, boolean: bool }
},
timestep: { number },
adaptiveTimestep: { boolean: bool },
__type__: { object, boolean: bool }

}