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.
Now, my question is:
What's the best possibility to solve problems of this kind in a fast way with Sage?
