# The Stony Brook Algorithm Repository

## Xtango and Polka Algorithm Animation Systems

XTANGO is a general purpose algorithm animation system, developed by John Stasko of Georgia Tech, that supports programmers developing color, real-time, 2 & 1/2 dimensional, smooth animations of their own algorithms and programs. The focus of the system is on ease-of-use. XTANGO utilizes the path-transition animation paradigm which helps move animation design to an abstract, high level. Programmers need not be graphics experts to develop their own animations.

XTANGO is implemented on top of UNIX and the X11 Window System. It can be run on either color or black-and-white monitors. XTANGO is available for use via anonymous ftp from ftp.cc.gatech.edu in directory pub/people/stasko.

Included with the XTANGO distribution is a large collection of animations. Several of which are quite fun to watch. My favorites include:

• AVL trees (avl)

• Binomial heaps (binoheap)

• Boyer-Moore string matching (boyer)

• Bin Packing (bpack)

• Bubble sort (bsort)

• Convex Hull (conhull)

• Fast Fourier Transform (fft)

• Fibonacci heaps (fiboheap)

• Heapsort (heap)

• Knight's tour (knight)

• K-selection (ksel)

• Eight Queens (queens)

• Quicksort (quicksort)

• Treaps (treap)

The basic process of animation consists of implementing the algorithm in C (another language can be used, but it must just produce a trace file which is read by a C program driver) and then deciding on the important events to be portrayed during the execution of the algorithm. These events then activate animation routines implemented in a separate file using the XTANGO animation package to create and manipulate objects (circles, squares, lines, and so on). Transitions on objects include movement, color change, resizing, and filling, as well as others. For example, the animation for binary search consists of a series of rectangles, each representaing one of the elements being searched. A bouncing circle hits the current dividing element, which changes color. The ball then bounces to the next dividing element and continues to do this until the desired element has been found. To learn more about XTANGO, see the September 1990 issue of IEEE Computer which has an article about the TANGO system, a ancestor of XTANGO.

POLKA is a general purpose animation system that is particularly well-suited to building animations of programs, algorithms and computations, especially parallel computations. POLKA supports color, real-time, 2 & 1/2 dimensional, smooth animations. The focus of the system is on a balance of power and ease-of-use. POLKA provides its own high-level abstractions to make the creation of animations easier and faster than with many other systems. Programmers need not be graphics experts to develop their own animations. POLKA also includes a hot new interactive front-end called SAMBA that can be used to generate animations from any type of program that can generate ASCII.

POLKA is implemented in C++ on top of UNIX and the X11 Window System, and it requires the Motif or Athena widget set. (Because it supports Athena widgets, if you're running Linux, you should be able to get Polka to build there.) It can be run on either color (much better) or black-and-white monitors. POLKA is available for use via anonymous ftp from ftp.cc.gatech.edu under pub/people/stasko.

 ` ` Dictionaries (4) ` ` Sorting (4) ` ` Convex Hull (3) ` ` Discrete Fourier Transform (3) ` ` Hamiltonian Cycle (3) ` ` Median and Selection (3) ` ` Minimum Spanning Tree (3) ` ` Priority Queues (3) ` ` Shortest Path (3) ` ` Vertex Coloring (3) ` ` Bin Packing (2) ` ` Connected Components (2) ` ` Matrix Multiplication (2) ` ` Random Number Generation (2) ` ` String Matching (2) ` ` Topological Sorting (2) ` ` Traveling Salesman Problem (2) ` ` Finite State Machine Minimization (1) ` ` Intersection Detection (1)