Rule-based Animation of Algorithms using Animated Data Structures in Gato

Schliep, Alexander and Hochstättler, Winfried and Pattberg, Torsten (2001) Rule-based Animation of Algorithms using Animated Data Structures in Gato.
Technical Report p.


Graph algorithms make up the core of the classical computer science curriculum, due to the easy accessibility of graphs, their wide applicability and the large spectrum of algorithmic classes and approaches they support. Also, they are a natural target for algorithm animation, as they are both graphic and dynamic in nature~cite{brown84,Stasko88,hudson.stasko:animation,soft-vis,Stasko97}. When developing Gato (Graph Animation Toolbox), we wanted to address the following important concerns in developing algorithm animations. Firstlyanimations should be consistent with respect to interesting events~cite{brown98} within the same algorithm, moreover they should be consistent among distinct algorithms as well. In the authors' opinion, this suggests a declarative approach~cite{crescenzi97,leonardo-url} with {em animation rules} providing an immediate link between {em cause} --- an instruction in an algorithm --- and {em effect} --- a change in the visualization. Secondly, the animations should be easy to implement in order to speed up the costly development process. The animation rules should be reusable, as they typically apply to whole algorithm classes dealing with the same problem; a rule hierarchy similar to class hierarchies in object-oriented programming does seem natural. Thirdly, students should be able to easily change algorithms already implemented and animated without interfering with the animation. Also, the implementation of new algorithms from scratch should be aided by an animation method which allows to obtain at least a ''low-grade'' animation automatically. We have developed the concept of an animated data structure (ADS), which link visualization instructions to methods accessing data structures, such as queues, central to graph algorithms. Observing that interesting events in graph algorithms can be defined in terms of changes to those data structures, ADSs provide an efficient and simple solution successfully addressing the concerns above.

Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2001-410
Depositing User: Alexander Schliep
Date Deposited: 06 Apr 2002 00:00
Last Modified: 16 Jan 2012 13:16