Maximum(minimum) Weight Spanning Tree ( Directed )

版本 1.11.0.0 (9.1 KB) 作者: Guangdi Li
For learning "Directed Maximum Spanning Tree", Chu-Liu/Edmonds Algorithm is implemented here.
4.0
(4)
4.4K 次下载
更新时间 2013/6/6

查看许可证

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

引用格式

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. 检索来源 .

MATLAB 版本兼容性
创建方式 R2008a
兼容任何版本
平台兼容性
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/

版本 已发布 发行说明
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