Solved

Set of all children

  • 8 September 2021
  • 4 replies
  • 35 views

Userlevel 1
Badge

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

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.

View original

4 replies

Userlevel 5
Badge +2

@LowBjorn how did you declare/construct the set s_Edges ? Is it related to the set of nodes s_Nodes or, the tuples (A, B) … are read in from an external source ? 

Userlevel 1
Badge

@mohansx I just realised that the formulation of my question was a little off compared to my aimms structure. In fact, the edges are defined through a binary parameter that indicates if an edge exists from node1 to node2. e.g. p01_EdgeExists(node1, node2) := 1; indicates that there is an edge.

I updated my post.

Userlevel 1
Badge

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.

Userlevel 5
Badge +2

@LowBjorn glad 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. 

Reply


Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator