javascript - D3 Graph Layout - Tree Structure With multiple Parent - Stack Overflow

admin管理员组

文章数量:1415491

Let me start off with stating that I am pletely 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 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

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

Let me start off with stating that I am pletely 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 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

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

• javascript
• json
• d3.js
• layout

Share Improve this question Follow edited Jun 20, 2020 at 9:12 CommunityBot 111 silver badge asked Oct 2, 2016 at 14:59 MohitMohit 1,06344 gold badges1919 silver badges4747 bronze badges 6

• I can't figure out your expected output. Assuming zero is the root node, would it look like this. 3 to 4 goes away as it fails the parent/child relationship... Is this your expected output? – Mark Commented Oct 2, 2016 at 15:58
• @Mark Actually the input is just for reference as how the input I have...it may contain thousands of nodes, the excepted output regardless is that which ever is the root node should appear on the top, then its childs and so on with minimum link overlap. Hope I was able to explain myself ;) – Mohit Commented Oct 2, 2016 at 16:05
• But is my diagram the expected output given your sample data? – Mark Commented Oct 2, 2016 at 16:09
• @Mark Not pletely, level 1 should contain 0 as root, then its lower level 2 should have 2 and 1, just as you have but the last level 3 should only have 5 connected with 1, there should not be another 1 on level 3...thanks for pointing it out I will update the question with a proper output for the given input. – Mohit Commented Oct 2, 2016 at 16:20
• I suggest drawing a picture. I'm even more confused after reading your last ment, then I was originally :) – Mark Commented Oct 2, 2016 at 16:26

 |  Show 1 more ment

1 Answer 1

Sorted by: Reset to default 4

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/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-pute 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/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.

本文标签： javascriptD3 Graph LayoutTree Structure With multiple ParentStack Overflow