\subsection{Algorithm Specifications}\index{Algorithm!Specifications}

\vspace*{1in}

The following list enumerates the algorithms which are currently callable
from the GUI interface, and those which we anticipate will be included in
the July 31st relase of the system.  The algorithm animations may be called 
and viewed, as in any animation system, but the results (in the form of
the return value and any attributes set) can be obtained for further use
in the Scheme interface.  For example, selecting {\em Kruskal} from
the {\em Algorithm} menu runs Kruskal's minimum spanning tree animation,
but the return value can be saved and used by calling the same algorithm from 
the command-line interface (see the User's Manual on Page~\pageref{part:users-manual}).  For example, a command to bring up a the spanning tree of a graph
$g$ is:
\begin{verbatim}
          (show-labeled-graph (graph (vertices g) (kruskal g))).
\end{verbatim}

Each algorithm below is listed by its Scheme command name (and alias if
appropriate).  The return values can be retrieved by calling the 
algorithms from Scheme (as above), and the values of the attributes
set by algorithms can also be retrieved using Scheme.  See the User's
Manual for a discussion of this (NOT WRITTEN YET 7/19/96).  It would
be straightforward to incorporate the retrieval and setting of all 
fundamental attributes through the graph menu, but this has not been
done for all of them yet.  However, color, vertex size, edge width,
and vertex and edge labels {\em are} easily changed from the GUI
interface.

\subsubsection{Searches and Sorts}

\begin{flushleft}

\begin{tabular}{|l|l|}   \hline
command name & depth-first-search \\ \hline
alias 	     & dfs \\ \hline
status 	     & in use, animated \\ \hline
input 	     & $<$graph*$>$ \\ \hline
output 	     & Sequence$<$Vertex*$>$ \\ \hline
attributes used & starttime \\ 
                & finishtime \\
                & back \\ 
                & low \\ 
                & pred \\ \hline
attributes set  & starttime \\ 
                & finishtime \\
                & back \\ 
                & low \\
                & pred \\ \hline
\end{tabular}

\vspace*{4mm}

\begin{tabular}{|l|l|}   \hline
command name & topological-sort \\ \hline
alias & 			\\ \hline
status 	     & in use, animated \\ \hline
input 	     & directed, acyclic graph \\ \hline
output 	     & Sequence$<$Vertex*$>$ \\ \hline
attributes used & finishtime \\ \hline
attributes set & \\ \hline
\end{tabular}

\vspace*{4mm}

\begin{tabular}{|l|l|}   \hline
command name & breadth-first-search \\ \hline
alias 	     & bfs \\ \hline
status 	     & in use, animated \\ \hline
input 	     & $<$graph*$>$ \\ \hline
output 	     & Sequence$<$Vertex*$>$ \\ \hline
attributes used & starttime \\ 
                & finishtime \\
                & pred \\ \hline
attributes set  & starttime \\
                & finishtime \\ 
                & pred \\ \hline
\end{tabular}

\vspace*{4mm}

\subsubsection{Components}

\begin{tabular}{|l|l|}   \hline
command name & strongly-connected-components \\ \hline
alias 	     & scc \\ \hline
status 	     & in use, component layout exists \\ \hline
input 	     & directed graph \\ \hline
output 	     & Set$<$Set$<$Vertex*$> >$ \\ \hline
attributes used & finishtime \\
                & pred \\ \hline
attributes set  & 	\\ \hline
\end{tabular}

\vspace*{4mm}

\begin{tabular}{|l|l|}   \hline
command name & biconnected-components \\ \hline
alias 	     & bcc \\ \hline
status 	     & under construction\\ \hline
input 	     & undirected graph \\ \hline
output 	     & Set$<$Set$<$Vertex*$> >$ \\ \hline
attributes used & low \\ \hline
                & starttime \\ \hline
attributes set  & 	\\ \hline
\end{tabular}

\vspace*{4mm}

\subsubsection{Shortest Paths}

\begin{tabular}{|l|l|}   \hline
command name & dijkstra     \\ \hline
alias 	     &              \\ \hline
status 	     & under construction\\ \hline
input 	     & $<$graph*$>$ \\ \hline
output 	     & Sequence$<$double$>$ \\ \hline
attributes used & weight       \\ 
                & distance \\ 
                & pred \\ \hline
attributes set & weight       \\ 
                & distance \\ \hline
\end{tabular}

\vspace*{4mm}

\begin{tabular}{|l|l|}   \hline
command name & floyd-warshall     \\ \hline
alias 	     &              \\ \hline
status 	     & in use, not animated\\ \hline
input 	     & $<$graph*$>$ \\ \hline
output 	     & Sequence$<$double$>$ \\ \hline
attributes used & weight       \\ 
                & distance \\ 
                & pred \\ \hline
attributes set & weight       \\ 
                & distance \\ \hline
\end{tabular}

\vspace*{4mm}

\subsubsection{Minimum Spanning Tree}

\begin{tabular}{|l|l|}   \hline
command name & kruskal     \\ \hline
alias 	     &              \\ \hline
status 	     & in use, animated\\ \hline
input 	     & $<$graph*$>$ \\ \hline
output 	     & Set$<$Edge*$>$ \\ \hline
attributes used & weight       \\ 
                & mark \\ 
                & DJSet (disjoint set) \\ \hline
attributes set & DJSet       \\ 
                & mark (indicates tree edge) \\ \hline
\end{tabular}

\vspace*{4mm}

\begin{tabular}{|l|l|}   \hline
command name & prim     \\ \hline
alias 	     &              \\ \hline
status 	     & under construction\\ \hline
input 	     & $<$graph*$>$ \\ \hline
output 	     & Set$<$Edge*$>$ \\ \hline
attributes used & weight       \\ 
                & key \\ 
                & pred (disjoint set) \\ \hline
attributes set & pred       \\ \hline
\end{tabular}

\vspace*{4mm}

\subsubsection{Network Flows and Matching}

\begin{tabular}{|l|l|}   \hline
command name & ford-fulkerson     \\ \hline
alias 	     &              \\ \hline
status 	     & drawing board \\ \hline
input 	     & directed graph, source, sink \\ \hline
output 	     & double (the maximum flow)\\ \hline
attributes used & flow       \\ 
                & capacity \\ 
                & partition (disjoint set) \\ \hline
attributes set & flow       \\ 
                & capacity \\ 
                & partition (disjoint set) \\ \hline
\end{tabular}

\vspace*{4mm}

\begin{tabular}{|l|l|}   \hline
command name & goldberg-tarjan     \\ \hline
alias 	     &              \\ \hline
status 	     & implemented, but not available yet \\ \hline
input 	     & directed graph, source, sink \\ \hline
output 	     & double (the maximum flow)\\ \hline
attributes used & flow       \\ 
                & capacity \\ 
                & partition (disjoint set) \\ \hline
attributes set & flow       \\ 
                & capacity \\ 
                & partition (disjoint set) \\ \hline
\end{tabular}

\vspace*{4mm}

\begin{tabular}{|l|l|}   \hline
command name & bipartite-matching     \\ \hline
alias 	     &              \\ \hline
status 	     & drawing board, (but simply calls flow alg.)\\ \hline
input 	     & $<$graph*$>$ \\ \hline
output 	     & Set$<$Edge*$>$ \\ \hline
attributes used & flow       \\ 
                & capacity \\ 
                & mark \\ \hline
attributes set & flow       \\ 
                & capacity \\ 
                & mark (indicates matching edge) \\ \hline
\end{tabular}

\end{flushleft}
