Maximum(minimum) Weight Spanning Tree ( Directed )

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

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)

[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]

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]

Please check your Bioinformatic toolbox :)

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

[Guangdi Li]

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

[Varsha]

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

[Guangdi Li]

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]

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.

[Lila]

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 )