[Edu-sig] Announcement: Gato & CATBox

[Alexander Schliep]

Hello everyone,

Winfried Hochstaettler, from the FernUniversität Hagen in Germany, and  
myself have
been working for quite some time on Gato, the Graph Animation Toolbox,  
and CATBox,
the Combinatorial Algorithm Toolbox, which is an interactive course in  
combinatorial
optimization published by Springer Verlag.

Gato and the algorithms itself are all written in Python and the  
algorithm animation is
provided through animated data structures. There is more information,  
screencasts
and dowloadlinks at http://schliep.org/CATBox.

Gato itself is LGPL licensed; the book and the algorithm  
implementations used are copyright
Springer.

Gato and CATBox has been used in university classrooms for several years
by colleagues on several continents at the later undergraduate/early  
graduate
level. We would be particularly interested in collaborating with high  
school/lower
level undergrad faculty.

Screencast:  http://biomaps.rutgers.edu/~schliep//CATBox/Dijkstra.swf

Best,
Alexander


A longer blurb about CATBox:

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 as well as 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.