CODEWITHSUNDEEP
javascriptjsond3.jslayout
Mohit
Mohit

Reputation: 1063

D3 Graph Layout - Tree Structure With multiple Parent

Let me start off with stating that I am completely new to D3 and Javascript. And with little bit of experimenting it I was trying to develop a Tree Like structure with the catch being, node can have multiple parents.

Input:

Json with nodes and links info like,

 var graph = {
    "nodes": [  { "id" : 0},
                { "id" : 1},
                { "id" : 2},
                { "id" : 3},
                { "id" : 4},
                { "id" : 5}
            ],
    "links": [  { "target": 5, "source":  1 },
                { "target":  2, "source":  0 },
                { "target": 3, "source":  4 },
                { "target": 1, "source":  2},
                { "target":  1, "source":  0 },
                
            ]
    };

Note: This is just for reference as how I have the data, it may be thousands of nodes.

Output:

I want the output like a tree structure, somewhat like this, as in to say the nodes must be plotted in a depth/level like structure with root being on the top and same level nodes arranged in such a way to minimize the link overlap.

Edit: The output for the input provided above is this Assuming Zero is root.

Problems I am facing:

  1. As I am only given nodes and their source & target, not their coordinates, I have to parse through the whole list calculate the level, then divide the height based on that level and then plot the nodes. What is the most efficient way to handle this kind of problem? Should I go deep into the algorithmic solution?

Or

  1. Is there some graph plotting function in D3 which takes this JSON as input and does the the rest of the job?

Please not that the nodes can have multiple parent and my main focus here is plotting of these nodes in a proper/hierarchical order, so the main problem I am facing is calculating the X/Y coordinates for all the nodes given just the input as stated above.

Please help me understand this topic better and Thank you.

Upvotes: 2

Views: 7295

Answers (1)

Mark
Mark

Reputation: 108512

Been thinking about this off and on all day. With built-in d3 constructs, I think this is about as close as you are going to get. I've taken your data and converted it to a version 4 example:

<!DOCTYPE html>
<meta charset="utf-8">
<style>
  .links line {
    stroke: #aaa;
    stroke-width: 5px;
  }
  
  .nodes circle {
    pointer-events: all;
    stroke: none;
  }
</style>
<svg width="600" height="300"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>
  var svg = d3.select("svg"),
    width = +svg.attr("width"),
    height = +svg.attr("height");

  var simulation = d3.forceSimulation()
    .force("link", d3.forceLink().id(function(d) {
      return d.id;
    }))
    .force("charge", d3.forceManyBody())
    .force("center", d3.forceCenter(width / 2, height / 2))
    .force("y", d3.forceY())

  var graph = {
    "nodes": [{
      "id": 0
    }, {
      "id": 1
    }, {
      "id": 2
    }, {
      "id": 3
    }, {
      "id": 4
    }, {
      "id": 5
    }],
    "links": [{
        "target": 5,
        "source": 1
      }, {
        "target": 2,
        "source": 0
      }, {
        "target": 3,
        "source": 4
      }, {
        "target": 1,
        "source": 2
      }, {
        "target": 1,
        "source": 0
      },

    ]
  };

  var link = svg.append("g")
    .attr("class", "links")
    .selectAll("line")
    .data(graph.links)
    .enter().append("line");

  var node = svg.append("g")
    .attr("class", "nodes")
    .selectAll("circle")
    .data(graph.nodes)
    .enter().append("circle")
    .attr("r", 10);

  node.append("title")
    .text(function(d) {
      return d.id;
    });

  simulation
    .nodes(graph.nodes)
    .on("tick", ticked);

  simulation.force("link")
    .links(graph.links);

  function ticked() {

    var k = 6 * simulation.alpha();

    // Push sources up and targets down to form a weak tree.
    link
      .each(function(d) {
        d.source.y -= k, d.target.y += k;
      })
      .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;
      });

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

  }
</script>

If you don't want the movement and settle effect, you can pre-compute the layout to make it static.

I also experimented with converting your data to a hierarchical format for use with d3.tree but didn't have much luck replicating your image:

<!DOCTYPE html>
<meta charset="utf-8">
<style>
  .node circle {
    fill: #999;
  }
  
  .node text {
    font: 10px sans-serif;
  }
  
  .node--internal circle {
    fill: #555;
  }
  
  .node--internal text {
    text-shadow: 0 1px 0 #fff, 0 -1px 0 #fff, 1px 0 0 #fff, -1px 0 0 #fff;
  }
  
  .link {
    fill: none;
    stroke: #555;
    stroke-opacity: 0.4;
    stroke-width: 1.5px;
  }
</style>
<svg width="300" height="300"></svg>
<script src="//d3js.org/d3.v4.min.js"></script>
<script>
  var graph = {
    "nodes": [{
      "id": 0
    }, {
      "id": 1
    }, {
      "id": 2
    }, {
      "id": 3
    }, {
      "id": 4
    }, {
      "id": 5
    }],
    "links": [{
      "target": 5,
      "source": 1
    },{
      "target": 2,
      "source": 0
    }, {
      "target": 3,
      "source": 4
    }, {
      "target": 1,
      "source": 2
    }, {
      "target": 1,
      "source": 0
    }]
  };

  var root = {
    id: 0,
    data: graph.nodes[0],
    children: []
  }

  function recurChild(obj) {
    graph.links.forEach(function(d) {
      if (d.source === obj.id) {
        var c = {
          id: d.target,
          data: graph.nodes[d.target],
          children: []
        };
        obj.children.push(c);
        recurChild(c);
      }
    });
  }
  recurChild(root);

  root = d3.hierarchy(root);

  var svg = d3.select("svg"),
    width = +svg.attr("width"),
    height = +svg.attr("height"),
    g = svg.append("g").attr("transform", "translate(40,0)");

  var tree = d3.tree()
    .size([height, width - 160]);

  tree(root);
  
  console.log(root.descendants())

  var link = g.selectAll(".link")
    .data(root.descendants().slice(1))
    .enter().append("path")
    .attr("class", "link")
    .attr("d", function(d) {
      return "M" + d.y + "," + d.x + "C" + (d.y + d.parent.y) / 2 + "," + d.x + " " + (d.y + d.parent.y) / 2 + "," + d.parent.x + " " + d.parent.y + "," + d.parent.x;
    });

  var node = g.selectAll(".node")
    .data(root.descendants())
    .enter().append("g")
    .attr("class", function(d) {
      return "node" + (d.children ? " node--internal" : " node--leaf");
    })
    .attr("transform", function(d) {
      return "translate(" + d.y + "," + d.x + ")";
    })

  node.append("circle")
    .attr("r", 2.5);

  node.append("text")
    .attr("dy", 3)
    .attr("x", function(d) {
      return d.children ? -8 : 8;
    })
    .style("text-anchor", function(d) {
      return d.children ? "end" : "start";
    })
    .text(function(d) {
      return d.data.id;
    });
</script>

d3.hierarchy really implies just that, straight hierarchy with no multiple parent structure.

Upvotes: 4

Related Questions