This is more of a algorithmic question. I have a page which using javaScript displays items and items relationship to other item by drawing arrow connection from source to target (think jsPlumb). Each item can have 0 or more connections. The challenge i have is to place the divs/circles strategically with the container in the most optimum way .

• optimum : Least number of connections (arrows connecting two circles) overlaps

Visual Example: Below picture is an unoptimised version of the display, having placed the circles randomly within the container .

Notice in above picture the number of connection (arrows) overlap is unnecessarily high. Below picture is one optimized solution with circles placed in better position resulting in no overlap of connection in this small example:

The size of container in which items are placed is 1020x800. where large number of circles exist there will always be overlaps so the idea is to minimize the amount of connection overlap. I am hoping for example of how this could be done as i find reading algorithm articles slightly daunting :(.

This is more of a algorithmic question. I have a page which using javaScript displays items and items relationship to other item by drawing arrow connection from source to target (think jsPlumb). Each item can have 0 or more connections. The challenge i have is to place the divs/circles strategically with the container in the most optimum way .

• optimum : Least number of connections (arrows connecting two circles) overlaps

Visual Example: Below picture is an unoptimised version of the display, having placed the circles randomly within the container .

Notice in above picture the number of connection (arrows) overlap is unnecessarily high. Below picture is one optimized solution with circles placed in better position resulting in no overlap of connection in this small example:

The size of container in which items are placed is 1020x800. where large number of circles exist there will always be overlaps so the idea is to minimize the amount of connection overlap. I am hoping for example of how this could be done as i find reading algorithm articles slightly daunting :(.

• java
• javascript
• algorithm
• layout

• possible duplicate of Graph visualization code in JavaScript? – David Eisenstat Commented Aug 29, 2013 at 13:03
• @DavidEisenstat i disagree - your the mentioned thread is asking for ways in which you can graph nodes on a webpage, my question is very different in that its not restricted to webpages only and that it is a question from problem-solving/ algorithms rather than using x/y library to represent a graph. – ke3pup Commented Aug 29, 2013 at 22:13
• Do you have any links to the papers you have researched? – arynaq Commented Aug 29, 2013 at 22:26
• @arynaq online articles no , but this is the book i have from my university days in software engineering (amazon./Algorithm-Design-Jon-Kleinberg/dp/0321295358) but failed to find something that would help me. – ke3pup Commented Aug 30, 2013 at 0:15
• 1 In your unoptimized example, if I put B on the right, between C and D, I could draw the connection from B to E as a counterclockwise arc extending up and around C, and the connection from D to E as a counterclockwise arc extending down and around A. This would avoid overlaps. Would that be a possible acceptable solution to you (a solution that includes drawing arcs around nodes)? – גלעד ברקן Commented Sep 17, 2013 at 4:01

3 Answers 3

Approach 1

A pretty nice class of algorithms for laying out graphs are simulation-based algorithms. In those algorithms, you model your graph as if it was a physical object with physical properties.

In this case imagine the nodes of the graph are balls that repel each other, while the edges are springs or rubbers that keep the graph together. The repelling force is stronger the closer the nodes are to each other e.g. inverse square of their distance, and the tension force of each spring is proportional to its length. The repelling force will cause the nodes to get as far as possible from the other nodes and the graph will untie. Of course, you'll have to experiment with coefficients a little to get the best results (but I guarantee - it is a lot of fun).

The main pros of this approach are:

1. easy to code - nested loops calculating force between every node-node pair and updating node position
2. works for all kinds of graphs either planar or nonplanar
3. lots of fun to experiment
4. if you make it interactive, e.g. allow user to move nodes with a mouse - it attracts people and everyone wants to "play with the graph"

The downsides of this approach are:

1. it can get stuck in a local energy minimum (shaking or helping manually helps)
2. it is not extremely fast (but can make a nice animation)

A similar method can be used to layout/untie knots.

Sample code

<html>
<head>
</head>
<body>
  <canvas id="canvas" width="800" height="600" style="border:1px solid black"/>   
  <script>
    window.requestAnimFrame = (function(callback) {
       return window.requestAnimationFrame || window.webkitRequestAnimationFrame || 
              window.mozRequestAnimationFrame || window.oRequestAnimationFrame || window.msRequestAnimationFrame ||
              function(callback) {
                 window.setTimeout(callback, 1000 / 120);
              };
    })();

    var width = 800;
    var height = 600;

    function addEdge(nodeA, nodeB) {
      if (nodeA.edges.indexOf(nodeB) == -1) {
        nodeA.edges[nodeA.edges.length] = nodeB;
        nodeB.edges[nodeB.edges.length] = nodeA;
      }
    }

    function createGraph(count) {
      var graph = new Array();
      for (var i = 0; i < count; i++) {
        var node = new Object();
        node.x = Math.floor((Math.random() * width));  
        node.y = Math.floor((Math.random() * height));
        node.edges = new Array();        
        graph[i] = node;  
        if (i > 0) 
          addEdge(graph[i], graph[i - 1]);        
      }

      for (var i = 0; i < count / 2; i++) {
        var a = Math.floor((Math.random() * count));  
        var b = Math.floor((Math.random() * count));  
        addEdge(graph[a], graph[b]);
      }
      return graph;
    }

    function drawEdges(ctx, node) {
      for (var i = 0; i < node.edges.length; i++) {
        var otherNode = node.edges[i];
        ctx.beginPath();
        ctx.moveTo(node.x, node.y);
        ctx.lineTo(otherNode.x, otherNode.y);
        ctx.stroke();
      }
    }

    function drawNode(ctx, node) {
      ctx.beginPath();
      ctx.arc(node.x, node.y, 30, 0, 2 * Math.PI, false);
      ctx.fillStyle = 'green';
      ctx.fill();
      ctx.lineWidth = 5;
      ctx.strokeStyle = '#003300';
      ctx.stroke();
    }    

    function drawGraph(ctx, graph) {
      ctx.fillStyle = 'white';
      ctx.fillRect(0, 0, width, height);
      for (var i = 0; i < graph.length; i++)         
        drawEdges(ctx, graph[i]);      
      for (var i = 0; i < graph.length; i++)         
        drawNode(ctx, graph[i]);      
    }

    function distanceSqr(dx, dy) { 
      return dx * dx + dy * dy; 
    }

    function force(nodeA, nodeB, distanceFn) {
      var dx = nodeA.x - nodeB.x;
      var dy = nodeA.y - nodeB.y;
      var angle = Math.atan2(dy, dx);
      var ds = distanceFn(distanceSqr(dx, dy));
      return { x: Math.cos(angle) * ds, y: Math.sin(angle) * ds };
    }

    function repelForce(distanceSqr) {
      return 5000.0 / distanceSqr;
    }

    function attractForce(distanceSqr) {
      return -distanceSqr / 20000.0;
    }

    function gravityForce(distanceSqr) {
      return -Math.sqrt(distanceSqr) / 1000.0;
    }


    function calculateForces(graph) {
      var forces = new Array();  
      for (var i = 0; i < graph.length; i++) {
        forces[i] = { x: 0.0, y: 0.0 };

        // repelling between nodes:
        for (var j = 0; j < graph.length; j++) {
          if (i == j)
            continue;
          var f = force(graph[i], graph[j], repelForce);
          forces[i].x += f.x;
          forces[i].y += f.y;
        }

        // attraction between connected nodes:
        for (var j = 0; j < graph[i].edges.length; j++) {
          var f = force(graph[i], graph[i].edges[j], attractForce);
          forces[i].x += f.x;
          forces[i].y += f.y;          
        }          

        // gravity:
        var center = { x: 400, y: 300 };
        var f = force(graph[i], center, gravityForce);
        forces[i].x += f.x;
        forces[i].y += f.y;           
      }  
      return forces;
    }

    function updateNodePositions(graph) {
      var forces = calculateForces(graph);
      for (var i = 0; i < graph.length; i++) {
        graph[i].x += forces[i].x;      
        graph[i].y += forces[i].y;           
      }  
    }    

    function animate(graph) {    
      var ctx = document.getElementById("canvas").getContext("2d");
      for (var i = 0; i < 20; i++)
        updateNodePositions(graph);
      drawGraph(ctx, graph);
      requestAnimFrame(function() { animate(graph); });
    }

    animate(createGraph(8));
  </script>
</body>
</html>

You can see how this code works here. Refresh the page to get different graphs. Of course, sometimes it doesn't find the global minimum and there are more crossing edges than it is possible - so if the results don't satisfy you, you can add random shaking.

Approach 2

This problem is similar to routing problem in design of PCBs. If you're not satisfied with the simple and easy solution provided by Approach 1, you can improve the solution by using autorouting methods. E.g. you can put your nodes on a grid and then use A* algorithm to find the shortest paths connecting them.

1. Use Approach 1 to find a suboptimal initial solution (optional).
2. Remove all edges. Place the nodes on a grid (round up their coordinates). The grid must have enough resolution so that no two nodes overlap.
3. Sort the edges in ascending approximated length (use Euclidean or Manhattan metric).
4. For each edge use A* algorithm to find the shortest route to connect the nodes. As a cost function use not only the distance from the source node, but also add enough large penalty for stepping onto any grid points that are already taken by any edge routed previously.
5. Mark the grid points on the path found in the previous step as "taken", so all next edges will favour paths not stepping on / intersecting with this path.

The above algorithm is a greedy heuristic and unfortunately it doesn't guarantee the optimal solution, because the result depends on the order of routing the edges. You can further improve the solution by removng a random edge that crosses another edge and reroute it.

Step 1. is optional to make the graph layout more regular and make the average connection distance small, however it should not affect the number of intersections (if the grid has enough resolution).

It looks like simple closed polygon extraction to me. try this:

1. forget about direction of connections remove all redundant connections (bidirectional ones are duplicate)

2. find all closed loops

   start point is always container with more than 2 connections (or just with 1) so loop through unused neighboring containers until get back to the start point (set this path as used) or until reach endpoint (1 connection only, also set this path as used) or until reach crossroad (connections > 2, also set this path as used).

3. repeat until there are no unused line between containers left.

after this you have your graph deposed to non intersecting parts.

now join them back together so no connection is intersecting. Shared connections are inside and non shared connections are on the outside. Open loop (with endpoints) can be anywhere.

I hope this helps

I think the simulation-based algorithm would be the bbest choice, however, since your goal is to minimize overlapping arcs and not to optimize the distribution of nodes you should apply a repelling force between arcs (not between nodes) and use the nodes as springs.

Iteration:

1. For each arc in the graph pute its central point (averaging the starting point with the ending point)
2. for each couple of arcs apply a repulsion between their centres (both extremes of the arc move accordingly)
3. for each node in the graph pute its new position as the average of the connected arcs and update the related endpoint of the arc

You can also add a contraction phase with the nodes attracted to the middle of the graph (average of the coordinates of all the nodes).

Stop iterating when some stability threshold is reached.