File Exchange

image thumbnail

Tree data structure as a MATLAB class

version 1.4 (279 KB) by

A per-value class that implements a generic tree data structure.

4.73077
33 Ratings

64 Downloads

Updated

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:
http://tinevez.github.io/matlab-tree/

Comments and Ratings (69)

Balaji

Balaji (view profile)

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!

Jean-Yves Tinevez

Hi @Simon.
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?

Jan Gläscher

Jan Gläscher (view profile)

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?

fmanar

fmanar (view profile)

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.

fmanar

fmanar (view profile)

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??

shachaf rotem

Song

Song (view profile)

Gread job !! But it would nice to integreate more properties into class, e.g. the depths, ID etc.

Song

Song (view profile)

Great job !!

cat cat

Can you help me to use the code? I don't understand how to use it...

Cheerie Ling

Hi Jean-Yves,
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.

Laura

Laura (view profile)

Matt

Matt (view profile)

Great stuff, saved me quite a bit of effort, thank you!

Arash Afshar

@Raziur: I sincerely don't know.

Raziur Rahman

Is there anything like this (Tree-Structure) for R-Programming?

Rob Campbell

Rob Campbell (view profile)

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.
E.J. Yoerger

Grigory

find() doesn't work in case tree has empty [] elements.

Hi @Thomas,
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.

Thomas Clark

Thomas Clark (view profile)

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?

Best regards

Tom Clark

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.

Jean-Yves Tinevez

Hi @Muhammad.
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.
Best
jy

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.

Hi @Muhammad.
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?

Jean-Yves Tinevez

Thanks!

Hi Jean-Yves thanks! I missed that one. Very good job by the way.

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?

Hi @kan,

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.
Best
jy

kan

kan (view profile)

Hi @Jean-Yves,
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.

Farzaneh

Farzaneh

@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

Jean-Yves Tinevez

Hi @Farzaneh,
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?

Farzaneh

@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 ?

Jean-Yves Tinevez

Hi Yuantao. Any news?

Jean-Yves Tinevez

Hi Yuantao.
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.

yuantao song

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"

Rui

Rui (view profile)

@Sean: Yes, it is possible.
:)

Sean

Sean (view profile)

@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?

@Sean: Thanks!
Yes. You cannot define addition for two trees that differ in structure. Imagine you are trying to add

1
|
2

to

3
|
5-+-6

It makes no sense.

Sean

Sean (view profile)

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?

Eric Nunes

Eric Nunes

@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?

Eric Nunes

@Jean Is it possible to add more content to the node apart from the data.

Jean-Yves Tinevez

@Eric: It is explained in the tutorial, shipped with the class. Check here:
http://www.mathworks.com/matlabcentral/fileexchange/35623-tree-data-structure-as-a-matlab-class/content/tree/TreeDemo_creating.html

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
disp(t.tostring)

If it does not work, contact me via email.
best
jy

Eric Nunes

Hi,
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.

Regards,
Eric

Jean-Yves Tinevez

@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.

Hadi

Hadi (view profile)

HI
I used your code but encounter with the error on line 60 at depthfirstiterator that there is mismatch [ , ) ! I use matlab R2009a

Jean-Yves Tinevez

@Scott: Hi,
This is a good idea, I'll put it in next release.
I also need to integrate Per Isakson contribution.

Scott Teuscher

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).

Steve Goley

Excellent implementation of the tree data structure. I really like the automatic plotting function although it gets a bit crowded for large trees.

Jean-Yves Tinevez

@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.

Best
jy

Skirt Zhang

@Jean-Yves Tinevez
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

Jean-Yves Tinevez

@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.

per isakson

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!
/ per

function path2root = findpath2root( this, nix )
path2root = cat( 2, nix, parent_ixs( nix ) );
function p2r = parent_ixs( ix )
if ix == 1
p2r = [];
else
pix = this.Parent( ix );
p2r = cat( 2, pix, parent_ixs( pix ) );
end
end
end

per isakson

Wolfgang Garn

Wolfgang Garn (view profile)

Excellent tool! I like the overloaded Matlab operators. Simple search and display methods.

zain

zain (view profile)

Just found what i need.
Thanks Jean-Yves Tinevez for this great tool.

Werner

Werner (view profile)

lixin fan

@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.

dai zhengguo

dai zhengguo (view profile)

A well defined tool for tree data structure, Thanks for your submission.

Jean-Yves Tinevez

@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.

lixin fan

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.

Updates

1.4

- Move to gihub
- Add some extra tuning capabilities to plots.

1.3

Put back the thumbnail.

1.2

- Iteration, plotting and string conversion can be done by forcing the children to be iterated in alphabetical (or any) order.
- Tree plotting hsa several new options to customize its look.
- Two new methods to condense and decondense a tree.

1.1

Fixed a severe bug in the chop method, noticed by Francisco Marquez Gutierrez (thanks!).

MATLAB Release
MATLAB 7.14 (R2012a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video