Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

D3 force layout graph with nodes positioned in a grid

I have built a force-directed graph, however, in my case, I have also a grid with 80px*80px boxes. I'd like that each node in graph was positioned not only according to existing gravity and forces, but also in the middle of the closest grid box (without being fixed). Is it possible to do this in d3js?

like image 256
kolobok Avatar asked Sep 03 '14 11:09

kolobok


2 Answers

Moritz Stefaner came up with a way to do this

code: https://github.com/moritzstefaner/gridexperiments/

demo: http://moritzstefaner.github.io/gridexperiments/

EDIT:

as mentioned by @altocumulus, this didn't have a copy of the code. Normally I only copy the code from individual's sites as they're much more likely to disappear than something on github. Or I'll copy it when it is short (less than 50 loc?). Anyway, since the meat of the code can probably be pulled out, I've copied mortiz's index.html file below. the other referenced js files can be found elsewhere very easily. (just note that you should probably pull the versions of each library as of Dec 9, 2011)

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html lang="en">
<head>
    <meta charset="utf-8">
    <title>Forces and grids</title>
    <script type="text/javascript" src="d3.min.js"></script>
    <script type="text/javascript" src="d3.layout.min.js"></script>
    <script type="text/javascript" src="d3.geom.min.js"></script>
    <script type="text/javascript" src="underscore-min.js"></script>
    <script src="jquery-1.7.2.min.js" charset="utf-8"></script>
    <style type="text/css" media="screen">
        .menu { position:absolute; top :20px; right:20px; }
    </style>    
</head>
<body>
    <script type="text/javascript" charset="utf-8">
        var w = 700, h = 700;
        var vis = d3.select("body").append("svg:svg").attr("width", w).attr("height", h);
        var background = vis.append("g");
        var nodes = [];
        var links = [];
        var USE_GRID = true;
        var GRID_SIZE = 60;
        var GRID_TYPE = "HEXA";

        // set up event handlers
        $(document).ready(function(){
            $("#USE_GRID").click(
                function(){
                    USE_GRID = $(this).is(":checked");
                    $(this).blur();
                    force.start();
                }
            );

            //$("#CELL_SIZE").rangeinput();
            $("#CELL_SIZE").bind("change", 
                function(){
                    console.log($(this).attr("value"));
                    GRID_SIZE = $(this).attr("value");
                    grid.init();
                    force.start();
                }
            );

            $("[name=GRID_TYPE]").click( 
                function(){
                    GRID_TYPE = $(this).attr("value");
                    grid.init();
                    force.start();
                }
            );
        });
        for(var i = 0; i < 30; i++) {
            var node = {
                label : "node " + i
            };
            nodes.push(node);
        };
        for(var i = 0; i < nodes.length; i++) {
            for(var j = 0; j < i; j++) {
                if(Math.random() > .99-Math.sqrt(i)*.02)
                    links.push({
                        source : i,
                        target : j,
                        weight :1
                    });
            }
        };
        var force = d3.layout.force().size([w, h]).nodes(nodes).links(links).gravity(1).linkDistance(function(d){return (1-d.weight)*100}).charge(-3000).linkStrength(function(x) {
            return x.weight * 5
        });
        force.start();
        var link = vis.selectAll("line.link").data(links).enter().append("svg:line").attr("class", "link").style("stroke-width", 1.5).style("stroke", "#555").style("opacity", function(d){return d.weight*.7});
        var node = vis.selectAll("g.node").data(force.nodes()).enter().append("svg:g").attr("class", "node");
        node.append("svg:circle").attr("r", 6).style("fill", "#555").style("stroke", "#FFF").style("stroke-width", "4px");
        node.call(force.drag);
        var updateLink = function() {
            this.attr("x1", function(d) {
                return d.source.screenX;
            }).attr("y1", function(d) {
                return d.source.screenY;
            }).attr("x2", function(d) {
                return d.target.screenX;
            }).attr("y2", function(d) {
                return d.target.screenY;
            });
        }
        var updateNode = function() {
            this.attr("transform", function(d) {
                if(USE_GRID) {
                    var gridpoint = grid.occupyNearest(d);
                    if(gridpoint) {
                        d.screenX = d.screenX || gridpoint.x;                           
                        d.screenY = d.screenY || gridpoint.y;                                                       
                        d.screenX += (gridpoint.x - d.screenX) * .2;
                        d.screenY += (gridpoint.y - d.screenY) * .2;

                        d.x += (gridpoint.x - d.x) * .05;
                        d.y += (gridpoint.y - d.y) * .05;
                    }
                } else {
                    d.screenX = d.x;
                    d.screenY = d.y;
                }
                return "translate(" + d.screenX + "," + d.screenY + ")";
            });
        };
        var grid = function(width, height) {
            return {
                cells : [],
                init : function() {
                    this.cells = [];
                    for(var i = 0; i < width / GRID_SIZE; i++) {
                        for(var j = 0; j < height / GRID_SIZE; j++) {
                            // HACK: ^should be a better way to determine number of rows and cols
                            var cell;
                            switch (GRID_TYPE) {
                                case "PLAIN":
                                    cell = {
                                        x : i * GRID_SIZE,
                                        y : j * GRID_SIZE
                                    };
                                    break;
                                case "SHIFT_ODD_ROWS":
                                    cell = {
                                        x : i * GRID_SIZE,
                                        y : 1.5 * (j * GRID_SIZE + (i % 2) * GRID_SIZE * .5)
                                    };
                                    break;
                                case "HEXA":
                                    cell = {
                                        x : i * GRID_SIZE + (j % 2) * GRID_SIZE * .5,
                                        y : j * GRID_SIZE * .85
                                    };
                                    break;
                            }
                            this.cells.push(cell);
                        };
                    };
                },
                sqdist : function(a, b) {
                    return Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2);
                },
                occupyNearest : function(p) {
                    var minDist = 1000000;
                    var d;
                    var candidate = null;
                    for(var i = 0; i < this.cells.length; i++) {
                        if(!this.cells[i].occupied && ( d = this.sqdist(p, this.cells[i])) < minDist) {
                            minDist = d;
                            candidate = this.cells[i];
                        }
                    }
                    if(candidate)
                        candidate.occupied = true;
                    return candidate;
                }
            }
        }(w, h);
        force.on("tick", function() {
            vis.select("g.gridcanvas").remove();
            if(USE_GRID) {
                grid.init();
                var gridCanvas = vis.append("svg:g").attr("class", "gridcanvas");
                _.each(grid.cells, function(c) {
                    gridCanvas.append("svg:circle").attr("cx", c.x).attr("cy", c.y).attr("r", 2).style("fill", "#555").style("opacity", .3);
                });
            }
            node.call(updateNode);
            link.call(updateLink);
        });
    </script>
    <div class="menu">
        <div>
            <input type="checkbox" id="USE_GRID" checked>use grid</input>       
        </div>
        <div>
            <input type="range" min="30" step="10" max="150" id="CELL_SIZE" value="60"></input>
        </div>
        <div>
            <input type="radio" name="GRID_TYPE" value="PLAIN">plain</input>
            <input type="radio" name="GRID_TYPE" value="SHIFT_ODD_ROWS">Shift odd rows</input>
            <input type="radio" name="GRID_TYPE" value="HEXA" checked>Hexa</input>                              
        </div>
    </div>
</body>

like image 160
viggity Avatar answered Oct 10 '22 03:10

viggity


You have to apply your custom forces in

force.on("tick", function() {

  node.attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; });

  link.attr("x1", function(d) { return d.source.x; })
      .attr("y1", function(d) { return d.source.y; })
      .attr("x2", function(d) { return d.target.x; })
      .attr("y2", function(d) { return d.target.y; });

});

so there is no built-in way to do such a thing...

So in your case you have to find the close grid box centers and count the x and y values using the distance between the nodes and the box centers and some gravity equation.

In you case

node
    .attr("cx", function(d) {
        d.x += f(d).x;
        return d.x;
    })
    .attr("cy", function(d) {
        d.y += f(d).y;
        return d.y;
    });

where f(d) is the vector of your gravity force depends on the distance between the box centers and the actual node d. For example

var blackHole = function (d) {
    var gc = {
        x: 100,
        y: 100
    };
    var k = 0.1;

    var dx = gc.x - d.px;
    var dy = gc.y - d.py;

    return {
        x: k * dx,
        y: k * dy
    };
};

It is pretty hard to find out an f(d) which really works by multiple gravity centers, so I suggest you to read about such force algorithms. I tried out some funny examples, but none of them works the way you want. ;-)

Now at least:

var grid = function (d) {
    var fx = d.px % 100;
    if (fx < 0)
        fx += 100;
    if (fx > 50)
        fx -= 100;

    var fy = d.py % 100;
    if (fy < 0)
        fy += 100;
    if (fy > 50)
        fy -= 100;
    var k = -1;

    return {
        x: k * fx,
        y: k * fy
    };
};

This is a 100px dense grid with very simple forces... But I guess the result is not what you expected, nodes can overlap, because by force layout only nodes with common links repel each other, at least that is my experience (edit: that's because the negative charge)... I think is could be much easier to build a custom force layout using d3 quad...

like image 40
inf3rno Avatar answered Oct 10 '22 04:10

inf3rno