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": [] }
];

Can you provide a sample output format?

Eddie
– Eddie

2018-06-04 05:59:10 +00:00
Commented Jun 4, 2018 at 5:59 — Eddie
– Eddie, Commented Jun 4, 2018 at 5:59
got it, updated the question

Vialito
– Vialito

2018-06-04 06:01:46 +00:00
Commented Jun 4, 2018 at 6:01 — Vialito
– Vialito, Commented Jun 4, 2018 at 6:01

Nina Scholz · Accepted Answer · 2018-06-04 06:28:03Z

2

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; }

answered Jun 4, 2018 at 6:28

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Vialito Over a year ago

It happened to me a few times already that I'm trying to solve a problem like this with a few for loops and make it more complex than it is. You solved it in a few lines and the right ids are returned to nodes.next, too. I'll have to practise more using map and js array methods, this really helped me in the right direction doing that, thank you.

CertainPerformance · Accepted Answer · 2018-06-04 06:04:49Z

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);

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related