How to draw special trees from a list consisting of tuples with Sage?
I have the following problem:
Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list L.
To every tuple (i,j) I have associated a list L{ij}=[...]. The entries of L{ij} are special other tuples from L, which we call "compatible with the tuple (i,j)". So, in general, all the lists L{ij} are different from one another.
I would like the PC to draw trees in the following manner:
In the first level, there is one tuple T. This was manually chosen from the list L.
In the second level, there are all the tuples T1, ... , Tr, which are compatible with T. Each of them shall be connected with T by a single line.
In the third level, for each tuple Ts of the second line, there are drawn all the tuples that are compatible with Ts and at the same time already appeared one level higher (here: in level 2). Call the tuples of this level T11, ... , T1m, T21, ... T2p, .... Each of the T11, ... , T1m shall be connected with T1 by a single line. Each of the T21, ... , T2p shall be connected with T2 by a single line, and so on.
Iterate this, until the process stops (is finished) and you have drawn a tree.
The arrows of the tree are just edges and the points are the tuples, that should be numbered by (1,1), ... , (k,n). Note that not every entry of L has to appear in the resulting tree, since the lists L{ij} need not be a partition of L.
Here is a small example:
Let L=[(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)].
Let L_{11}=[(2,2), (2,3), (2,1)].
Let L_{12}=[(1,3), (2,1)].
Let L_{13}=[(1,2)].
Let L_{21}=[(1,1), (1,2),(2,2)].
Let L_{22}=[(1,1), (2,1)].
Let L_{23}=[(1,1)].
This gives the following tree for (1,1):
(1,1)
--------------|--------------
| | |
(2,1) (2,2) (2,3)
| |
| |
(2,2) (2,1)
Not only the tree, but also its "longest" branches (i.e. these, that can no more be extended by the procedure above...in the above example, these are (1,1)-(2,1)-(2,2) and (1,1)-(2,2)-(2,1) and (1,1)-(2,3)) should be returned (there are no repetitions allowed in the branches).
Now, my question is:
What's the best possibility to solve problems of this kind in a fast way with Sage?
Thanks for the help!
According to your definition, i do not understand why there is no infinite branch in your example like
(1,1)-(2,1)-(2,2)-(2,1)-(2,2)-(2,1)-(2,2)-(2,1)-(2,2)-(2,1)-(2,2)-....Hi, thank you for your comment. I draw the tree in order to find longest branches of tuples that are compatible with one another...therefore, I would prefer to have no repetitions in the branches...this was not clear from my original question...I edited it now.
Is the example still wrong or is there something missing? It seems like
(2, 2)should not have any descendants since(1, 1)and(2, 1)have already appeared. Also, shouldn't(1, 2)be a child of(2, 1)?Hi, thank you for your comment. $(1,1)$ and $(2,1)$ appeared in level 2. So, in level 3 we write down $(2,1)$ as a descendant of $(2,2)$, since it is compatible with $(2,2)$. This is true for $(1,1)$, too, but we didn't allow repetitions...$(1,1)$ would be a descendant and an ancestor.
$(1,2)$ is no descendant of $(2,1)$, because it did not appear in level 2.
Since I did not explain it very well in the original question, I would like to add the following comment for clarification:
If we choose an arbitrary, but fixed, branch, then it is not allowed that a fixed tuple appears both as a predecessor and an ancestor (this is what I meant by repetitions). But, one fixed tuple can appear in two neighboring branches (this is what I forgot to mention).