Link is intended to be a combinatorial computing environment of unprecedented power, sophistication, extensibility, and robustness. This section describes {\em LINK}'s functionality and the organization of its primary components, including the combinatorial library, graphical user-interface, and functional programming language interface. %............................................................................ \subsubsection{Combinatorial Library} Link is first and foremost a system for manipulating combinatorial objects. In addition to graphs, it will support fundamental combinatorial objects such as hypergraphs, partial orders, strings, permutations, partitions, Young tableaux, and matroids. The interelationships between these different objects makes it advantageous to properly support all of them. \begin{itemize} \item {\em Generators} construct specific instances of particular combinatorial objects such as all permutations of $n$ elements or random unlabeled trees on $n$ nodes with uniform probability. Generator functions will produce specific instances of parameterized graphs such as cycles, wheels, and complete graphs of order $n$, as well as construct graphs from other graphs, such as line graphs and graph products. \item {\em Invariants} report properties of combinatorial objects such as graph arboricity, connectivity, crossing number, chromatic polynomial, girth, or automorphism group. \item {\em Predicates} test an object to see if it satisfies a particular property, such as whether a graph is planar or a partition is graphical. A rich set of predicates is necessary for consistency checking, since the correctness and efficiency of certain graph algorithms hold only for specific classes of graphs. \item {\em Algorithms for augmented objects and data structures} deal with weights, labels, and pointers to other objects associated with an object's components, such as the nodes and edges of a graph. These augmentations are the basis for problems such as network flows or the weighted partitioning of sets. The most efficient combinatorial algorithms can be very challenging to implement, and indeed the asymptotically fastest known algorithms for many important problems have never been implemented. \item {\em Embedders} assign geometric interpretations to the typically geometry-free objects found in combinatorics, including algorithms for minimum genus embeddings or drawings which minimize crossing number. \item {\em Object instance databases} will contain combinatorial configurations with interesting extremal properties that are expensive to compute. These include non-isomorphic graphs up to ten vertices, tournaments, posets, planar graphs, cubic graphs, and many other special combinatorial object instances. \end{itemize} The library will ultimately contain several hundred basic algorithms. %These plans are ambitious, because we intend to implement state-of-the art %algorithms for critical problems such as weighted matching and %multicommodity flow, which are not implemented in existing systems, as well %as a broad base of algorithms for matroids, hypergraphs, partial %orders, and strings which do not exist in current systems. We are using C++ as the primary implementation language for the library. A fundamental strength of our library will be the framework we provide for others to extend the library. The library will also contain basic implementations of mathematical algorithms which, if not strictly combinatorial, will enhance its usefulness through synergy such as linear algebra, mathematical programming, arbitrary precision arithmetic, and statistical analysis. In these areas, we hope to take advantage of the availability of high-quality, non-commercial implementations. We anticipate that most computations done with the library will be performed on a user's machine. However, emerging operating systems will enable users to specify where in a network a computation should take place. Therefore, we will provide parallel implementations of important algorithms for a variety of architectures, perhaps using a machine-independent programming model such as Linda. %............................................................................ \subsubsection{User Interface} A multipurpose extensible user interface is almost as important to the ultimate success of the tool as the quality of the library. We anticipate three distinct types of user interfaces. The first is the command-line interface, which enables applications developed in C, Fortran, Lisp, Mathematica, and Maple to take advantage of the combinatorial library. For people, the primary interfaces will be the interactive graphical user interface (GUI) and the interactive functional language interface (LI). {\bf Graphical User Interface} Beyond a basic interface for manipulating objects, we will have facilities for displaying and editing large graphs, animating algorithms, and managing experiments. Our graphical user interface will be based on X/Motif. The animation interface must provide a strong conceptual model and programming primitives for easily capturing and animating combinatorial events in the tool. This type of domain-specific level of abstraction is lacking in previous animation packages. We will provide primitives to animate basic combinatorial objects and situations. For example, a primitive might specify whether the labels in a graph are changing one at a time, all at once, or according to the pre-order traversal of a spanning tree of the graph. Considerable effort will go into ensuring a symbiotic relationship between the object editor and the algorithm animation support. {\bf Functional-Language Interface} Our experience with computer algebra systems has demonstrated the convenience of an interactive, functional language interface. The same language can be used both for interactive queries, which typically consist of simple calls to the library on specific data, and for composing more sophisticated functions from the library and supplied control structures. Functional languages such as Lisp are extensible, in the sense that user-defined functions are indistinguishable from system functions. Further, list-oriented data structures are a natural representation for discrete structures. We are building our language interface on top of TCL. The critical part about the language interface is that it must be capable of conforming to the user's perspective of the tool. There must be a natural path from an algorithm designed interactively to the algorithm appearing as an efficient new function in the library. %............................................................................ \subsubsection{Documentation and Testing} One major reason for the success of {\em Combinatorica} is its documentation: a published book which contains and describes each line of code in the system, along with hundreds of examples and reference material. The code is designed to be read, for the book represents a literate program. We intend for {\em LINK}'s combinatorial library to be comparable in quality to the best numerical libraries, where quality is a function of efficiency, reliability, and robustness. We will achieve this quality through the techniques of redundant implementation and regression testing. \subsection{Library Functions} \label{appendix-functions} Below are the lists of candidate functions for the library. The lists are intended as representative, not exhaustive. %The functions have been partitioned into %predicates (Figure \ref{predicate-list}), %generators (Figure \ref{generator-list}), %invariants (Figure \ref{invariant-list}), %algorithms (Figure \ref{algorithms-list}), %utility functions (Figure \ref{utility-list}), %and set and hypergraph operations (Figure \ref{set-list}). \begin{figure}[h] \begin{center} {\tiny \begin{tabular}[p]{lllll} BinarySubsets & CartesianProduct & CirculantGraph & CodeToLabeledTree & \\ Compositions & ConstructTableau & Cycle & DeBruijnSequence & \\ Derangements & DistinctPermutations & EmptyGraph & ExactRandomGraph & \\ Factorization & FunctionalGraph & GraphComplement & GraphDifference & \\ GraphIntersection & GraphJoin & GraphPower & GraphProduct & \\ GraphSum & GraphUnion & GrayCode & GridGraph & \\ Harary & Hypercube & IntervalGraph & Josephus & \\ K & KSubsets & LabeledTreeToCode & LexicographicPermutations & \\ LexicographicSubsets & LineGraph & MakeGraph & NextComposition & \\ NextKSubset & NextPartition & NextSubset & NextTableau & \\ NthPair & NthPermutation & NthSubset & Partitions & \\ Path & RandomComposition & RandomGraph & RandomHamiltonianGraph & \\ RandomHeap & RandomKConnGraph & RandomKEdgeConnGraph & RandomKSubset & \\ RandomPartition & RandomPermutation & RandomPlanarGraph & RandomPoset & \\ RandomRegularGraph & RandomSubset & RandomTableau & RandomTree & \\ RealizeDegreeSequence & RegularGraph & Star & Strings & \\ Subsets & Tableaux & TableauxToPermutation & Turan & \\ Wheel & & & & \end{tabular} \caption{Generators for Graphs and Other Combinatorial Objects. \label{generator-list}} } \end{center} \end{figure} \begin{figure}[h] \begin{center} {\tiny \begin{tabular}[p]{lllll} AchromaticNumber & AcyclicOrientation & AllLinearExtensions & AllSpanningTrees & \\ Arboricity & ArticulationVertices & Automorphisms & Bandwidth & \\ BasisMatrix & BettiNumber & Bicomponents & BindingNumber & \\ Biparticity & BookNumber & Bridges & Cage & \\ ChromaticIndex & ChromaticNumber & ChromaticPolynomial & CircleModel & \\ CircularArcModel & Circulation & Circumference & CliqueCover & \\ CliqueNumber & Coarseness & Cofactor & Condensation & \\ ConductanceMatrix & ConnectedComponents & Converse & CoveringNumber & \\ CriticalGraph & CrossingNumber & CutSet & CutVertices & \\ CycleNumber & DegreeSequence & Diameter & DirectedDiameter & \\ DistanceMatrix & DominatingSet & DualGraph & DurfeeSquare & \\ EarDecomposition & Eccentricity & EdgeAboricity & EdgeColoring & \\ EdgeConnectivity & EdgeIndependenceNumber & EdgeInducedSubgraph & EdgeIntegrity & \\ EdgeTransitive & EquivalenceClasses & EulerianCycle & EulerianOrientation & \\ Eulericity & FFactor & FMatching & FaceChromaticNumber & \\ FerrersDiagram & FindCycle & Genus & Girth & \\ GracefulLabeling & GraphCenter & GraphComposition & GraphMinor & \\ HamiltonianCycle & Homomorphism & IncidenceMatrix & IndependenceNumber & \\ Index & InducedSubgraphIsomorphism & IntersectionNumber & IntervalModel & \\ InversePermutation & Inversions & Isomorphism & KColoring & \\ KEdgeDisjointSpanningTrees & LargestEigenvalue & LongestIncreasingSubsequence & M & \\ MatchingNumber & MaxDegree & MaximalMatching & MaximumAntichain & \\ MaximumClique & MaximumIndependentSet & MaximumSpanningTree & MinDegree & \\ MinEdgeCut & MinVertexCut & MinimumChainPartition & MinimumChangePermutations & \\ MinimumSpanningTree & MinimumVertexCover & Minor & MultiplicationTable & \\ NeighborSet & NumberOfSpanningTrees & OrientGraph & PackingNumber & \\ PathNumber & PerfectEliminationOrdering & Permute & PlanarSeparator & \\ PosetDimension & ProperEdgeColoring & ProperFaceColoring & ProperVertexColoring & \\ Radius & RamseyNumbers & RankPermutation & RankSubset & \\ RectilinearCrossingNumber & Runs & SecondLargestEigenvalue & SignaturePermutation & \\ SmallSeparator & Spectrum & StableMarriage & StronglyConnectedComponents & \\ SubgraphIsomorphism & TableauClasses & Thickness & TotalChromaticNumber & \\ TotalGraph & Toughness & TransitiveClosure & TransitiveReduction & \\ TransposePartition & TriangulatePlanarGraph & TwoColoring & V & \\ VertexArboricity & VertexColoring & VertexConnectivity & VertexIntegrity & \\ WeaklyConnectedComponents & & & & \end{tabular} \caption{Invariants for Graphs and Other Combinatorial Objects. \label{invariant-list}} } \end{center} \end{figure} \begin{figure}[h] \begin{center} {\tiny \begin{tabular}[p]{lllll} AllSpanningTreesRootedAtx & Backtrack & BinarySearch & BreadthFirstTraversal & \\ ChinesePostman & CircularVertices & ConvexEmbedding & ConvexHull & \\ CrossingMinimal & DelaunayTriangulation & DepthFirstTraversal & Dicomponents & \\ DilateVertices & DirectedEdgeConn & DirectedVertexConn & EuclideanDistMatrix & \\ EuclideanTSP & GridPlanarEmbedding & HasseDiagram & InDegreeList & \\ InNeighborSet & KArcDisjointSpanningTrees & KruskalSpanningTree & MaxFlow & \\ MaximumCut & MinimumCostFlow & MinimumWeightMatching & MinimumWeightPerfectMatching & \\ MininumWeightFactor & NearestNeighbors & NormalizeVertices & NumberCrossings & \\ OutDegreeList & OutNeighborSet & PlanarEmbedding & PrimSpanningTree & \\ RadialEmbedding & RandomVertices & RankedEmbedding & RootedEmbedding & \\ RotateVertices & STNumbering & SchnyderEmbedding & ShakeGraph & \\ ShortestCycle & ShortestPath & SpanningTreesRootedAtX & SpringEmbedding & \\ TranslateVertices & & & & \end{tabular} \caption{Network and Embedding Algorithms. \label{algorithms-list}} } \end{center} \end{figure} \begin{figure}[h] \begin{center} {\tiny \begin{tabular}[p]{lllll} AddEdge & AddRandomEdges & AddRandomVertices & AddVertex & \\ CatalanNumber & ChangeEdges & ChangeVertices & Contract & \\ CutAndPaste & DeleteCycle & DeleteEdge & DeleteFromTableau & \\ DeleteVertex & Distribution & Edges & ExpandGraph & \\ FromAdjacencyLists & FromCycles & FromInversionVector & FromOrderedPairs & \\ FromUnorderedPairs & HeapSort & InduceSubgraph & InsertIntoTableau & \\ MakeSimple & MakeUndirected & NumberOfCompositions & NumberOfDerangements & \\ NumberOfInvolutions & NumberOfPartitions & NumberOfPermutationsByCycles & NumberOfSpanningTrees & \\ NumberOfTableaux & Permute & Polya & RandomGraphOnEdges & \\ ReadAdjacencyList & ReadAdjacencyMatrix & ReadEdgeList & ReadGraph & \\ ReadIncidenceList & ReadStandardFormatGraph & RemoveSelfLoops & RotateVertices & \\ SelectionSort & ShowGraph & ShowLabeledGraph & StirlingFirst & \\ StirlingSecond & SubdivideEdge & SubdivideGraph & ToAdjacencyLists & \\ ToCycles & ToInversionVector & ToOrderedPairs & ToUnorderedPairs & \\ Vertices & WriteGraph & WritePostscriptGraph & & \end{tabular} \caption{Utility Functions for Graphs and Other Combinatorial Objects. \label{utility-list}} } \end{center} \end{figure}