\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}