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.
_______________________________________________
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
