Developing Gato and CATBox with Python: Teaching graph algorithms through visualization and experimentation

A. Schliep and W. Hochstättler

In Multimedia Tools for Communicating Mathematics, Springer-Verlag, 291–310, 2002.

Teaching algorithms, especially graph algorithms, is one of the natural applications of multi-media in mathematics. The objects considered are of a highly dynamic nature and require an adequate dynamic visualization. CATBox, the combinatorial algorithm tool-box, is an interactive course combining a textbook with the visualization software Gato, the graph animation tool-box. For the design of Gato, the following simple rules were used to address issues of clearness of presentation, consistency, level of interactivity and software engineering. 1) Use a real programming language instead of pseudo-code: By choosing Python for presenting algorithms we bought consistency of the presentation at the expense of using a syntactically slightly more complex language compared to traditional pseudo-code. 2) Visualization based on rules: Interesting events (Brown 1998) in the visualization always correspond to changes to data-structures used in the algorithm. Therefore, those changes to data-structures should be tightly coupled to the corresponding visualization commands. For reasons of consistency and maintainability we added these `rules' as sub-classes of abstract classes implementing data-structures. This occasionally provided surprising insights even in the case of very simple algorithms. 3) Choose the appropriate software framework: Over a number of years various predecessors to CATBox, all under the same name but with slightly different feature sets, have been implemented in a number of ways. For the current implementation we chose Python/Tkinter, due to the rules mentioned above and its availability on a large number of computer-platforms. 4) Good Software Engineering: The applicable aspects of the `Extreme Programming' methodology were used for developing Gato. The application of these rules yields a software which allows learners to experiment with both problem instances and the algorithms themselves. We will also address software engineering issues arising in an academic setting with special emphasis on software quality control and cross-platform requirements. Additionally, positive experiences resulting from licensing Gato freely under the LGPL (Library GNU Public License) will be discussed.

A reprint is available as PDF.

DOI: 10.1007/978-3-642-56240-2_18.