1
$\begingroup$

Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good algorithm is needed, since I also have other .yaml files with more items.

Question: How can I convert a tree with recursive relationship between those elements to a parent-child tree.

FROM:

Tree with recursive relationship

TO:

Parent-Child tree

There are more elemtens like id=2 which have no parent anymore and the height of the resulting tree might vary.

What I tried so far:

  1. Find the lowest childen which is not parent of some other element
  2. Save those childen into a list/vector
  3. Iterate over this list/vector and connect parents which results into a linked list

But now I have the problem that I have to rotate the tree in some way in order to receive a tree from which I can create my tree view. I hope there is a better solution than I came up with.

List of linked nodes

Edit 1: If you parse such a .yaml file you will get a tree structure where each node has a key with a value or not. You can see in the picture that for example '2' is a key without a value and one childen with the name 'name'. The child 'name' itself has two children with the key 'en' and value 'Europe'.

You can say that those children are attributes from the item with the id '2' but still you will get a tree structure.

Now I want to make a tree which has in its first node the item with id '2' and all its 'attributes' and then in its child node the item with the id '3' and a sibling node with id '1'; and the item with the id '3' has a child node with id '4'.

yaml test file

Edit 2: What did I mean with 'recursive relationship': The term might be confusing and inappropiate in this situation. In a relational database model you can have a relationship from one relation (table) to itself. You call this a 'recursive relation'. The table would then have the columns 'id' and 'name' and 'parentID'.

I was hoping that this term makes my problem more clear because the 'parentID' does not refer to another .yaml file or some different id. However, it refers to some 'top' node (except the single root node) within the same file ('top'-node means image 1: node with id=1, id=2, id=3, id=4). If you think of those 'top' nodes being a tuple within a relational database you can say that the 'parentID' refers to another tuple which is related to it as parent.

The general rule, which I can think of is: I have a broken tree where actual parents/children are all siblings: (image 1 and image 4)

  • node with id=1 is sibling of node with id=2, id=3, id=4
  • node with id=2 is sibling of node with id=1, id=3, id=4
  • node with id=3 is sibling of node with id=1, id=2, id=4
  • node with id=4 is sibling of node with id=1, id=2, id=3

The child node 'parentID' of all those siblings tells me which node should be the parent node. Now I want to create a tree with the correct child-parent relation: (image 2)

  • node id=1 becomes a children of node id=2
  • node id=4 becomes a children of node id=3
  • node id=3 becomes a children of node id=2
  • node id=2 has no 'parentID' and so won't change its place

So, the algorithm has to:

  1. Find the parentID of one 'top' node (maybe with DFS)
  2. Find the correct parent (maybe iterate over all 'top' nodes and stop when id=parentID)
  3. Make the node (1.) the child of node (2.) (Maybe linked list or something else)
  4. Repeat until I went through all 'top' nodes

This algorithm could be good but there is the fact that there is no order within the file. So, at step (2.) I also have to go through all child nodes since my parent could already became a child of some other node. See image 1:

  • 'top'-node with id=1 becomes a children of 'top'-node with id=2
  • 'top'-node with id=2 has no parent (parentID=0) and won't change its place
  • 'top'-node with id=3 becomes a children of 'top'-node with id=2
  • 'top'-node with id=4 has now to become a children of node id=3
$\endgroup$
  • $\begingroup$ Can you give a formal description of how your input tree is represented (from a theoretical perspective) and what the output representation is supposed to be. This is not clear from your figure. For example, why does the node with parent_id=2 have the node with id 1 as its parent? $\endgroup$ – Steven May 29 at 12:13
  • $\begingroup$ @Steven I added additional information in my edit. I hope it makes my problem clear. $\endgroup$ – Simon Pio. May 29 at 13:28
  • $\begingroup$ What do you mean by a recursive relationship? I think of that as being exactly a tree. I don't understand the format, and a single example doesn't help me; it forces me to reverse engineer the general rule that you want to implement. Instead, I'd prefer that you figured out the general rule and told us about it. $\endgroup$ – D.W. May 29 at 23:01
  • $\begingroup$ @D.W. I hope my second edit helps. I don't really know what do you mean by general rule but I tried to explain my problem as far as I can. $\endgroup$ – Simon Pio. May 30 at 10:13
  • 1
    $\begingroup$ Please don't use "Stuff. EDIT: Stuff." Instead, edit the question to read well for someone who encounters it for the first time, and so it is self-contained. We have revision history, so no need to mark what is changed. $\endgroup$ – D.W. May 30 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.