File Exchange

image thumbnail

Maximum(minimum) Weight Spanning Tree ( Directed )

version 1.11 (9.06 KB) by

For learning "Directed Maximum Spanning Tree", Chu-Liu/Edmonds Algorithm is implemented here.

4 Downloads

Updated

View License

We use the idea of Chu-Liu/Edmonds Algorithm, see paper [1,2], to implement four functions here.
1. Maximal Directed Maximum Spanning Tree
By DirectedMaximumSpanningTree.m
2. Minimal Directed Maximum Spanning Tree
By DirectedMinimalSpanningTree.m
3. Maximal Directed Maximum Spanning Forest
By MaximalDirectedMSF.m
4. Minimal Directed Maximum Spanning Forest
By MinimalDirectedMSF.m

One could start with "ControlCenter.m", here is one simple example and explanation for how to use the code.
As for advance users, I also improve the code by mex programming , it is able to handle variables over 1000 in dataset, check the fold named as : AdvanceUser
If there is any problem, please let me know, i will help you as soon as possible.

Attention: mex compiler should be ready in your matlab.

[1] Y. J. Chu and T. H. Liu, ``On the shortest arborescence of a directed graph'', Science Sinica, v.14, 1965, pp.1396-1400.
[2] J. Edmonds, ``Optimum branchings'', J. Research of the National Bureau of Standards, 71B, 1967, pp.233-240.

If you use this code, please cite our paper:

Bielza, C., Li, G. & Larrañaga, P. (2011). Multi-Dimensional Classification with Bayesian Networks. International Journal of Approximate Reasoning, 52, 705-727

Comments and Ratings (15)

Shoujun Zhou

I wish you can provide a paper and souce data for an application.

Hey is there a more recent SearchCycleNode.c which is more easily compiled?

Hayro

Hayro (view profile)

What are the complexities of these algorithms?

Berkan Sesen

I spent half a day to get this working. My mex compiler on Windows MatLab works, but SearchCycleNode.c cannot be compiled...
If you are using Windows, this submission is useless I guess. The author claims it works with Linux matlab but I couldn't test.

Amir

Amir (view profile)

I have checked the bioinformatic toolbox but it did not install. Could you please tell me how can I add this toolbox to Matlab?

Guangdi Li

Guangdi Li (view profile)

Please check your Bioinformatic toolbox :)

Amir

Amir (view profile)

Hi,
When I want to run it in matlab under Linux (R2009a)
it happens an error :

Undefined function or method 'biograph' for input arguments of type 'double'.

Error in ==> DirectedMaximumSpanningTree at 31
[ CNumber, Component ] = conncomp( biograph( TreeMatric ),'Weak', true );

Would you please help me in this error?

Guangdi Li

Guangdi Li (view profile)

please try to compile the code under linux matlab, the problem can be solved.

Varsha

Varsha (view profile)

Seal Huang , how did you solve this problem? I am having the same problem

Guangdi Li

Guangdi Li (view profile)

It's better to test "mex" in your system at first, details are available from both matlab help system and online help.

Hanif uet

I am trying to run these M-file but it gives error like,

??? Error using ==> mex at 221
Unable to complete successfully.

Error in ==> ControlCenter at 2
mex SearchCycleNode.c
I have MATLAB version R2009B.

How can i solve this problem.
Waiting for ur Response.

Seal Huang

I have solved my problem. Thank you for your code~

Seal Huang

Thanks for your code. I tried to compile the file SearchCycleNode.c, but I can not find a proper compiler.
When seting my compiler, I just saw
[1] "Lcc-win32 C 2.4.1 in C:\PROGRA~1\MATLAB\R2009a\sys\lcc "
[0] None
And if I choose [1], I would see
------------------------------------------------------------------------
Error SearchCycleNode.c: 10 illegal statement termination
Error SearchCycleNode.c: 10 skipping `int'
Error SearchCycleNode.c: 10 undeclared identifier `ClusterNode'
Error SearchCycleNode.c: 10 type error: pointer expected
Warning SearchCycleNode.c: 10 Statement has no effect
Error SearchCycleNode.c: 14 type error: pointer expected
Error SearchCycleNode.c: 19 illegal statement termination
Error SearchCycleNode.c: 19 skipping `int'
Error SearchCycleNode.c: 19 undeclared identifier `Visited'
Error SearchCycleNode.c: 19 type error: pointer expected
Error SearchCycleNode.c: 19 undeclared identifier `List'
Error SearchCycleNode.c: 19 type error: pointer expected
Warning SearchCycleNode.c: 19 Statement has no effect
Error SearchCycleNode.c: 20 illegal statement termination
Error SearchCycleNode.c: 20 skipping `double'
Error SearchCycleNode.c: 20 undeclared identifier `TreeMatric'
Error SearchCycleNode.c: 20 type error: pointer expected
Error SearchCycleNode.c: 20 type error: pointer expected
Error SearchCycleNode.c: 20 undeclared identifier `CostMatrix'
Error SearchCycleNode.c: 20 type error: pointer expected
Error SearchCycleNode.c: 20 type error: pointer expected
Error SearchCycleNode.c: 20 undeclared identifier `OriginalCostMatric'
Error SearchCycleNode.c: 20 too many errors

C:\PROGRA~1\MATLAB\R2009A\BIN\MEX.PL: Error: Compile of 'SearchCycleNode.c' failed.

??? Error using ==> mex at 218
Unable to complete successfully.
---------------------------------------------------------------------------
Can you tell me how can I compile the file successfully?
Thank you very much!

Guangdi Li

Guangdi Li (view profile)

As an internal function, '[S, C] = conncomp(BGObj)' is a function from Bioinformatics toolbox.
The error happens because of the Matlab version of your software doesn't support Bioinformatics toolbox.
My advice is that you update Matlab above the version 2008a, or at least 2007b.
Please let me know if there is any problem, i will help you as soon as possible.

sweety

sweety (view profile)

Thanks for the spanning tree code. I tried to run all individual file but wasn't able to run can u tell me which file should i run.
When I run controlcenter file this msg came, can u tell me how to fix it. thank you so much....
----------------------------------------------------------------------------
??? Undefined command/function 'conncomp'.

Error in ==> DirectedMaximumSpanningTree at 28
[ CNumber, Component ] = conncomp( biograph( TreeMatric ),'Weak', true );

Error in ==> ControlCenter at 12
[MaxTree1,MaxCost1] = DirectedMaximumSpanningTree( CostMatric,Root )

Updates

1.11

update description

1.10

Correct a small part

1.8

Thanks to Talya Meltzer's comment, the bug is corrected in the new version.

1.7

I improve the efficiency by mex programming, in order to handle more than 1000 variables in short computation time.

1.6

update the file because previous version has some mistakes

1.5

update the figure

1.2

only change the name :-)

MATLAB Release
MATLAB 7.6 (R2008a)

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

» Watch video