Code covered by the BSD License

### Highlights from Maximum(minimum) Weight Spanning Tree ( Directed )

3.66667

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

# Maximum(minimum) Weight Spanning Tree ( Directed )

02 Jun 2009 (Updated )

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

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.

[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)
15 May 2013

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

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

11 Feb 2011

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 );

12 Dec 2010

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

11 Dec 2010

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

29 Nov 2010

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

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

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

14 May 2010

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

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

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 )

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