CODEWITHSUNDEEP
javascriptd3.jshierarchy
Andrew
Andrew

Reputation: 1594

Find the length of the longest chain in a hierarchy

I have hierarchical data being used to create an svg in my application. I need to find the length of the longest chain in that datasource. I could go through the datasource level by level, recursively going deeper into it to read _children, calling a recursive function to count the levels, but I am sure there must be a better way. This is further complicates because the datasource can go both directions from the node it starts on with _children and _parents.

var findChildren = function (ds, level) {
    if (!ds._children || ds._children.length == 0) {
        return level;
    }

    var longest = level + 1;
    ds._children.forEach(function (item) {
        var result = findChildren(item, level + 1);
        if (result > longest) {
            longest = result;
        }
    });
    return longest;
}

This is the function I am currently using, with an identical one that checks ds._parents to go the other way, passing the result of one as the starting level of the other. I am just sure there must be a better way...

For example, the same data could be in three ways, depending where the user opened the tree from.

  1. {"number":1,"type":"Delivery","_parents":[{"number":1,"type":"Order","_parents":[{"number":1,"type":"Quote"}]}]}

  2. {"number":1,"type":"Order","_parents":[{"number":1,"type":"Quote"}], "_children":[{"number":1,"type":"Delivery"}]}

  3. {"number":1,"type":"Quote","_children":[{"number":1,"type":"Order","_children":[{"number":1,"type":"Delivery"}]}]}

Upvotes: 2

Views: 283

Answers (1)

Gerardo Furtado
Gerardo Furtado

Reputation: 102218

You said that you...

need to find the length of the longest chain in that datasource.

That is the length going to the root to the deepest leaf in the data structure. There are convenient D3 methods to quickly find the deepest leaf.

So, suppose we have a hierarchical data like this:

{
    "name": "Eve",
    "children": [{
        "name": "Cain"
    }, {
        "name": "Seth",
        "children": [{
            "name": "Enos"
        }, {
            "name": "Noam"
        }]
    }, {
        "name": "Abel"
    }, {
        "name": "Awan",
        "children": [{
            "name": "Enoch"
        }]
    }, {
        "name": "Azura"
    }]
}

When you pass it to d3.hierarchy()...

var hierarchy = d3.hierarchy(data);

... it automatically creates a property named depth in each node:

node.depth - zero for the root node, and increasing by one for each descendant generation.

So, we just need a simple function to get the biggest depth value. For instance:

var longest = d3.max(hierarchy.descendants().map(function(d) {
    return d.depth
}));

Here is a demo:

var data = {
  "name": "Eve",
  "children": [{
    "name": "Cain"
  }, {
    "name": "Seth",
    "children": [{
      "name": "Enos"
    }, {
      "name": "Noam"
    }]
  }, {
    "name": "Abel"
  }, {
    "name": "Awan",
    "children": [{
      "name": "Enoch"
    }]
  }, {
    "name": "Azura"
  }]
};

var hierarchy = d3.hierarchy(data);
var longest = d3.max(hierarchy.descendants().map(function(d) {
  return d.depth
}));
console.log("The longest chain has " + (longest + 1) + " levels.")
<script src="https://d3js.org/d3.v4.min.js"></script>

Upvotes: 2

Related Questions