# AlgorithmAnimations: Displaying how algorithms compute

Graph algorithms are easy to visualize and indeed there already exists a variety of packages and programs to animate the dynamics when solving problems from graph theory. Still, and somewhat surprisingly, it can be difficult to understand the ideas behind the algorithm from the dynamic display alone.

CATBox consists of a software system for animating graph algorithms and a course book which we developed simultaneously. The software system presents both the algorithm and the graph and puts the user always in control of the actual code that is executed. He or she can set breakpoints, proceed in single steps and trace into subroutines. The graph, and additional auxiliary graphs like residual networks, are displayed and provide visual feedback. The course book, intended for readers at advanced undergraduate or graduate level, introduces the ideas and discusses the mathematical background necessary for understanding and verifying the correctness of the algorithms and their complexity. Computer exercises and examples replace the usual static pictures of algorithm dynamics.

For this volume we have chosen solely algorithms for classical problems from combinatorial optimization, such as minimum spanning trees, shortest paths, maximum flows, minimum cost flows, weighted and unweighted matchings both for bipartite and non-bipartite graphs.

We consider non-bipartite weighted matching, in particular in the geometrical case, a highlight of combinatorial optimization. In order to enable the reader to fully enjoy the beauty of the primal-dual solution algorithm for weighted matching, we present all mathematical material not only from the point of view of graph theory, but also with an emphasis on linear programming and its duality. This yields insightful and aesthetically pleasing pictures for matchings, but also for minimum spanning trees.

## Extras

There are two parts to the CATBox software: First, the open-source animation software Gato © 1998-2010 Alexander Schliep, and Winfried Hochstättler and copyright © 1998-2001 ZAIK/ZPR, an institute at the Unversität zu Köln licensed under the LGPL.
Second, there are algorithm implementations, algorithm visualizations and problem instances which are © 1998-2010 Alexander Schliep, Winfried Hochstättler, and © 2010 Springer Verlag Heidelberg.

These are not open source and you are not allowed to redistribute them.

 OS Filename Description MacOS X CATBox-1.1-MacOSX-10.5.dmg CATBox files including Gato binaries for MacOS X 10.5.x (Note: does not work with 10.6.x) . MacOS X CATBox-1.1-MacOSX-10.6.dmg CATBox files including Gato binaries for MacOS X 10.6.x and later. Windows 7 CATBox-1.1.exe CATBox files including Gato binaries for Windows 7 and Vista. Linux CATBox files including Gato binaries for x86 32bit Linux. All CATBox-1.1-Src.tar.gz CATBox and Gato source files.(Note: does not work with MacOS 10.6.x; vendor Tk/Tkinter broken)

## Installation

#### MacOS X

The easiest way to install everything is to download the file CATBox-1.1-MacOSX-10.6.dmg, double-click it and move Gato.app and Gred.app to the Applications folder and the CATBox to your Documents folder. Done.

#### Windows 7

The file CATBox-1.1.exe contains an installer application which, by default, will install Gato and Gred in a folder called Gato, and a folder called CATBox in your Documents folder. Done.

#### Linux

The file contains the executables Gato and Gred and a folder called CATBox. Move to your preferred locations. Done.

#### All Operating Systems

The file CATBox-1.1-Src.tar.gz contains all the necessary sources to install Gato and CATBox. After unpacking move the CATBox folder to a location of your choice. The actual installation for Gato uses Python's distutils.

##### Requirements
• Python version 2.6.x. Gato will not run with Python 3.x.
• Tk version 8.4.7 or above.
• Tkinter module enabled in Python.
Note that most modern operating systems come with Python and Tk preinstalled. Use your package manager to install necessary updates for Python 2.6.x or consult http://www.python.org/download/. It is easy to test that everything is setup properly:
```> python2.6
Python 2.6.2 (r262:71600, Aug 13 2009, 15:33:59)
[GCC 4.0.1 (Apple Inc. build 5490)] on darwin
>>> import Tkinter
>>> t = Tkinter.Tk()
>>>
```
should produce a small window. From the command line you can then install Gato with the following commands.
```> cd Gato
> python2.6 setup.py install
```
If you prefer a different install location than your system-wide Python installation, you can specify a different one
```> cd Gato
> python2.6 setup.py install --prefix=/home/schliep/test/
```
which will install Gato in /home/schliep/test/lib/python2.6/site-packages. Just make sure that that directory is on your PYTHONPATH and /home/schliep/test/bin is on your path. Done.

### Publications

Hochstättler, Winfried and Schliep, Alexander. CATBox – An Interactive Course in Combinatorial Optimization (2010) [details]

Contact: Alexander Schliep (alexander@schlieplab.org).