Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Tree Structure from Adjacency List

I am trying to generate a hierarchical tree object from a flat array with parent IDs.

// `parent` represents an ID and not the nesting level.
var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

The final tree object should look as follows:

{ 
    id: 1, 
    name: "Business", 
    children: [
        { 
            id: 2, 
            name: "Management", 
            children: [
                { id: 3, name: "Leadership" },
                { id: 7, name: "Project Management" }
            ]
        }
        // [...]
    ]
}
// [...]

You can see my current work on this fiddle, but it only works on the first two levels.

I thought about collecting the orphans (objects from flat without a parent in tree yet) and then looping over them again to see if they now have a parent. But that could mean many loops over the tree object, especially with many categories over multiple levels.

I'm sure there is a more elegant solution.

like image 536
John B. Avatar asked Jan 24 '14 21:01

John B.


People also ask

Can a tree be represented in adjacency list?

Adjacency lists (or any list/array) is basically out of the picture for binary trees or anything with node. left and node. right properties, but still on the table for n-ary trees, for which the node. children property is much more akin to tree[node] or children[node] .

Which data structure is used in adjacency list?

This representation is called the adjacency List. This representation is based on Linked Lists. In this approach, each Node is holding a list of Nodes, which are Directly connected with that vertices. At the end of list, each node is connected with the null values to tell that it is the end node of that list.

How do you represent an adjacency list?

In Adjacency List, we use an array of a list to represent the graph. The list size is equal to the number of vertex(n). Adjlist[0] will have all the nodes which are connected to vertex 0. Adjlist[1] will have all the nodes which are connected to vertex 1 and so on.


2 Answers

Looks like you can do this in 2 passes no matter the tree depth:

var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

var nodes = [];
var toplevelNodes = [];
var lookupList = {};

for (var i = 0; i < flat.length; i++) {
    var n = {
        id: flat[i].id,
        name: flat[i].name,
        parent_id: ((flat[i].parent == 0) ? null : flat[i].parent),
        children: []
        };
    lookupList[n.id] = n;
    nodes.push(n);
    if (n.parent_id == null) {
        toplevelNodes.push(n);
    }
}

for (var i = 0; i < nodes.length; i++) {
  var n = nodes[i];
  if (!(n.parent_id == null)) {
      lookupList[n.parent_id].children = lookupList[n.parent_id].children.concat([n]);
  }
}

console.log(toplevelNodes);
like image 200
TreyE Avatar answered Oct 01 '22 01:10

TreyE


Update 2, (six years later)

I happened to stumble across this again and realized how much simpler this can be with a little ES6 destructuring and a straightforward recursion:

const makeForest = (id, xs) => 
  xs .filter (({parent}) => parent == id)
     .map (({id, parent, ...rest}) => ({id, ...rest, children: makeForest (id, xs)}))

var flat = [{id: 1, name: "Business", parent: 0}, {id: 2, name: "Management", parent: 1}, {id: 3, name: "Leadership", parent: 2}, {id: 4, name: "Finance", parent: 1}, {id: 5, name: "Fiction", parent: 0}, {id: 6, name: "Accounting", parent: 1}, {id: 7, name: "Project Management", parent: 2}];

console .log (
  makeForest (0, flat)
)
.as-console-wrapper {min-height: 100% !important; top: 0}

Note the name change. We're not making a tree, but an entire forest of trees, with each direct child of the root its own node. It would be relatively trivial to change this to generate a tree, if you had a structure to use for the root. Also note that this will let us find the tree rooted at any id. It doesn't have to be the overall root.

Performance

This does, as you worried about, have a worst-case performance of O(n^2). The actual run time is something like O(n * p) where p is the number of distinct parent nodes in the list. So we only approach the worst case when we have a tree nearly as deep as the length of the list. I would use something like this unless and until I could show that it was a hot spot in my code. My guess is that I would never find a need to replace it.

Lesson

Never count out recursion. This is significantly simpler than any of the other answers here, including my two versions below.


Update 1

I was not happy with extra complexity in my original solution. I'm adding another version that reduces that complexity. It manages to build the data in a single pass. It also gives one the chance to restructure the records in the trees differently from their original format if necessary. (By default, it only removes the parent node.)

Updated Version

Available on JSFiddle.

var makeTree = (function() {
    var defaultClone = function(record) {
        var newRecord = JSON.parse(JSON.stringify(record));
        delete newRecord.parent;
        return newRecord;
    };
    return function(flat, clone) {
        return flat.reduce(function(data, record) {
            var oldRecord = data.catalog[record.id];
            var newRecord = (clone || defaultClone)(record);
            if (oldRecord && oldRecord.children) {
                newRecord.children = oldRecord.children;
            }
            data.catalog[record.id] = newRecord;
            if (record.parent) {
                var parent = data.catalog[record.parent] = 
                        (data.catalog[record.parent] || {id: record.parent});
                (parent.children = parent.children || []).push(newRecord);
            } else {
                data.tree.push(newRecord);
            }
            return data;
        }, {catalog: {}, tree: []}).tree;
    }
}());

Note that this will work regardless of the order of the flat list -- the parent nodes do not have to precede their children -- although there is nothing in here to sort the nodes.


Original Version

My solution (also on JSFiddle):

var makeTree = (function() {
    var isArray = function(obj) {return Object.prototype.toString.call(obj) == "[object Array]"; };
    var clone = function(obj) {return JSON.parse(JSON.stringify(obj));};
    var buildTree = function(catalog, structure, start) {
        return (structure[start] || []).map(function(id, index) {
            var record = catalog[id];
            var keys = structure[start][index];
            var children = isArray(keys) ? keys.map(function(key) {
                return buildTree(catalog, structure, key);
            }) : buildTree(catalog, structure, keys);
            if (children.length) {
                record.children = children;
            }
            return record;
        })
    };
    return function(flat) {
        var catalog = flat.reduce(function(catalog, record) {
            catalog[record.id] = clone(record);
            delete(catalog[record.id].parent);
            return catalog;
        }, {});
        var structure = flat.reduce(function(tree, record) {
            (tree[record.parent] = tree[record.parent] || []).push(record.id);
            return tree;
        }, {});
        return buildTree(catalog, structure, 0); // this might be oversimplified.
    }
}());
like image 33
Scott Sauyet Avatar answered Oct 01 '22 01:10

Scott Sauyet