ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 12 Nov 2015 10:31:27 -0600How to draw special trees from a list consisting of tuples with Sage?http://ask.sagemath.org/question/30673/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 <code>L<sub>{ij}</sub>=[...]</code>. The entries of <code>L<sub>{ij}</sub></code> are special other tuples from `L`, which we call "compatible with the tuple `(i,j)`". So, in general, all the lists <code>L<sub>{ij}</sub></code> 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 <code>T<sub>1</sub>, ... , T<sub>r</sub></code>, which are compatible with T. Each of them shall be connected with `T` by a single line.
In the third level, for each tuple <code>T<sub>s</sub></code> of the second line, there are drawn all the tuples that are compatible with <code>T<sub>s</sub></code> **and** at the same time already appeared one level higher (here: in level 2). Call the tuples of this level <code>T<sub>1<sub>1</sub></sub>, ... , T<sub>1<sub>m</sub></sub>, T<sub>2<sub>1</sub></sub>, ... T<sub>2<sub>p</sub></sub>, ...</code>. Each of the <code>T<sub>1<sub>1</sub></sub>, ... , T<sub>1<sub>m</sub></sub></code> shall be connected with <code>T<sub>1</sub></code> by a single line. Each of the <code>T<sub>2<sub>1</sub></sub>, ... , T<sub>2<sub>p</sub></sub></code> shall be connected with <code>T<sub>2</sub></code> 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 <code>L<sub>{ij}</sub></code> 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!BernThu, 12 Nov 2015 10:31:27 -0600http://ask.sagemath.org/question/30673/