CATBox - An interactive course in Combinatorial Optimization

Image of the front cover of the CATBox book.

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 available from Springer which we developed simultaneously. The software 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 the 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.

WebGato

Explore all of the algorithms included in CATBox online at the WebGato site. This alternative to the desktop Gato software provides an online presentation allowing forward and backward animations of all algorithms used in the book with a selection of graph instances.

From the 1.2.5 release onwards it is possible to generate HTML files for playing your own animations over the web with the desktop Gato desktop software.

Note that the software behing WebGato, the standards-compliant JavaScript-player included with Gato, is licensed under the GPL version 3 or later. It has been developed by Scott Merkling and Alexander Schliep and is copyright © 2014-21 Alexander Schliep, and copyright © 2014-16 Scott Merkling.

Samples

You can download a sample chapter covering computing maximal flows in capacitated networks: CATBox-Sample-MaxFlows.pdf
Online version of Dijkstra's algorithm for computing shortest paths.
Online version of Kruskal's algorithm for computing minimal spanning trees.

Download

There are two main parts to the CATBox software: The open-source animation software Gato and the algorithm implementations. Gato is copyright © 2016-2021 Alexander Schliep, copyright © 1998-2015, Alexander Schliep and Winfried Hochstättler, and copyright © 1998-2001 ZAIK/ZPR, Universität zu Köln, Germany. It is licensed under the LGPL. In addition there are algorithm implementations, algorithm visualizations and problem instances which are © 1998-2021, Winfried Hochstättler and Alexander Schliep and © 2010 Springer Verlag.

The files below contain Gato and CATBox version 1.2.7 which has been released on 1/25/2021. Changes in this release include:

Still Python 2.7, but cleanup for Python 3.x.
Paned modus is now default.
Added -s --separate command line options for old standard behaviour with two graph windows.
Added replay (r), undo (u), do (d) key commands alllowing to play back animation commands (used to be experimental).
Fixed bugs in undo command.
Fixed bugs in WM interaction.
Enabled SVG export of graph in current animation state and saving of animations as HTML.

OS	Filename	Description
All	`CATBox-1.2.7-Algorithms.tar.gz`	Archive containing only the CATBox algorithms source files. Use when installing Gato from PyPi.
All	`CATBox-1.2.7-Src.tar.gz`	Archive containing CATBox and Gato source files.
MacOS	`CATBox-1.2.7.dmg`	CATBox files including Gato binaries for MacOS X 10.15 (not tested on other versions of MacOS).
Windows 10	`CATBox-1.2.7-setup.exe`	CATBox installer including Gato and Gred binaries and CATBox-Algorithms for Windows 10.

Installation

Note there are issues with code signing of the binaries depending on the MacOS version. On MacOS 10.15 right clicking and chosing open on the apps will allow you to run them. Note that the apps will ask for permission to access System Events. There is one AppleScript command to force Tkinter windows to go to the front (see line 2359 of Gato.py, similarly for Gred.py).

As an alternative use the source distribution and build the apps yourself using python2.7 setup-mac-gato.py py2app and python2.7 setup-mac-gred.py py2app.

On 10.14 and 10.15, the easiest way to install everything is to download the file CATBox-1.2.7.dmg, double-click it and move Gato.app and Gred.app to the Applications folder and the CATBox to your Documents folder. Save HTML animations you generate with Gato to CATBox/MyAnimations where you find subdirectories js and css containing the necessary JavaScript and CSS code.

The file CATBox-1.2.7-setup.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.

The easiest way is to install Gato from PyPi and download the algorithms CATBox-1.2.7-Algorithms.tar.gz. Alternatively, download CATBox-1.2.7-Src.tar.gz.

The latter file 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.7.x. Gato will not run on Python 3.x yet.
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.7.x or consult http://www.python.org/download/. It is easy to test that everything is setup properly:

> python2.7
Python 2.7.2 (r262:71600, Aug 13 2009, 15:33:59) 
[GCC 4.0.1 (Apple Inc. build 5490)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 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.7 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.7 setup.py install --prefix=/home/schliep/test/

which will install Gato in /home/schliep/test/lib/python2.7/site-packages. Just make sure that that directory is on your PYTHONPATH and /home/schliep/test/bin is on your path. Done.