Code covered by the BSD License

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

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

# Maximum(minimum) Weight Spanning Tree ( Directed )

### Guangdi Li (view profile)

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)
06 Mar 2015 Hayro

### Hayro (view profile)

What are the complexities of these algorithms?

Comment only
15 May 2013 Berkan Sesen

### Berkan Sesen (view profile)

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

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

Comment only
11 Feb 2011 Guangdi Li

Comment only
11 Feb 2011 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 );

Comment only
12 Dec 2010 Guangdi Li

### Guangdi Li (view profile)

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

Comment only
11 Dec 2010 Varsha

### Varsha (view profile)

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

Comment only
29 Nov 2010 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.

Comment only
28 Oct 2010 Hanif uet

### Hanif uet (view profile)

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.

Comment only
17 May 2010 Seal Huang

### Seal Huang (view profile)

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

14 May 2010 Seal Huang

### Seal Huang (view profile)

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!

Comment only
09 Jul 2009 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.

Comment only
08 Jul 2009 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 )

09 Jun 2009 1.2

only change the name :-)

25 Jun 2009 1.5

update the figure

26 Jun 2009 1.6

update the file because previous version has some mistakes

26 Jan 2010 1.7

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

17 Apr 2010 1.8

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

29 Nov 2010 1.10

Correct a small part

06 Jun 2013 1.11

update description