ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 26 Nov 2015 04:28:31 -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!Thu, 12 Nov 2015 10:31:27 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/Comment by Bern for <p>I have the following problem:</p>
<p>Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list <code>L</code>.</p>
<p>To every tuple <code>(i,j)</code> 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 <code>L</code>, which we call "compatible with the tuple <code>(i,j)</code>". So, in general, all the lists <code>L<sub>{ij}</sub></code> are different from one another.</p>
<p>I would like the PC to draw trees in the following manner:</p>
<p>In the first level, there is one tuple T. This was manually chosen from the list <code>L</code>.</p>
<p>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 <code>T</code> by a single line. </p>
<p>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> <strong>and</strong> 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. </p>
<p>Iterate this, until the process stops (is finished) and you have drawn a tree.</p>
<p>The arrows of the tree are just edges and the points are the tuples, that should be numbered by <code>(1,1), ... , (k,n)</code>. Note that not every entry of <code>L</code> has to appear in the resulting tree, since the lists <code>L<sub>{ij}</sub></code> need not be a partition of <code>L</code>.</p>
<p>Here is a small example: </p>
<pre><code>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)].
</code></pre>
<p>This gives the following tree for <code>(1,1)</code>:</p>
<pre><code> (1,1)
--------------|--------------
| | |
(2,1) (2,2) (2,3)
| |
| |
(2,2) (2,1)
</code></pre>
<p>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 <code>(1,1)-(2,1)-(2,2)</code> and <code>(1,1)-(2,2)-(2,1)</code> and <code>(1,1)-(2,3)</code>) should be returned (there are no repetitions allowed in the branches).</p>
<p>Now, my question is:</p>
<blockquote>
<p>What's the best possibility to solve problems of this kind in a fast way with Sage?</p>
</blockquote>
<p>Thanks for the help!</p>
http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30878#post-id-30878Since 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).Thu, 19 Nov 2015 05:58:59 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30878#post-id-30878Comment by Bern for <p>I have the following problem:</p>
<p>Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list <code>L</code>.</p>
<p>To every tuple <code>(i,j)</code> 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 <code>L</code>, which we call "compatible with the tuple <code>(i,j)</code>". So, in general, all the lists <code>L<sub>{ij}</sub></code> are different from one another.</p>
<p>I would like the PC to draw trees in the following manner:</p>
<p>In the first level, there is one tuple T. This was manually chosen from the list <code>L</code>.</p>
<p>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 <code>T</code> by a single line. </p>
<p>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> <strong>and</strong> 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. </p>
<p>Iterate this, until the process stops (is finished) and you have drawn a tree.</p>
<p>The arrows of the tree are just edges and the points are the tuples, that should be numbered by <code>(1,1), ... , (k,n)</code>. Note that not every entry of <code>L</code> has to appear in the resulting tree, since the lists <code>L<sub>{ij}</sub></code> need not be a partition of <code>L</code>.</p>
<p>Here is a small example: </p>
<pre><code>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)].
</code></pre>
<p>This gives the following tree for <code>(1,1)</code>:</p>
<pre><code> (1,1)
--------------|--------------
| | |
(2,1) (2,2) (2,3)
| |
| |
(2,2) (2,1)
</code></pre>
<p>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 <code>(1,1)-(2,1)-(2,2)</code> and <code>(1,1)-(2,2)-(2,1)</code> and <code>(1,1)-(2,3)</code>) should be returned (there are no repetitions allowed in the branches).</p>
<p>Now, my question is:</p>
<blockquote>
<p>What's the best possibility to solve problems of this kind in a fast way with Sage?</p>
</blockquote>
<p>Thanks for the help!</p>
http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30697#post-id-30697Hi, 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.Thu, 12 Nov 2015 19:17:43 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30697#post-id-30697Comment by fidbc for <p>I have the following problem:</p>
<p>Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list <code>L</code>.</p>
<p>To every tuple <code>(i,j)</code> 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 <code>L</code>, which we call "compatible with the tuple <code>(i,j)</code>". So, in general, all the lists <code>L<sub>{ij}</sub></code> are different from one another.</p>
<p>I would like the PC to draw trees in the following manner:</p>
<p>In the first level, there is one tuple T. This was manually chosen from the list <code>L</code>.</p>
<p>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 <code>T</code> by a single line. </p>
<p>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> <strong>and</strong> 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. </p>
<p>Iterate this, until the process stops (is finished) and you have drawn a tree.</p>
<p>The arrows of the tree are just edges and the points are the tuples, that should be numbered by <code>(1,1), ... , (k,n)</code>. Note that not every entry of <code>L</code> has to appear in the resulting tree, since the lists <code>L<sub>{ij}</sub></code> need not be a partition of <code>L</code>.</p>
<p>Here is a small example: </p>
<pre><code>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)].
</code></pre>
<p>This gives the following tree for <code>(1,1)</code>:</p>
<pre><code> (1,1)
--------------|--------------
| | |
(2,1) (2,2) (2,3)
| |
| |
(2,2) (2,1)
</code></pre>
<p>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 <code>(1,1)-(2,1)-(2,2)</code> and <code>(1,1)-(2,2)-(2,1)</code> and <code>(1,1)-(2,3)</code>) should be returned (there are no repetitions allowed in the branches).</p>
<p>Now, my question is:</p>
<blockquote>
<p>What's the best possibility to solve problems of this kind in a fast way with Sage?</p>
</blockquote>
<p>Thanks for the help!</p>
http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30681#post-id-30681Is 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)`?Thu, 12 Nov 2015 14:44:36 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30681#post-id-30681Comment by Bern for <p>I have the following problem:</p>
<p>Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list <code>L</code>.</p>
<p>To every tuple <code>(i,j)</code> 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 <code>L</code>, which we call "compatible with the tuple <code>(i,j)</code>". So, in general, all the lists <code>L<sub>{ij}</sub></code> are different from one another.</p>
<p>I would like the PC to draw trees in the following manner:</p>
<p>In the first level, there is one tuple T. This was manually chosen from the list <code>L</code>.</p>
<p>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 <code>T</code> by a single line. </p>
<p>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> <strong>and</strong> 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. </p>
<p>Iterate this, until the process stops (is finished) and you have drawn a tree.</p>
<p>The arrows of the tree are just edges and the points are the tuples, that should be numbered by <code>(1,1), ... , (k,n)</code>. Note that not every entry of <code>L</code> has to appear in the resulting tree, since the lists <code>L<sub>{ij}</sub></code> need not be a partition of <code>L</code>.</p>
<p>Here is a small example: </p>
<pre><code>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)].
</code></pre>
<p>This gives the following tree for <code>(1,1)</code>:</p>
<pre><code> (1,1)
--------------|--------------
| | |
(2,1) (2,2) (2,3)
| |
| |
(2,2) (2,1)
</code></pre>
<p>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 <code>(1,1)-(2,1)-(2,2)</code> and <code>(1,1)-(2,2)-(2,1)</code> and <code>(1,1)-(2,3)</code>) should be returned (there are no repetitions allowed in the branches).</p>
<p>Now, my question is:</p>
<blockquote>
<p>What's the best possibility to solve problems of this kind in a fast way with Sage?</p>
</blockquote>
<p>Thanks for the help!</p>
http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30677#post-id-30677Hi,
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.Thu, 12 Nov 2015 14:10:00 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30677#post-id-30677Comment by tmonteil for <p>I have the following problem:</p>
<p>Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list <code>L</code>.</p>
<p>To every tuple <code>(i,j)</code> 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 <code>L</code>, which we call "compatible with the tuple <code>(i,j)</code>". So, in general, all the lists <code>L<sub>{ij}</sub></code> are different from one another.</p>
<p>I would like the PC to draw trees in the following manner:</p>
<p>In the first level, there is one tuple T. This was manually chosen from the list <code>L</code>.</p>
<p>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 <code>T</code> by a single line. </p>
<p>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> <strong>and</strong> 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. </p>
<p>Iterate this, until the process stops (is finished) and you have drawn a tree.</p>
<p>The arrows of the tree are just edges and the points are the tuples, that should be numbered by <code>(1,1), ... , (k,n)</code>. Note that not every entry of <code>L</code> has to appear in the resulting tree, since the lists <code>L<sub>{ij}</sub></code> need not be a partition of <code>L</code>.</p>
<p>Here is a small example: </p>
<pre><code>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)].
</code></pre>
<p>This gives the following tree for <code>(1,1)</code>:</p>
<pre><code> (1,1)
--------------|--------------
| | |
(2,1) (2,2) (2,3)
| |
| |
(2,2) (2,1)
</code></pre>
<p>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 <code>(1,1)-(2,1)-(2,2)</code> and <code>(1,1)-(2,2)-(2,1)</code> and <code>(1,1)-(2,3)</code>) should be returned (there are no repetitions allowed in the branches).</p>
<p>Now, my question is:</p>
<blockquote>
<p>What's the best possibility to solve problems of this kind in a fast way with Sage?</p>
</blockquote>
<p>Thanks for the help!</p>
http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30676#post-id-30676According 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)-....`Thu, 12 Nov 2015 13:57:28 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=30676#post-id-30676Answer by vdelecroix for <p>I have the following problem:</p>
<p>Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list <code>L</code>.</p>
<p>To every tuple <code>(i,j)</code> 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 <code>L</code>, which we call "compatible with the tuple <code>(i,j)</code>". So, in general, all the lists <code>L<sub>{ij}</sub></code> are different from one another.</p>
<p>I would like the PC to draw trees in the following manner:</p>
<p>In the first level, there is one tuple T. This was manually chosen from the list <code>L</code>.</p>
<p>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 <code>T</code> by a single line. </p>
<p>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> <strong>and</strong> 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. </p>
<p>Iterate this, until the process stops (is finished) and you have drawn a tree.</p>
<p>The arrows of the tree are just edges and the points are the tuples, that should be numbered by <code>(1,1), ... , (k,n)</code>. Note that not every entry of <code>L</code> has to appear in the resulting tree, since the lists <code>L<sub>{ij}</sub></code> need not be a partition of <code>L</code>.</p>
<p>Here is a small example: </p>
<pre><code>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)].
</code></pre>
<p>This gives the following tree for <code>(1,1)</code>:</p>
<pre><code> (1,1)
--------------|--------------
| | |
(2,1) (2,2) (2,3)
| |
| |
(2,2) (2,1)
</code></pre>
<p>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 <code>(1,1)-(2,1)-(2,2)</code> and <code>(1,1)-(2,2)-(2,1)</code> and <code>(1,1)-(2,3)</code>) should be returned (there are no repetitions allowed in the branches).</p>
<p>Now, my question is:</p>
<blockquote>
<p>What's the best possibility to solve problems of this kind in a fast way with Sage?</p>
</blockquote>
<p>Thanks for the help!</p>
http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?answer=31013#post-id-31013From what I understood or your vague description, this is one possibility
def make_tree(G, root):
r"""
This function output a pair ``(tree, labels)`` where the tree is on the
nodes `{0, 1, 2, ..., n-1}` and the labels is a list of tuples of length
``n`` that correspond to the label of the vertices.
"""
T = DiGraph()
labels = [root]
n = 0
leaves = [(0,root,set([root]))]
current = set(G)
while leaves:
new_leaves = []
new_current = set()
for i,u,b in leaves:
for _,v,_ in G.outgoing_edges(u):
if v in current and v not in b:
labels.append(v)
n += 1
T.add_edge(i,n)
new_leaves.append((n,v,b.union([v])))
new_current.add(v)
leaves = new_leaves
current = new_current
return T,labels
def tree_from_graph(T, i, labels):
r"""
This function makes a labelled tree out of a graph in a recursive way.
"""
children = [tree_from_graph(T, j, labels) for _,j,_ in sorted(T.outgoing_edges(i), key=lambda x: labels[x[1]])]
return LabelledOrderedTree(children, label=labels[i])
Then if you load this file in Sage (e.g. with %runfile) you can do
sage: compatibility = {
....: (1,1): [(2,2), (2,3), (2,1)],
....: (1,2): [(1,3), (2,1)],
....: (1,3): [(1,2)],
....: (2,1): [(1,1), (1,2),(2,2)],
....: (2,2): [(1,1), (2,1)],
....: (2,3): [(1,1)] }
sage: G = DiGraph(compatibility)
sage: T, labels = make_tree(G, (1,1))
sage: tree_from_graph(T, 0, labels)._ascii_art_()
______(1, 1)__
/ / /
(2, 1) (2, 2) (2, 3)
| |
(2, 2) (2, 1)
Tue, 24 Nov 2015 08:59:13 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?answer=31013#post-id-31013Comment by vdelecroix for <p>From what I understood or your vague description, this is one possibility</p>
<pre><code> def make_tree(G, root):
r"""
This function output a pair ``(tree, labels)`` where the tree is on the
nodes `{0, 1, 2, ..., n-1}` and the labels is a list of tuples of length
``n`` that correspond to the label of the vertices.
"""
T = DiGraph()
labels = [root]
n = 0
leaves = [(0,root,set([root]))]
current = set(G)
while leaves:
new_leaves = []
new_current = set()
for i,u,b in leaves:
for _,v,_ in G.outgoing_edges(u):
if v in current and v not in b:
labels.append(v)
n += 1
T.add_edge(i,n)
new_leaves.append((n,v,b.union([v])))
new_current.add(v)
leaves = new_leaves
current = new_current
return T,labels
def tree_from_graph(T, i, labels):
r"""
This function makes a labelled tree out of a graph in a recursive way.
"""
children = [tree_from_graph(T, j, labels) for _,j,_ in sorted(T.outgoing_edges(i), key=lambda x: labels[x[1]])]
return LabelledOrderedTree(children, label=labels[i])
</code></pre>
<p>Then if you load this file in Sage (e.g. with %runfile) you can do</p>
<pre><code>sage: compatibility = {
....: (1,1): [(2,2), (2,3), (2,1)],
....: (1,2): [(1,3), (2,1)],
....: (1,3): [(1,2)],
....: (2,1): [(1,1), (1,2),(2,2)],
....: (2,2): [(1,1), (2,1)],
....: (2,3): [(1,1)] }
sage: G = DiGraph(compatibility)
sage: T, labels = make_tree(G, (1,1))
sage: tree_from_graph(T, 0, labels)._ascii_art_()
______(1, 1)__
/ / /
(2, 1) (2, 2) (2, 3)
| |
(2, 2) (2, 1)
</code></pre>
http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=31081#post-id-31081The code is not very documented, do not hesitate to ask more if you need. There are at least good pointers to the relevant Sage objects: **Digraph** and **LabelledOrderedTree**.Thu, 26 Nov 2015 04:28:31 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=31081#post-id-31081Comment by Bern for <p>From what I understood or your vague description, this is one possibility</p>
<pre><code> def make_tree(G, root):
r"""
This function output a pair ``(tree, labels)`` where the tree is on the
nodes `{0, 1, 2, ..., n-1}` and the labels is a list of tuples of length
``n`` that correspond to the label of the vertices.
"""
T = DiGraph()
labels = [root]
n = 0
leaves = [(0,root,set([root]))]
current = set(G)
while leaves:
new_leaves = []
new_current = set()
for i,u,b in leaves:
for _,v,_ in G.outgoing_edges(u):
if v in current and v not in b:
labels.append(v)
n += 1
T.add_edge(i,n)
new_leaves.append((n,v,b.union([v])))
new_current.add(v)
leaves = new_leaves
current = new_current
return T,labels
def tree_from_graph(T, i, labels):
r"""
This function makes a labelled tree out of a graph in a recursive way.
"""
children = [tree_from_graph(T, j, labels) for _,j,_ in sorted(T.outgoing_edges(i), key=lambda x: labels[x[1]])]
return LabelledOrderedTree(children, label=labels[i])
</code></pre>
<p>Then if you load this file in Sage (e.g. with %runfile) you can do</p>
<pre><code>sage: compatibility = {
....: (1,1): [(2,2), (2,3), (2,1)],
....: (1,2): [(1,3), (2,1)],
....: (1,3): [(1,2)],
....: (2,1): [(1,1), (1,2),(2,2)],
....: (2,2): [(1,1), (2,1)],
....: (2,3): [(1,1)] }
sage: G = DiGraph(compatibility)
sage: T, labels = make_tree(G, (1,1))
sage: tree_from_graph(T, 0, labels)._ascii_art_()
______(1, 1)__
/ / /
(2, 1) (2, 2) (2, 3)
| |
(2, 2) (2, 1)
</code></pre>
http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=31071#post-id-31071Thank you very much for your answer.Wed, 25 Nov 2015 21:08:31 -0600http://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/?comment=31071#post-id-31071