Tree like data structure

Question

Hi i am working on a problem and could do with some help, i am working in C#.

What i'm trying to do is create a data structure as follows:

I need to layout out item with x and y co-ordinates on a page. Now the actual laying out is not a problem is more about having a valid set of co-ordinates.

Each item in my list can have multiple parents and multiple children where the starting item has no parents which defines it as a start element.

Now all i need to do is get the co-ordinates for each element so that everything is positioned correctly with the parents above the children in a centered position.

If an element has only 1 child then the child is placed below the parent on the same x co-ordinate, if the parent has more than one child then the children are placed with equal spaces apart and the parent needs to be in the middle above the children to two equal length lines join to both the children from the parent.

Also an element can have parents in more than one level too.

I have a graphical file of what i am trying to do to give you a better example if anyone has any thoughts or advice for me. Let me know if your interested and i can drop you a mail with the file too.

Thanks

Answer 1

I think that it's not possible without further restrictions on the data. For example, the data could contain a cycle, in which case it is impossible for the condition that parents are drawn above children to hold.

I could think of an algorithm that does what you need for a tree-like graph:

1. from bottom to top calculate the needed width for an element:
   • that's 1 for leaf nodes
   • it's n*x for a node T, that has n child nodes and x is the width of the widest child
2. layout the graph from top to bottom with respect to the nodes' calculated width