
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}

