[SOLVED] Logic to strategically place items in a container with minimum overlapping connections

Issue

This Content is from Stack Overflow. Question asked by paulc1111

I’m trying to draw a directed graph in python with networkx

It uses Fruchterman-Reingold force-directed algorithm to position nodes. However, I couldn’t get a result of graph with minimum overlapping edges. I want something like this in NetworkX or some other python API.

Can Fruchterman-Reingold algorithm produce a graph with minimum overlapping edges? If it can, which parameter should I adjust? If it can not, is there any API or alogrithm to use in python?

My code to visualize

pos = nx.spring_layout(G, k=100, iterations=500, seed=1)

enter image description here

Please help me out here..!

Let me know if you need more info.! (I will edit in this post.)

Thanks!



Solution

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).


This Question was asked in StackOverflow by ke3pup and Answered by Piotr Kołaczkowski It is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.

people found this article helpful. What about you?