Maximum(minimum) Weight Spanning Tree ( Directed )

Version 1.11.0.0 (9.06 KB) by Guangdi Li
For learning "Directed Maximum Spanning Tree", Chu-Liu/Edmonds Algorithm is implemented here.
4.0
(4)
4.4K Downloads
Updated 6 Jun 2013

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

Cite As

Guangdi Li (2024). Maximum(minimum) Weight Spanning Tree ( Directed ) (https://www.mathworks.com/matlabcentral/fileexchange/24327-maximum-minimum-weight-spanning-tree-directed), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2008a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

DirectedSpanningTree/

DirectedSpanningTree/AdvanceUser/

DirectedSpanningTree/Subfunction/

Version Published Release Notes
1.11.0.0

update description
1.10.0.0

Correct a small part
1.8.0.0

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

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

update the file because previous version has some mistakes
1.5.0.0

update the figure
1.2.0.0

only change the name :-)
1.0.0.0