
Over the last 10 years there have been numerous attempts to develop
software for discrete mathematics that would benefit pure research,
application-driven research, and/or pedagogic concerns.  This software
has focused on combinatorics, graph theory, computational geometry, or
some combination of these areas.
However, each package has had shortcomings which has prevented it from
becoming a generally useful tool.  Some packages are too specialized,
some are not robust, some are inefficient, and some are hard to
learn. Nevertheless, the fact that these systems continue to be
designed in spite of previous efforts indicates that there is a real
need for a comprehensive and robust system which can serve a variety
of users, from applications to research, to education.  The magnitude
of such a project exceeds the efforts made so far by the researchers
and research groups responsible for the existing systems.  A good
discussion of software packages for discrete math is found
in \cite{DeanS92,TIT93,MeN95}.
% Combinatorial Support for Discrete Mathematics, ed. by N. Dean and
% G. Shannon  (AMS 1994)

From the standpoint of a theoretician or an applications researcher,
there are several features which characterize a useful software tool
for their work.  First of all, it is essential to have a set of libraries
that are efficient, easy to use, robust, and extensible.  Secondly, a
sophisticated GUI and command-line interface are vital for
interaction, visualization, testing, and experimentation.  
Having a large set of standard algorithms and data structures is
also important.  Educators trying to produce the next generation of
researchers would also find all of these features very useful.  But
even with the improvements in object-oriented design and GUI
technology these goals present an enormous challenge.  The LINK
project is an attempt to balance the trade-offs inherent in these
varied goals and produce a usable and reliable tool for theorists,
applied researchers and educators.
 
%This document is an overview of the history and structure of the LINK
%software system.  It is intended to provide a general introduction to
%LINK and its applications.  Specific details about the system are
%available in the LINK User Guide and Programmers Reference Manual
%(forthcoming).  The remainder of this section discusses the history
%and motivation of the LINK project.  In section 2, we discuss the
%organization of LINK.  Section 3 presents the libraries that make up
%LINK.  In section 4, the process of creating a LINK application is
%described along with several current applications.  Finally, we
%discuss future work and present our conclusions in sections 5 and 6.
%
%\subsection{History and Motiviation}

In July 1991, four researchers met at the SIAM conference for Applied
Mathematics in Washington D.C.  and discussed the possibility of
creating a large software package for discrete mathematics.  Each had
already directed similar projects.  Greg Shannon of Indiana University
had organized the development of GraphLab \cite{SMF90}, Nate Dean was
largely responsible for the package NETPAD at Bellcore \cite{MDM90} ,
Steve Skiena at State University at New York at Stony Brook had
produced Combinatorica on top of Mathematica \cite{Ski90}, and Mark
Goldberg and his students at Rensselaer Polytechnic Institute had
implemented SetPlayer \cite{BCGR92}.  Though these packages have many
useful features, some overlapping and some not, none was complete or
without significant drawbacks depending on the user and the
application.  These researchers wanted a more comprehensive package
that would add new features and retain the positive aspects of their
previous efforts.  They wanted a package that could easily be used for
intensive research and applications, and yet have the capability to be
used for pedagogic purposes.  There would be numerous tradeoffs in
trying to satisfy these somewhat competing goals.  The hope was that
they could find a satisfactory balance that would fulfill each of
these goals in turn.

Later that year and into the next they, along with their students, did
further research and wrote a proposal for a research grant to develop
such a package.  The grant stipulated that they would receive
organizational support from DIMACS (Center for Discrete Mathematics
and Theoretical Computer Science).  The late Daniel Gorenstein joined
the project as the principal investigator with co-PI's Nate Dean, Mark
Goldberg, Greg Shannon and Steve Skiena.

Independently, at Los Alamos National Laboratory (LANL) there were
several projects where such a package would be of considerable use,
and researchers and programmers at LANL began implementing many
components similar to software that the PI's had developed.  Mark
Goldberg was on sabbatical at LANL and was involved in one of these
projects.  He and the other PI's convinced Vance Faber (the group
leader of CIC-3, the Computer Research and Applications Group of the
Communications, Information, and Computing Division) that a more
general tool would better fulfill the needs of these and similar
projects at LANL.  The grant was accepted by the National Science
Foundation in the fall of 1992, and CIC-3 provided staff support and
development resources in the form of support for the PIs' students to
work on the project at LANL.  In addition, Greg Shannon took a leave
of absence from IU and worked on LINK at LANL as a contractor.

Initial work on LINK began with meetings in December 1992 between
representatives from Indiana University, RPI, Stony Brook and LANL.
Many months were spent in designing the graph hierarchy, and how that
hierarchy would be represented to the user, and in the implementation
of basic data structure classes.  Algorithms were implemented using
these designs in order to test the ease of programming and the
efficiency of the design.  Much time was spent dealing with the
intricacies of C++ and the immaturity of the compilers available at
that time.

In the summer of 1993, students from all the representative
institutions worked together with staff from LANL at Los Alamos.
During this time, the current \Graph\ and \Collection\ hierarchies were
developed and much of the work on the Tcl interface was done.  This
command-line interface provided a means of testing the various
generators, layouts and algorithms that had been implemented during
the spring and summer months.

In November, 1994, Dr. Jonathan Berry, a student of Mark Goldberg's
at the time and the designer of the \Collection hierarchy and co-designer
of the \Graph hierarchy, took over as project coordinator.  Plans were
made for Dr. Berry to spend a year at DIMACS reworking the LINK 
interface to be more friendly to students and researchers and preparing
the system for its initial July, 1996 release.  Dr. Berry will remain
project coordinator and primary contact for matters concerning the
LINK system at Elon College in North Carolina, though the
\verb+berryj@dimacs.rutgers.edu+ email address will still be valid.
