Minimum Spanning Tree

ROOT
1

Hi,

Can root make a minimum spanning tree from a set of given (3D) points or does it have any other form of cluster analysis?

Thanks,
J

2

Hi,

Not exactly sure what you are looking for . Is it something like the
program/ilbrary LEDA (mpi-sb.mpg.de/LEDA/leda.html) ?

We just installed in the latest release a linear/quadratic programming
unit that can be used to optimize network flow problems, like
the “shortest path” .

Eddy

3

Yes, exactly. It’s just that LEDA is commercial and you need a license, as I understand it.
I do basically all of my analysis with ROOT and I thought maybe one could somehow use TTree to obtain a minimum spanning tree.

Cheers,
J

4

[quote=“jodenhei”]Yes, exactly. It’s just that LEDA is commercial and you need a license, as I understand it.
I do basically all of my analysis with ROOT and I thought maybe one could somehow use TTree to obtain a minimum spanning tree.
[/quote]

Does your ttree store events containing hits which you want to cluster, or do you want to cluster multiple tree entries together? There is little in common between TTrees and MSTs, other than the name, so I wouldn’t imagine that a TTree would be useful for constructing a MST, particularly if you want to cluster each event individually.

What about the boost graph library? I’ve not used it but it appears to be well documented and has some MST construction code.

mike