How to compare values in an array, that is inside an array of objects, with a property of the objects?

Question

I've got a graph with nodes that can be connected to multiple other nodes.

Every node is an object in an array. Within every node's object is an array that contains the ids of all the nodes linked to this node and its depth:

const nodes = [
    { "id": 37, "depth": 0, "children": [210, 395, 265], "next": [] },
    { "id": 210, "depth": 1, "children": [37, 260, 259, 391],"next": [] },
    { "id": 256, "depth": 2, "children": [265], "next": [] },
    { "id": 259, "depth": 2, "children": [210, 397, 396], "next": [] },
    { "id": 260, "depth": 2, "children": [210], "next": [] },
    { "id": 265, "depth": 1, "children": [37, 256, 388, 394, 271, 269], "next": [] },
    { "id": 269, "depth": 2, "children": [265], "next": [] },
    { "id": 271, "depth": 2, "children": [265], "next": [] },
    { "id": 388, "depth": 2, "children": [265], "next": [] },
    { "id": 391, "depth": 2, "children": [210], "next": [] },
    { "id": 394, "depth": 2, "children": [265], "next": [] },
    { "id": 395, "depth": 1, "children": [37], "next": [] },
    { "id": 396, "depth": 3, "children": [259, 413], "next": [] },
    { "id": 397, "depth": 3, "children": [259], "next": [] },
    { "id": 413, "depth": 4, "children": [396], "next": [] }
];

I would like to traverse the graph where the node with depth 0 is the root.

The problem is that a node's children array contains all the nodes linked to it. A node with a depth of 2 points back to a node with a depth of 1.

So I would like to create a new array within the nodes' objects, let's say nodes.next and get rid of the children that point back to a node that has a depth lower than itself.

I got it working after a while in two ways. In the first I checked if the length of the children's array is more than 1. Then I relied on the fact that the node in the children's array that should not be pushed to next, happens to be at index 0. That isn't very reliable.

What I found difficult in the second solution is checking if the depth of the nodes in the children's array is higher then the depth of the node in the current iteration. If it is, push it to the node's next array. I hope you can show how to do that in a better way, because this solution isn't pretty by any means:

let currentDepth;
let childDepth;
let currentID;
let childID;

const getChildDepth = (childID) => {
    for (let i = 0; i < nodes.length; i++) {
        if (childID === nodes[i].id) {
            childDepth = nodes[i].depth
        }
    }
};

for (let i = 0; j < nodes.length; j++) {
    currentDepth = nodes[j].depth;
    currentID = nodes[j].id;
    if (nodes[j].children.length > 1) {
        for (let i = 0; i < nodes[j].children.length; i++) {
            childID = nodes[j].children[i];
            getChildDepth(childID);
            if (childDepth > currentDepth) {
                nodes[j].next.push(childID)
            }
        }
    }
}

sample output:

const nodes = [
    { "id": 37, "depth": 0, "children": [210, 395, 265], "next": [210, 395, 265] },
    { "id": 210, "depth": 1, "children": [37, 260, 259, 391],"next": [260, 259, 391] },
    { "id": 256, "depth": 2, "children": [265], "next": [] },
    { "id": 259, "depth": 2, "children": [210, 397, 396], "next": [397, 396] },
    { "id": 260, "depth": 2, "children": [210], "next": [] },
    { "id": 265, "depth": 1, "children": [37, 256, 388, 394, 271, 269], "next": [256, 388, 394, 271, 269] },
    { "id": 269, "depth": 2, "children": [265], "next": [] },
    { "id": 271, "depth": 2, "children": [265], "next": [] },
    { "id": 388, "depth": 2, "children": [265], "next": [] },
    { "id": 391, "depth": 2, "children": [210], "next": [] },
    { "id": 394, "depth": 2, "children": [265], "next": [] },
    { "id": 395, "depth": 1, "children": [37], "next": [] },
    { "id": 396, "depth": 3, "children": [259, 413], "next": [413] },
    { "id": 397, "depth": 3, "children": [259], "next": [] },
    { "id": 413, "depth": 4, "children": [396], "next": [] }
];

Answer 1

You could take a Map as reference to the nodes and update next by filtering the children with a depth check.

var nodes = [{ id: 37, depth: 0, children: [210, 395, 265], next: [] }, { id: 210, depth: 1, children: [37, 260, 259, 391], next: [] }, { id: 256, depth: 2, children: [265], next: [] }, { id: 259, depth: 2, children: [210, 397, 396], next: [] }, { id: 260, depth: 2, children: [210], next: [] }, { id: 265, depth: 1, children: [37, 256, 388, 394, 271, 269], next: [] }, { id: 269, depth: 2, children: [265], next: [] }, { id: 271, depth: 2, children: [265], next: [] }, { id: 388, depth: 2, children: [265], next: [] }, { id: 391, depth: 2, children: [210], next: [] }, { id: 394, depth: 2, children: [265], next: [] }, { id: 395, depth: 1, children: [37], next: [] }, { id: 396, depth: 3, children: [259, 413], next: [] }, { id: 397, depth: 3, children: [259], next: [] }, { id: 413, depth: 4, children: [396], next: [] }],
    references = new Map(nodes.map(n => [n.id, n]));

nodes.forEach(node => node.next = node.children.filter(
    id => references.get(id).depth > node.depth
));

console.log(nodes);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Luckily, since the depths are explicitly noted in the objects, it's simple to map the nodes to another array and check the depths of each child, filtering out the ones whose depth is smaller. Make a Map of each node ID and its depth in advance for easy lookup:

const nodes = [
    { "id": 37, "depth": 0, "children": [210, 395, 265]},
    { "id": 210, "depth": 1, "children": [37, 260, 259, 391]},
    { "id": 256, "depth": 2, "children": [265]},
    { "id": 259, "depth": 2, "children": [210, 397, 396]},
    { "id": 260, "depth": 2, "children": [210]},
    { "id": 265, "depth": 1, "children": [37, 256, 388, 394, 271, 269]},
    { "id": 269, "depth": 2, "children": [265]},
    { "id": 271, "depth": 2, "children": [265]},
    { "id": 388, "depth": 2, "children": [265]},
    { "id": 391, "depth": 2, "children": [210]},
    { "id": 394, "depth": 2, "children": [265]},
    { "id": 395, "depth": 1, "children": [37]},
    { "id": 396, "depth": 3, "children": [259, 413]},
    { "id": 397, "depth": 3, "children": [259]},
    { "id": 413, "depth": 4, "children": [396]}
];
const depthsById = new Map(nodes.map(node => [node.id, node.depth]));
const nodesWithNext = nodes.map((node) => {
  const { depth } = node;
  const next = node.children.filter(childId => depthsById.get(childId) > depth);
  return { ...node, next};
});
console.log(nodesWithNext[0].next);
console.log(nodesWithNext[1].next);
console.log(nodesWithNext[10].next);
console.log('-------\n-------');
console.log(nodesWithNext);