Question 189937 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Creating a "tree" or directory structure from a object of (possibly circular) relations

Given a object whose keys are projects and values are dependencies. I’ve been trying to assemble a nested tree structure without any represented circular dependencies (think files and folders).

Here’s a simple example:

{
  'a': ['b'],
  'b': ['c'],
  'c': [],
}

This would create:

{
  'a': {
    'b': {
      'c': {}
    }
  }
}

Here are the "rules":

  1. any dependency that is not used by any other dependency should be at the top of the tree
  2. any dependency with only one use should be nested within that dependnecy and so on
  3. any dependency that is used by 2 or more dependencies it should be placed as a sibling of the highest node

Here’s a more complex example:

{
  'a': ['b', 'q'],
  'b': ['c', 'f'],
  'c': ['d'],
  'p': ['o'],
  'o': [],
  "d": [],
  'e': ['c'],
  "q": []
}

should be:

{
  'a': {
    'b': 
      "f": {},
    },
    'q': {},
  },
  "p": {
    'o': {},
  },
  "c": { // note this would first get put ito b, but because its used by e it becomes a sibling of the highest node
    "d"; {}
  },
  "e": {}
}

I’ve tried a bunch of solutions from working with nested dot keys to using full on class Node instances because of the circularity I keep runing into maximum call stack issues.

I’m also stuck becasuse of the nature of building up a node to have it relocate somewhere else in the tree.

I know this is a really open-ended problem but I’m wondering if there’s a simpler solution or way of thinking about it.

Tags:

2

Answers


  1. 0

    Try creating a graph, this seems like a two part solution since you have possible circular dependencies that you wont know about until the entire object is parsed. After you create the graph you can begin recursively popping off nodes and adding them to the new object.

    Login or Signup to reply.
  2. 0

    You could use a depth first traversal and create a node object for every visited key.

    function toNested(data) {
    const nodes = {};
    const roots = new Set(Object.keys(data));
    
    function dfs(key) {
        if (nodes[key]) return nodes[key];
        nodes[key] = {};
        for (const child of data[key] ?? []) {
            roots.delete(child);
            nodes[key][child] = dfs(child);
        }
        return nodes[key];
    }

    for (const key in data) {
        dfs(key);
    }
    for (const root of roots) { // There should be only one left
        return { [root]: nodes[root] };
    }
}

const data = {
  'a': ['b', 'q'],
  'b': ['c', 'f'],
  'c': ['d'],
  'p': ['o'],
  'o': [],
  "d": [],
  'e': ['c'],
  "q": []
}

console.log(toNested(data));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search