A tree is a hierarchical data structure where every node has exactly one parent (expect the root) and no or several children.
Along with this relational structure, each node can store any kind of data.
This class implements it using plain MATLAB syntax and arrays. Most useful methods are implemented, using overloading of MATLAB functions for tree objects.
For instance you can type:
>> find ( (a.^2 .* b) > (c - 5) & d )
with a, b, c and d being tree objects.
Very handy, trivial to use. A rather long tutorial is included to walk you through trees, and show how to make the best out of them.
The tutorial can be found here:
How to find preorder and post order of the tree??
how to find children of a node ??
Hello, thank you for the tutorial. each time i tried to display the tree by using "disp(t.tostring)" i get a message: No appropriate method, property, or field 'tostring' for class 'tree'. please what could possibly be the problem
Hello, thanks your tutorial is really helpful. But i need to know how can i extract a branch of a tree, starting from the root node to the leaf node.
Very nice clean class, great documentation. Unfortunately wasn't what I was looking for. I was hoping for something where I could retrieve the value of a node several layers down based on an inputted path , rather than just a search for the nodes reference. If this could be included it would allow people to create very large trees and select desired results fast.
It is a great class which I think should be a quintessential of matlab. It will be great if you can give examples of integration into other tree algorithms of matlab, which currently do not use a tree structure. Cant explain how much simple it made my life!
This is a MATLAB class so it cannot be installed as a series of script.
Please refer to MATLAB documentation on how to deal with classes on the path: https://mathworks.com/help/matlab/matlab_oop/organizing-classes-in-folders.html.
In short: the folder that contains the @tree folder should be on the path, but not the content of the @tree folder itself.
The package doesn't work for me... When i add the tree files to the path, then matlab gui can't do anything anymore. For instance opening a file fails because strcmp now refers to the function created for the tree. Also, the tree.example does not load, saying there's no such thing as tree.example. In fact following the tutorial almost no method are found in the class... What am i doing wrong here?
Hi Jean-Yves, thanks for putting the tree class together. Is it possible to put more information into the Node than just the name? For instance, can I put a struct in there or another cell array? And will the operators that you have defined for the tree class will still work then?
This package is best for someone who wants the conceptual idea of a tree, but isn't concerned with computational cost.
Implementation is very clean and easy to understand.
Looses a star because basic operations (i.e. getchildren) aren't implemented for fast evaluation. Should take O(1) time, but uses a search instead. Hence the comment on speed.
Hi when I try to create a tree structure using Matlab GUI it gives a message 'Struct contents reference from a non-struct array object.'
'Error in strcmp (line 28)
K = strcmp(obj.Node, str); '
Can you tell me the reason for this??
Gread job !! But it would nice to integreate more properties into class, e.g. the depths, ID etc.
Great job !!
Can you help me to use the code? I don't understand how to use it...
Thanks so much for sharing your codes. I have just started using it and have found it to be relevant to my current project which is clustering based. I need the codes to keep track of its member nodes: the parent (0) being the clusterhead. My problem is that I am unsure how to call 'tree' class from my main script. I tried run('.\tinevez\@tree\tree') but it does not work. I would be very grateful if you could advise me how to get my main script to interact with your codes.Thanks again.
Great stuff, saved me quite a bit of effort, thank you!
@Raziur: I sincerely don't know.
Is there anything like this (Tree-Structure) for R-Programming?
Thanks, I was about to role my own and this saved me the time. Well written and well commented.
Hi Mr. Tinevez-
I just downloaded your tree software and started using it. I am attempting to build a tree structure dynamically. I start at the root and have 4 nodes which in turn can have 4 nodes, and those can have 4 more nodes, etc. Of course, after about 4-8 levels of nodes, a particular branch will terminate. I eventually want to find all paths (connected branches) as well as the longest path. My issue is that your documentation that I downloaded shows the names of the nodes a being hard coded. Is there anyway to make this dynamically allocated so that I get a new name for a new node (child?) whenever I come across one?
I thank you in advance for any help.
find() doesn't work in case tree has empty  elements.
Thank you very much for the positive feedback.
As for your suggestion, I shall contact you via email to start the discussion on the technical side. But just a remark: Your construct is very elegant and it is a good idea to implement it. However, note that it depends on the iteration order of sibling nodes, which is not what you can expect from the plots.
Jean-Yves, thank you for an extraordinarily well documented and well put together submission.
This is an extremely useful tool straight out of the box. I also think it's a hallmark of the best submissions that it's possible to actually learn about the aspect of computer science they cover (in this case trees) from the documentation, as well as simply how to implement the code (given presupposed knowledge on the concept).
I've learned a lot today, and this submission will form the basis of a planned refactoring of the way my company manages frame of reference changes in multi body simulations.
I have one question on indexing however. Is it possible/sensible to implement a sub2ind() type method for the tree, so that for example you could retrieve branches or leaves based on their location in the tree?
For example, in your smaller example of the C.elegans lineage tree (the image in the submission), t.get(2,1,3) could return 'E.ar'. That way you don't need to keep a database of the single indices corresponding to each node.
I'd be happy to help with this if you'd be interested in collaborating - being more familiar with the code, perhaps you could suggest a good strategy/starting point?
Yes I was able to concatenate all the functions I needed in one file and run it (for some reason the 'eq' function doesn't seem to work). But there seems to be another problem, matlab coder won't work with cell arrays so I guess I am out of luck. But thanks any way.
In theory nothing prevents you from concatenating all the methods file in the class main file, inside a 'methods' block. Except that it would make the code completely unreadable and unmaintainable. I did this mistake once for another contribution (the msdanalyzer) and won't do it again.
Hi Jean-Yves, I am trying to compile my project using matlab coder and it is returning error "Cannot load '.../tree/@tree/tree.m' because code generation does not support classes and enumerations in @-directories." So the problem seems to be the @-directory which is needed for a multi-file class definition. Would you have any idea how to convert it into a single file class def?
Hi Jean-Yves, thanks that was very helpful. Btw is your implementation going to be more efficient than isequal because currently its taking a big chunk of my computation. If its faster it would save a lot of time for me.
Indeed, to compare the equality between two matrices, we would need the isequal method to be implemented.
This is not the case for @tree right now; I will do it for the next release.
In the meantime, you would have to do something like
>> cellfun(@(x) isequal(x, a), t.Node )
Hi Jean-Yves, I have a tree of matrices, all of the same dimensions. And I want to search the tree for a particular matrix. I tried find(tree == matrix) but it doesn't work, it gives me weird data. Then I tried a = (tree == matrix);prod(a); which works for column vectors but not for matrices. Is there a function that can help me?
Hi Jean-Yves thanks! I missed that one. Very good job by the way.
Yes! It's in the doc:
Hi Jean-Yves, I was wondering if we know the index of a node, is there an easy way to find out the index of its parent or child/children?
Indeed, you need to have at least MATLAB 2008a to use the @tree class. It is based on the new class definition that MATLAB shipped starting from this version.
when I executed ' t = tree ', I ran into the following error:
...\tree.m Line: 23 Column: 27
The expression to the left of the equals sign is not a valid target for an assignment.
Since this is my first time do OOP with Matlab, I'm wondering if it is because of the old version of my Matlab(7.0.0).
I'm sorry for bothering you with this kind of problem.
@Dear Jean-Yves : you're right , I checked and found my mistake , because I just copied @tree without .DS_Store in main path , I had this problem . thanks a lot
Like for @Yuantao I suspect a problem with the installation. Can you check the output of
>> which tree
and make sure it points to the actual tree class?
@Jean-Yves Tinevez : Thanks for this tool , i have a problem for plot a tree , when i want to use plot function , i recieve this error :
"??? Undefined function or method 'permuteIfNeeded' for input arguments of type 'tree'."
i also tried with your exmaple in toturial and the result was same error as above . can you help me please ?
Hi Yuantao. Any news?
I suspect a problem with path and installation here. Can you check the output of
>> which tree
and make sure it points to the actual tree class.
I write "t = tree", the system told me "Error using tree (line 28) missing input arguments"
I write "t = tree('I am the root node')", the matlab told me "Error using tree (line 62)Number of names in string"
@Sean: Yes, it is possible.
@Jean-Yves, thanks for the prompt response. Is it possible to add some routine that constructs the tree from linkage matrix in future release (http://www.mathworks.com/help/stats/linkage.html), and a quick way of getting of all leaf nodes of a subtree?
Yes. You cannot define addition for two trees that differ in structure. Imagine you are trying to add
It makes no sense.
Thanks for the great work! The is a great tool. @Jean-Yves: for the tree operators such as a+b, is it true that a and b must have the exact same structure?
@Jean: I constructed the tree using the tree data structure, now I have a root with the nodes and parent as its contents. I am trying to use the function depthtree as:
dt = depthtree(root)
But I am getting the error:
No appropriate method, property, or field depthfirstiterator for class tree.
Error in depthtree (line 9)
iterator = obj.depthfirstiterator;
Do I have to run the depthfirstiterator before depthtree?
@Jean Is it possible to add more content to the node apart from the data.
@Eric: It is explained in the tutorial, shipped with the class. Check here:
Basically, you get the ID of the node you just attached using the following syntax:
t = tree('root');
[ t node1 ] = t.addnode(1, 'Node 1'); %% attach to root
% node1 now contains the index of the first node.
[ t node2 ] = t.addnode(1, 'Node 2'); %% attach to root
[ t node11 ] = t.addnode(node1, 'Child of node 1'); %% attach to first node
If it does not work, contact me via email.
I am using the tree data structure for matlab, and found your tree class really helpful. I have few confusions , I am building a tree and adding nodes as we proceed from the root to the leaves, in that case how do i add nodes , since I don't know what the ID is going to be of the node which is going to split up. Also does the children of the same parent have the same ID.
@Hadi: I cannot reproduce your error, the function is working fine on my side. Unfortunately, I don't have MATLAB R2009 to investigate whether it is a backward compatibility problem.
I used your code but encounter with the error on line 60 at depthfirstiterator that there is mismatch [ , ) ! I use matlab R2009a
This is a good idea, I'll put it in next release.
I also need to integrate Per Isakson contribution.
Can the construction of the trees be vectorized? for example I have an ordered vector X which has the parent of each node and I could create a tree by t=tree(X).
Excellent implementation of the tree data structure. I really like the automatic plotting function although it gets a bit crowded for large trees.
@Skirt: Thanks! Unfortunately this class cannot do what you want. What you describe here is a simple graph, of which this tree is just a specialization (this is actually an even more specialized *rooted tree* in a tree, all nodes but the root have exactly one parent, and edges have a direction).
You can make a tree out of a simple undirected graph (simple pick one particular node, and name it "the root"), but I think that you could beneficiate from a proper data structure class for what you want.
There exist some basis on which you could build in MATLAB, using e.g. the adjacency matrix (used in gplot http://www.mathworks.fr/fr/help/matlab/ref/gplot.html) which is an unspecialized sparse matrix.
This is a great application. I need to build up a tree where the some nodes have multiple parents, so far I have not found the solution... can you help me about this? thanks a lot in advance
@per isakson: Thanks! I would like to add your function to the class. Do you have the metrics that shows that it is 1 order of magnitude faster? I could put it in a new published file.
I experiment with this Tree class to keep meta-data of a HDF5-file in memory. The file contains thousands of time series and it will be a back-end of a visualization tool. I want to read the series at random and present the result promptly. That is a bit of a challenge. Now I have something running, which looks promising. The Tree class plays a key role.
The code works well; I have had no real problems. The documentation is good. The class fills a gap; how come there isn’t a tree class in Matlab?
I added one method to the class, findpath2root. It is order of magnitude faster than findpath when one of the nodes is the root. It could be included in findpath.
Thanks a lot for this contributions!
function path2root = findpath2root( this, nix )
path2root = cat( 2, nix, parent_ixs( nix ) );
function p2r = parent_ixs( ix )
if ix == 1
p2r = ;
pix = this.Parent( ix );
p2r = cat( 2, pix, parent_ixs( pix ) );
Excellent tool! I like the overloaded Matlab operators. Simple search and display methods.
Just found what i need.
Thanks Jean-Yves Tinevez for this great tool.
@Jean-Yves: I am starting to use your tool. So far I haven't encountered any problems. I will keep you updated when deeper trees are created. Thanks for your assistance.
A well defined tool for tree data structure, Thanks for your submission.
@lixin: as for memory, I am pretty sure that the overhead is kept minimal. Speed performance, however, I don't know. If you want, we can work to solve your issues if you encounter then as your project goes.
Looks a quite nice tool. Solid and elegant!
I am planning to create some deep trees, probably with dozens (or hundreds) of depths and thousands of nodes. Just wonder if performance will be an issue.
- Move to gihub
Put back the thumbnail.
- Iteration, plotting and string conversion can be done by forcing the children to be iterated in alphabetical (or any) order.
Fixed a severe bug in the chop method, noticed by Francisco Marquez Gutierrez (thanks!).