Get from Ico-github-logo

Highlights from
Tree data structure as a MATLAB class

4.875

4.9 | 19 ratings Rate this file 119 Downloads (last 30 days) File Size: 34.8 KB File ID: #35623
image thumbnail

Tree data structure as a MATLAB class

by

 

13 Mar 2012 (Updated )

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

| Watch this File

File Information
Description

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/

MATLAB release MATLAB 7.14 (R2012a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (50)
18 Dec 2014 Grigory

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

07 Nov 2014 Jean-Yves Tinevez

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.

31 Oct 2014 Thomas Clark

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

27 Sep 2014 Muhammad Aneeq uz Zaman

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.

27 Sep 2014 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

27 Sep 2014 Muhammad Aneeq uz Zaman

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?

04 Jul 2014 Muhammad Aneeq uz Zaman

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.

04 Jul 2014 Jean-Yves Tinevez

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 )

03 Jul 2014 Muhammad Aneeq uz Zaman

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?

23 Jun 2014 Jean-Yves Tinevez

Thanks!

19 Jun 2014 Muhammad Aneeq uz Zaman

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

19 Jun 2014 Jean-Yves Tinevez

Hi @Muhammad.
Yes! It's in the doc:
http://tinevez.github.io/jyt-matlab/publish/html/TreeDemo/TreeDemo_traversal.html#8

19 Jun 2014 Muhammad Aneeq uz Zaman

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?

02 Jun 2014 Jean-Yves Tinevez

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

31 May 2014 kan

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.

12 May 2014 Farzaneh  
12 May 2014 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

11 May 2014 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?

11 May 2014 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 ?

27 Apr 2014 Jean-Yves Tinevez

Hi Yuantao. Any news?

18 Apr 2014 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.

18 Apr 2014 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"

03 Mar 2014 Rui  
06 Feb 2014 Jean-Yves Tinevez

@Sean: Yes, it is possible.
:)

05 Feb 2014 Sean

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

05 Feb 2014 Jean-Yves Tinevez

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

05 Feb 2014 Sean

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?

31 Jan 2014 Eric Nunes  
31 Jan 2014 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?

15 Jan 2014 Eric Nunes

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

15 Jan 2014 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

14 Jan 2014 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

10 Jan 2014 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.

23 Nov 2013 Hadi

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

10 Jul 2013 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.

10 Jul 2013 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).

21 Jan 2013 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.

23 Oct 2012 Alexander  
12 Sep 2012 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

11 Sep 2012 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

24 Aug 2012 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.

25 Jul 2012 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

25 Jul 2012 per isakson  
08 Jun 2012 Wolfgang Garn

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

27 May 2012 zain

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

11 May 2012 Werner  
09 May 2012 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.

07 May 2012 dai zhengguo

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

30 Apr 2012 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.

30 Apr 2012 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
13 Apr 2012

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

06 Aug 2013

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

06 Aug 2013

Put back the thumbnail.

10 Jul 2014

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

Contact us