\section{Related work}\label{sec:related_work}

\input{Y_other_animations}

One general purpose animation program is ANIMAL~\cite{2002-JVLC-Roessling,ANIMAL};
it provides the animator
with a rich menu
of elements common to many algorithms.
Steps in the animation are linked to steps in the pseudocode, a feature that
appears to be unique for Animal.
Though there is a large variety of options for creating interesting and
compelling animations,
it appears that the animations produced by the animator are passive.

Galles~\cite{Galles} is an animation tool with very
sophisticated creation options.
Primarily designed to be passive, it could conceivably, with a parser
for a graph input format and a mechanism to allow the user to view and
manipulate the input graph, be made interactive.
It suffers, however, from the fact that the
animator must navigate a complex Java-based interface with multiple classes.

Although secondary to its main purpose as a library of data structures and
algorithms,
LEDA~\cite{1999-LEDA-Mehlhorn} offers a graph window facility that can be
used to create animations of graph algorithms.
The documentation gives several examples and illustrates the rich functionality of
the drawing and visualization capability of graph windows.
Since LEDA is a general purpose, C++-based, programming language for
algorithms and data structures, it is easily augmented with extensions that
are integrated seamlessly with the core API; in this case, graph windows work
in concert with core graph functions and macros.
%%  (which are similar to, but
%% more sophisticated than, those in GDR).
Two major disadvantages of LEDA are (a)~it is a commercial product with
non-trivial licensing cost; and (b)~the windowing
system, at least in the last cost-free version, is based on X11 and hence not
portable.

Several online applets feature graph algorithm animation. Of these,
JAVENGA~\cite{JAVENGA} stands out. It is highly interactive. The drawing and
editing of
graphs is simple and intuitive, and graphs can be viewed in all three major
representations (drawing, adjacency matrix and adjacency list).
The variety of graph algorithms available is impressive:
breadth-first and depth-first search, topological sort, strongly connected
components, four shortest path algorithms, two minimum spanning tree
algorithms, and a network flows algorithm.
Animations can be run one step at a time with the option of moving backwards
or continuously with an adjustable number of milliseconds per step.
Javenga's main drawback is that the explorer is unable to save graphs for
future sessions, presumably an artifact of it being an applet.

The tool that probably comes closest to Galant is j-Alg~\cite{j-Alg};
it is highly interactive, has a relatively easy to use interface, and has sophisticated animations for a large variety of algorithms,
including \cmt{give partial list}.
In many ways its functionality, look and feel, and variety of animations
already implemented it far surpasses Galant in its current form.
The only drawback is that there is no readily available mechanism
for creating new animations.
New animations are typically developed as
student projects and require a fair amount of effort --- not surprising given
the sophistication of the results.

\cmt{Appears that there are several passive animation tool with sophisticated
creation mechanism --- almost like movie production.}

\cmt{Need to mention interactive Java Applets; they don't seem to work on my
  Mac -- must have at some point on the previous Mac}

AlgoViz~\cite{AlgoViz}
is a large catalog of algorithm animations, continually updated by
contributors who either submit new animations or comment on existing ones.
The animations listed are rated with respect to four categories:
lecture aid (roughly corresponding to passive), self study supplement (passive with
easy to use interface),
stand-alone (interactive),
and debugging aid (creative in a limited sense).
The perspective of most of the entries is classroom use with the role of the
animator implicit.
For example, several different animations constructed using Galles are posted.
Like any large repository with many contributors, AlgoViz is difficult to
monitor and
maintain: comments on the animations are not necessarily useful and some of the links are broken.


The OpenDSA project~\cite{%
2011-ProgramVisualization-Shaffer,2011-Koli-Shaffer,2012-SIGCSE-Fouh%
}
aims to create a textbook compilation of a variety of
(mostly passive) visualizations.

Earlier animation tools/systems include John Stasko's Xtango~\cite{Xtango},
SAMBA~\cite{SAMBA} and Polka~\cite{Polka,1992-TR_GIT-Stasko}, and, of course,
that of but
Bentley and Kernighan~\cite{1987-Animation-Bentley}.
SAMBA is especially notable for its emphasis on simplifying the creation of
animations so that students can easily accomplish it.
All of these suffer, however, from using old technology, requiring off-line creation
of problem instances and having no graph-algorithm specific implementations
or graph creation interfaces to offer.

% [Last modified: 2013 06 26 at 18:34:44 GMT]
