Chu  Y.J. Liu T.H. algorithm of building shortest root tree in oriented graph

© Sviatoslav Pimenov, Georgiy Korneev, Anatoly Shalyto

Saint-Petersburg State University of Information Technologies, Mechanics and Optics

Project documentation in Russian (PDF)
Source code

Visualizer (Russian, online)

Annotation

In this project we developed visualizer of algorithm of Chu Y.J. and Lui  T.H. It builds a tree with minimal weight in in the weighted directed graph. Visualizer contains examples, that demonstrates the basics of the algorithm and it’s important non-trivial parts. It is possible to edit built-in examples and to create new ones, that allows to see work of algorithm with every particular graph.

The visualizer is built on Vizi technology. The logics of algorithm is implemented in two automatons («direct» and «reverse») with 28 states in each. Automatons implemented using two switch statements: one chooses next state, another chooses action for current state. These automatons are generated from XML description of algorithm.