CODEWITHSUNDEEP
javascriptalgorithmd3.jsgraphgraph-theory
drew moore
drew moore

Reputation: 32680

Projecting relative positions of graph nodes to absolute coordinates

I have a data structure like this: 

nodes = [
         {
          "id":0,
          "proximities":{
             "1": 12.34,
             "2": 56.78
           }, 
         {
          "id":1,
          "proximities":{
             "0": 12.34,
             "2": 90.12
           }, 
         {
          "id":2,
          "proximities":{
             "0": 56.78,
             "1": 90.12
           }, 
      ]

It's an array of nodes I want to place on the screen. Each node contains a set of "proximities", numeric distances to other nodes, and I want to use these distances to compute the absolute XY positions at which to display the nodes. That is, we want to algorithmically compute a layout in which the distance between each pair of nodes is as close as possible to the distance given in the data.

I've tagged this question to d3 because I'll be using d3 to draw the graphic, and am curious about any built-in functionality it has that might make this easier for me.

That said, the root of my question is more broad: Is there a name for what I'm trying to do here? I'm sure there are graph theoretic approaches to solving this problem, but I'm having trouble finding them because I'm not sure what this problem is called. What should I Google?

Upvotes: 2

Views: 208

Answers (1)

Cyril Cherian
Cyril Cherian

Reputation: 32327

Here is how I approached your problem set.

My Nodes and their proximities are like:

nodes = [{
  "id": 0,
  name: "cyril",
  "proximities": {
    "1": 12.34,
    "2": 56.78,
    "3": 40
  }
}, {
  "id": 1,
  name: "tia",
  "proximities": {
    "0": 12.34,
    "2": 90.12
  }
}, {
  "id": 2,
  name: "josh",
  "proximities": {
    "0": 56.78,
    "1": 90.12
  }
}, {
  "id": 3,
  name: "sim",
  "proximities": {
    "0": 40,
  }
}]

Change the data set to format acceptable by Force Layout D3.

function makeNodesLinks(nodes) {

  var graph = {};
  graph.nodes = [];
  graph.links = [];
  var keys = [];

  nodes.forEach(function(d) {
    //add node
    graph.nodes.push({
      name: d.name,
      id: d.id
    });
    for (var key in d.proximities) {
      if (keys.indexOf(d.id + "-" + key)<0)//this means if link is present don't add
      {
        keys.push(d.id + "-" + key);//done to make links unique
        keys.push(key + "-" + d.id);
        //add link and value stores its approx distance.
        graph.links.push({
          source: d.id,
          target: parseInt(key),
          value: d.proximities[key]
        });
      }
    }
  });
  return graph;
}

Finally in the force layout the distance between the links are decided by value key.

  force
    .nodes(graph.nodes)
    .links(graph.links)
    .linkDistance(function(d) {
      return d.value*3;//approx distance between 2 nodes.
    })
    .start();

Working code here.

Now in case you don't want to see the links, change the style in CSS: make opacity 0 so it's not visible.

.link {
  stroke: #999;
  stroke-opacity: 0;
}

Upvotes: 1

Related Questions