Algorithm Animations with XTango

 

XTango [Sta90] is a general-purpose algorithm animation system, developed by John Stasko of Georgia Tech, that helps programmers develop color, real-time animations of their own algorithms and programs. Creating animations of your own implementations is useful both for pedagogical and debugging purposes.    

Included with the XTango distribution is a large collection of animations, several of which are quite interesting and enlightening to watch. The C language source for each animation is included. My favorites include animations of:

• Data structures - including AVL/red-black trees, and binary/Fibonacci heaps.  
• Sorting algorithms - including bubblesort, radixsort, quicksort, and shellsort.  
• Backtracking - including graph coloring, and both the eight-queens and knight's tour problems.  
• Geometric algorithms - including bin packing heuristics and the Graham scan/Jarvis march convex hull algorithms.  
• Graph algorithms - including minimum spanning trees and shortest paths.  
• String algorithms - including the Knuth-Morris-Pratt and Boyer-Moore algorithms.  

Anybody studying these algorithms might well profit from playing with the animations. The source code for the animations contains C language implementations of these algorithms, although of uncertain quality.

XTango is implemented on top of UNIX and X-windows. It is available via anonymous ftp from ftp.cc.gatech.edu in directory pub/people/stasko. Also available there is Polka, a C++ algorithm animation system that is particularly suited to animating parallel computations. POLKA provides its own high-level abstractions to make the creation of animations easier and faster than with many other systems. POLKA also includes an interactive front end called SAMBA that can be used to generate animations from any type of program that can generate ASCII.   

XTango Implementation