Maximum(minimum) Weight Spanning Tree ( Directed )

Versión 1.11.0.0 (9,06 KB) por Guangdi Li
For learning "Directed Maximum Spanning Tree", Chu-Liu/Edmonds Algorithm is implemented here.
4.0
(4)
4,4K descargas
Actualizado 6 jun 2013

Ver licencia

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

Citar como

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. Recuperado .

Compatibilidad con la versión de MATLAB
Se creó con R2008a
Compatible con cualquier versión
Compatibilidad con las plataformas
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/

Versión Publicado Notas de la versión
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