ASKSAGE: Sage Q&A Forum - Latest question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 08 Aug 2019 14:05:02 -0500Plotting a LabelledOrderedTree with duplicate labelshttps://ask.sagemath.org/question/47443/plotting-a-labelledorderedtree-with-duplicate-labels/ I'm attempting to plot a labelled, ordered, rooted tree in Sage using the `LabelledOrderedTree` class. Here is what I have so far:
sage: n2 = LabelledOrderedTree([], label=2)
sage: n1 = LabelledOrderedTree([], label=1)
sage: root = LabelledOrderedTree([n2, n1], label=1)
sage: root
1[2[], 1[]]
At this point, I've created the tree I'm attempting to build, but here is where I run into problems:
sage: P = root.plot()
...
sage/graphs/base/sparse_graph.pyx in sage.graphs.base.sparse_graph.SparseGraphBackend.add_edge (build/cythonized/sage/graphs/base/sparse_graph.c:17158)()
ValueError: cannot add edge from 1 to 1 in graph without loops
Is there a way to plot a `LabelledOrderedTree` object when multiple nodes share the same label?nicklecoderThu, 08 Aug 2019 14:05:02 -0500https://ask.sagemath.org/question/47443/tree ordering in sagehttps://ask.sagemath.org/question/47414/tree-ordering-in-sage/I am using the following code to generate the isomorphism class of trees of order $n$.
sage: from sage.graphs.trees import TreeIterator
sage: def check_trees(n):
....: trees = []
....: for t in TreeIterator(n):
....: if not t.is_tree():
....: return False
....: if t.num_verts() != n:
....: return False
....: if t.num_edges() != n - 1:
....: return False
....: for tree in trees:
....: if tree.is_isomorphic(t):
....: return False
....: trees.append(t)
....: return True
Then when I print the trees in TreeIterator using loops it is giving the trees in a particular order.
Can anyone explain to me what is this predefined order on trees of order $n$ on sage?
For n = 6, we have the following order.
![image description](/upfiles/15651617426843846.png)
![image description](/upfiles/1565161758281800.png)
![image description](/upfiles/15651617758237095.png)
![image description](/upfiles/15651617961674227.png)
![image description](/upfiles/15651619136363882.png)
![image description](/upfiles/15651618394324058.png)GA316Tue, 06 Aug 2019 23:18:41 -0500https://ask.sagemath.org/question/47414/caterpillar graphs in sagehttps://ask.sagemath.org/question/47386/caterpillar-graphs-in-sage/ A caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.
How to define [caterpillar graphs](https://en.wikipedia.org/wiki/Caterpillar_tree) in sage? is it already implemented?
Kindly help me with this.
Thank you.
GA316Mon, 05 Aug 2019 01:57:15 -0500https://ask.sagemath.org/question/47386/Is map_reduce working for parallel computing? How?https://ask.sagemath.org/question/46711/is-map_reduce-working-for-parallel-computing-how/The following computation was done on a computer with 16 CPUs.
![image description](/upfiles/15592161891060146.png)
sage: seeds = [[]]
....: succ = lambda l: [l+[0], l+[1]] if len(l) <= 22 else []
....: S = RecursivelyEnumeratedSet(seeds, succ,structure='forest', enumeration='depth')
....: map_function = lambda x: 1
....: reduce_function = lambda x,y: x+y
....: reduce_init = 0
....: %time S.map_reduce(map_function, reduce_function, reduce_init)
....:
CPU times: user 15 ms, sys: 47 ms, total: 62 ms
Wall time: 58.4 s
16777215
But it seems that the computation did not exploit the CPUs in parallel, as the following screenshot show.
**Question**: What's wrong? How to exploit the CPUs in parallel?
![image description](/upfiles/15592157095194797.png)Sébastien PalcouxThu, 30 May 2019 06:39:40 -0500https://ask.sagemath.org/question/46711/How to implement a parallelization?https://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/Consider a code of the kind *tree exploration amassing fruits*: when the procedure arrives to a new node of the tree, if it is a leaf a possible fruit is collected, else a computation is done to determine the children of the node. I would like to parallelize as follows: the children are allocated to all the available CPUs, each CPU has a queue and a given child is allocated to the CPU with the smallest queue.
It seems to be a generic way to parallelize such a tree exploration.
**Question**: How to implement such a parallelization?
In addition, how to use GPU (for HPC)?
The code has the following form:
cpdef function(list L1, list L2):
cdef int i,n #...
cdef list LL1,LL2 #...
#...
# core of the code
#...
n= #...
for i in range(n):
LL1= #...
LL2= #...
function(LL1,LL2)Sébastien PalcouxMon, 27 May 2019 00:14:24 -0500https://ask.sagemath.org/question/46682/natural sub-class of trees in Sagehttps://ask.sagemath.org/question/43574/natural-sub-class-of-trees-in-sage/ I want to calculate certain parameter for class of trees like path graphs, star graphs. I dont want to calculate it for all trees with n vertices as this wont help me in my problem. Basically I need a natural class of trees.
I have found that path graph and star graph is available in sage.
If you can suggest me some other class of trees like this in sage it will be very helpful to me.
Thank you.GA316Tue, 04 Sep 2018 01:33:27 -0500https://ask.sagemath.org/question/43574/tree of vectorshttps://ask.sagemath.org/question/39425/tree-of-vectors/This is a more complicated version of
[apply functions iteratively](https://ask.sagemath.org/question/36159/apply-functions-iteratively-modified-re-post/)
I have a starting "seed" vector, say
`e1 = matrix(4,1,(1,0,0,0))`
Next, I have a collection of 4x4 matrices
`thin_group = [T1,T2,T3,T4,T5]`
where
$T1 = \left(\begin{array}{rrrr}
-1 & 0 & 0 & 0 \\\\
2 & 1 & 0 & 0 \\\\
4 & 0 & 1 & 0 \\\\
4 & 0 & 0 & 1
\end{array}\right), T2 = \left(\begin{array}{rrrr}
1 & 2 & 0 & 0 \\\\
0 & -1 & 0 & 0 \\\\
0 & 4 & 1 & 0 \\\\
0 & 4 & 0 & 1
\end{array}\right), T3 = \left(\begin{array}{rrrr}
1 & 0 & 1 & 0 \\\\
0 & 1 & 1 & 0 \\\\
0 & 0 & -1 & 0 \\\\
0 & 0 & 0 & 1
\end{array}\right), T4 = \left(\begin{array}{rrrr}
1 & 6 & 0 & 6 \\\\
0 & 3 & 0 & 2 \\\\
0 & 4 & 1 & 4 \\\\
0 & -4 & 0 & -3
\end{array}\right), T5 = \left(\begin{array}{rrrr}
3 & 0 & 0 & 2 \\\\
6 & 1 & 0 & 6 \\\\
4 & 0 & 1 & 4 \\\\
-4 & 0 & 0 & -3
\end{array}\right)$
These matrices either fix `e1` or send to a different vector. I have a "height" function, which just measures how large the vector entries are getting.
`def h(X):
return max(abs(X[0,0],abs(X[1,0]), abs(X[2,0]),abs(X[3,0]))`
I want to develop the following procedure:
`hmax = 50`
Begin applying T1,...,T5 to e1. As soon as I get a different vector (T1*e1 = (-1,2,4,4)), measure the height of that vector. If the height is below hmax (h(-1,2,4,4) = 4 < hmax = 50), store that vector somewhere. Now apply another matrix from thin_group to (-1,2,4,4), (but not T1 again). If the new vector has a height below hmax, store it, and apply another matrix from thin_group, just not the previous one. Continue this process until we reach a vector with a height larger than hmax. Once this happens, go back to the previous vector and apply a different matrix from thin_group i.e. go up a different branch of the tree. Go up this branch until hmax is exceeded, then go up a different branch, etc.. Eventually, this process will generate all thin_group images of e1 with hmax < 50. (this is probably about 50,000 vectors)
This procedure should "remember" the vectors that were counted/stored, so I'm thinking that I may be able to index each vector in the tree with a sequence (a1,a2,a3,...,an) where aj=1,2,3,4,5 to denote which matrix T1,...,T5 we applied previously.
Any/all ideas or partial solutions greatly appreciated. Thanks!Daniel LTue, 07 Nov 2017 12:01:32 -0600https://ask.sagemath.org/question/39425/Insert children of a specified node in a binary tree and retrieve all leaves of a binary tree.https://ask.sagemath.org/question/37512/insert-children-of-a-specified-node-in-a-binary-tree-and-retrieve-all-leaves-of-a-binary-tree/ I am trying to use a binary tree to store data. When different cases happens at some step, I will need to create two children from the current node.
I also need to collect all information on the leaves (nodes with no children). I use the following definition of binary trees:
from sage.misc.binary_tree import BinaryTree
T = BinaryTree();
I can insert node the following way:
t.insert(0,[1,2,4]);
t.insert(1,[4,5]);
t.insert(2,[5,0]);
But I couldn't find a way to visualize the tree. Also I don't know how to add two children of one certain node. For example, if `0` is the root (it seems so), `1` is its left child and `2` is its right child (which I am not sure), how do I make sure I add two children for the node `2`?
I also looked at this page: (http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/binary_tree.html). I couldn't see how to insert a node with values in it, or how to retrieve information of leaves.
Do I have to define my own tree structure?
Thank you for your help!KittyLThu, 04 May 2017 14:22:32 -0500https://ask.sagemath.org/question/37512/Is there a way to compute the list of rooted spanning trees or arborescences in a directed graph ?https://ask.sagemath.org/question/37274/is-there-a-way-to-compute-the-list-of-rooted-spanning-trees-or-arborescences-in-a-directed-graph/Given a directed graph $D$ and a specified vertex $r$, I would like the list of all directed spanning trees, or arborescences, rooted in $r$.
This can be computed by induction as is done for spanning trees in undirected graphs with the *spanning_trees* method of the class *Graph*, but it seems like this has not been implemented for directed graphs.David AugerThu, 13 Apr 2017 03:12:24 -0500https://ask.sagemath.org/question/37274/Edges associated to the variables in G.kirchhoff_symanzik_polynomial()https://ask.sagemath.org/question/35610/edges-associated-to-the-variables-in-gkirchhoff_symanzik_polynomial/ How do the variables t0, t1, t2,... in G.kirchhoff_symanzik_polynomial(), for a given undirected graph G, correspond to the edges of G? (i.e. what is the bijection between the variables ti and the edges of G?) The variables do not follow the same order as in the list G.edges(), which I thought was the case.
pmWed, 16 Nov 2016 06:05:38 -0600https://ask.sagemath.org/question/35610/How to draw special trees from a list consisting of tuples with Sage?https://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 -0600https://ask.sagemath.org/question/30673/treewidth()https://ask.sagemath.org/question/26011/treewidth/Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property?
To illustrate with a concrete example (not the one above):
M = Matrix([[0, 0, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0]])
g = Graph(M)
T = g.treewidth(certificate=True)
T.vertices()
This returns:
[{0}, {2}, {2, 3}, {0, 4}, {1, 2}]
Clearly (0,2) is an edge of the original graph
but the answer above does not have a bag
that contains both 0 and 2.
stormMon, 02 Mar 2015 19:41:25 -0600https://ask.sagemath.org/question/26011/Use a Binary Treehttps://ask.sagemath.org/question/25973/use-a-binary-tree/ Hi folks,
newbie alert.
I want to have a binary tree with a single integer value at each node. I'm looking at BinaryTree() but this seems to have the structure of a tree but without values!!!
Please point me in the right direction. I don't mind creating a class from scratch if I can just make a start.
Thanks
JoeJoeSat, 28 Feb 2015 13:27:34 -0600https://ask.sagemath.org/question/25973/Getting a rooted graph from a nested list of listshttps://ask.sagemath.org/question/9614/getting-a-rooted-graph-from-a-nested-list-of-lists/At [Trac 9329](http://trac.sagemath.org/sage_trac/ticket/9329), a very simple expression tree walker is defined.
def tree(expr):
if expr.operator() is None:
return expr
else:
return [expr.operator()]+map(tree,expr.operands())
This gives a nested list of lists, like
sage: tree(2*(x+2^x))
[<built-in function add>, [<built-in function mul>, [<built-in function pow>, 2, x], 2],
[<built-in function mul>, x, 2]]
I'm trying to build a similar walker which would (roughly speaking) give the following dictionary which I could plot as a tree.
Graph({'add':['mul-lev1-1','mul-lev1-2'],'mul-lev1-1':['pow-lev2-1','2-lev2-1'],
'pow-lev2-1':['2-lev3','x-lev3'],'mul-lev1-2':['x-lev2','2-lev2-2']}).show(
layout='tree',tree_root='add')
![Binary Tree of this expression](/upfiles/13548511202509835.png)
Naturally, the same element could appear as many times as one liked in any level of the tree, so the naming scheme probably would be overly ponderous... but I'm wondering whether anyone who understands `Converter` better than I do (which isn't saying much) can get around the problem that dictionaries of dictionaries don't work here in any case to build a nice tree walker that can make such graph-able dictionaries. 'Cause doing it by hand is not particularly fun.kcrismanThu, 06 Dec 2012 15:36:07 -0600https://ask.sagemath.org/question/9614/Distinct (nonisomorphic) treeshttps://ask.sagemath.org/question/9993/distinct-nonisomorphic-trees/"Construct all non-isomorphic trees of order 7"
How to do that in Sage ?!
Please helpMohabSun, 07 Apr 2013 07:24:14 -0500https://ask.sagemath.org/question/9993/Simple tree diagramhttps://ask.sagemath.org/question/9840/simple-tree-diagram/How can I plot a simple tree diagram like the first one of the following link?
http://reference.wolfram.com/mathematica/tutorial/TreeDrawing.html
Is it possible to choose the orientation (from left to right) and display edge labels?
Thank you.
KaiserfilkSat, 23 Feb 2013 14:42:22 -0600https://ask.sagemath.org/question/9840/How to use E.T.E. a Python tree package within Sage?https://ask.sagemath.org/question/9721/how-to-use-ete-a-python-tree-package-within-sage/Hi, [ETE](http://ete.cgenomics.org/) is a Python based tree building package with nice graphical support. Can I use it within Sage? Thanks, RolandRolandbSat, 19 Jan 2013 03:04:51 -0600https://ask.sagemath.org/question/9721/Traversing sage's symbolic expression trees in pythonhttps://ask.sagemath.org/question/9503/traversing-sages-symbolic-expression-trees-in-python/I'm writing some python code around sage and I need to build an expression tree of the following basic form:
- each node represents an operation
- each child tree represents an expression tree to which the operation applies
Can anyone point me in the right direction as to how to traverse an instance of `sage.symbolic.expression.Expression`, so as to extract this kind of semantic information? rmp251Mon, 12 Nov 2012 11:16:40 -0600https://ask.sagemath.org/question/9503/Best way to plot graphhttps://ask.sagemath.org/question/8226/best-way-to-plot-graph/Hello!
Could you pleas advise me the best way to plot graph with cycles and make it looks like tree? Here is the sample picture of result I'd like to have:
![image description](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e4/Artificial_neural_network.svg/350px-Artificial_neural_network.svg.png)
Plot on this pictures have 'layers', is there any chance to get something like this in Sage? I tried this:
t = DiGraph()
t.add_edge((0,1))
t.add_edge((0,2))
t.add_edge((0,3))
t.add_edge((0,4))
t.add_edge((4,9))
t.add_edge((3,9))
t.add_edge((2,9))
t.add_edge((1,9))
t.plot()
but the [result](http://img17.imageshack.us/i/sage0.png/) is far from desired.
Thanks.
EugeneThu, 14 Jul 2011 10:23:01 -0500https://ask.sagemath.org/question/8226/Treeplot()?https://ask.sagemath.org/question/8032/treeplot/Hi,
I'm aware that Mathematica has a treeplot() function which basically plots a rooted tree. I've been searching for a while now to see if Sage has similar functionality. I basically want to plot a tree diagram with the following adjacency matrix:
01110000
10001100
10000110
10001010
01010000
01100000
00110001
00001110
Can anyone help me? (Maybe I have to use networkx somehow...).
Thanks!
unraisedarcTue, 29 Mar 2011 05:49:35 -0500https://ask.sagemath.org/question/8032/