Winfried Hochstaettler, from the FernUniversität Hagen in Germany, and
been working for quite some time on Gato, the Graph Animation Toolbox,
the Combinatorial Algorithm Toolbox, which is an interactive course in
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,
and dowloadlinks at http://schliep.org/CATBox.
Gato itself is LGPL licensed; the book and the algorithm
implementations used are copyright
Gato and CATBox has been used in university classrooms for several years
by colleagues on several continents at the later undergraduate/early
level. We would be particularly interested in collaborating with high
level undergrad faculty.
Graph algorithms are easy to visualize and indeed there already exists a
variety of packages and programs to animate the dynamics when solving
from graph theory. Still, and somewhat surprisingly, it can be
understand the ideas behind the algorithm from the dynamic display
CATBox consists of a software system for animating graph algorithms
course book which we developed simultaneously. The software system
both the algorithm and the graph and puts the user always in control
actual code that is executed. He or she can set breakpoints, proceed
steps and trace into subroutines. The graph, and additional auxiliary
like residual networks, are displayed and provide visual feedback. The
book, intended for readers at advanced undergraduate or graduate level,
introduces the ideas and discusses the mathematical background
understanding and verifying the correctness of the algorithms and their
complexity. Computer exercises and examples replace the usual static
For this volume we have chosen solely algorithms for classical
combinatorial optimization, such as minimum spanning trees, shortest
maximum flows, minimum cost flows as well as weighted and unweighted
both for bipartite and non-bipartite graphs.
We consider non-bipartite weighted matching, in particular in the
case, a highlight of combinatorial optimization. In order to enable
to fully enjoy the beauty of the primal-dual solution algorithm for
matching, we present all mathematical material not only from the point
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.
Edu-sig mailing list
[hidden email] http://mail.python.org/mailman/listinfo/edu-sig