3.66667

3.7 | 3 ratings Rate this file 49 Downloads (last 30 days) File Size: 9.06 KB File ID: #24327
image thumbnail

Maximum(minimum) Weight Spanning Tree ( Directed )

by

 

02 Jun 2009 (Updated )

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

| Watch this File

File Information
Description

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

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (12)
15 May 2013 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.

12 Feb 2011 Amir

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

11 Feb 2011 Guangdi Li

Please check your Bioinformatic toolbox :)

11 Feb 2011 Amir

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?

12 Dec 2010 Guangdi Li

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

11 Dec 2010 Varsha

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

29 Nov 2010 Guangdi Li

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

28 Oct 2010 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.

17 May 2010 Seal Huang

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

14 May 2010 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!

09 Jul 2009 Guangdi Li

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.

08 Jul 2009 sweety

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
09 Jun 2009

only change the name :-)

25 Jun 2009

update the figure

26 Jun 2009

update the file because previous version has some mistakes

26 Jan 2010

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

17 Apr 2010

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

29 Nov 2010

Correct a small part

06 Jun 2013

update description

Contact us