Gato: Graph Animation Toolbox

Gato is a is a software which visualizes algorithms on graphs. Graphs are mathematical objects consisting of vertices and edges connecting pairs of vertices: think of cities as vertices and interstates as edges connecting two cities. Algorithms might find a *shortest path* -- the fastest route -- or a *minimal spanning tree* or solve one of other interesting problems on graphs: *maximal-flow*, *weighted* and *non-weighted matching* and *min-cost flow*. Visualization means linking cause - the statements of an algorithm - immediately to an effect - changes to the graph the algorithm has as its input - by terms of blinking, changing colors and other visual effects.

Gato is used in CATBox (the Combinatorial Algorithm Toolbox - an interactive course on discrete mathematics) available from Springer Verlag and has been used for courses on algorithms - both in the Computer Science and the Mathematics department - taught at the University of Cologne, the Technical University Cottbus and Free University Berlin. You find binary releases at http://schliep.org/CATBox/

Collaborators

Winfried Hochstättler is the principal textbook author for the CATBox project, which uses Gato. Torsten Pattberg is a student research assistant who implemented and visualized algorithms for CATBox and also contributed to Gato.

Also Ramazan Buzdemir and Achim Gädke contributed as research assistants to Gato. Ramazan implemented graph layout algorithms for use in Gred, the graph editor in Gato. Achim worked on the graph editor.

Development

Gato is an open source project licensed under the GNU Library General Public License. Contributors are welcome. The development is hosted at Sourceforge at http://sourceforge.net/projects/gato. For downloads, documentation please go to the main Gato site at http://gato.sf.net.

Currently under development are a 3D-Graph viewer using OpenGL. Above you see a maximal flow in a capicated network computed with a preflow-push algorithm: unused edges are white, edges used partially light and up to capacity dark blue. Edges in a minimal cut are displayed in yellow. The z-coordinate of a vertex is proportional to its potential.

For further information see the main website at http://gato.sf.net/ or contact Alexander Schliep (alexander@schlieplab.org). This software is a result of or used in the following projects: AlgorithmAnimations.

Team

Members: Alexander Schliep, Janne Grunau, Scott Merkling. Collaborators: Winfried Hochstättler (Fernuniversität Hagen, Institut für Mathematik).

Publications

Hochstättler et al.. CATBox – An Interactive Course in Combinatorial Optimization. Springer, 2010.

Schliep et al.. Developing Gato and CATBox with Python: Teaching graph algorithms through visualization and experimentation. In Multimedia Tools for Communicating Mathematics, Springer-Verlag, 291–310, 2002.