Set of all children

Question

Given a set of nodes and directed edges (from parent to child node), is it possible to construct an indexed set S_Children(i_node) that contains all children of the specified node?

With all children I mean the set of all reachable nodes, starting from i_node.

For example:

s_Nodes := {A, B, C}

s_Edges := {(A, B), (B, C)}

Then I would want:

s_Children(A) := {B, C}

Edit:

The edges are actually defined through a binary parameter. i.e.

p01_edge(A, := 1;

p01_edge(B, C) := 1;

icon

Best answer by LowBjorn 13 September 2021, 14:10

View original

LowBjorn · Accepted Answer

I have found a recursive solution allong the following lines:

Define s_Children(i_node) to contain all direct descendants
Define s_ChildrenAux(i_node) to contain all direct descendants of each node in s_Children(i_node), minus the nodes already contained in s_Children(i_node)
Add s_ChildrenAux(i_node) to the set s_Children(i_node) and clear the auxiliary set.
Repeat until no elements exist in the auxiliary set after generation.

It works, and is quick enough. If there’s an answer without a loop I would still be very interested.

mohansx · Answer

@LowBjornglad you were able to figure it out. This is a graph traversal problem, so I think you will need some kind of loop to find all the children. I will try to spend some time and see if we can improve on your approach.

Set of all children

4 replies

Reply

Reply

Sign up

Login to the community

Scanning file for viruses.

This file cannot be downloaded