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 [4,14,9].
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.
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 [12], Nate Dean was largely responsible for the package NETPAD at Bellcore [10] , Steve Skiena at State University at New York at Stony Brook had produced Combinatorica on top of Mathematica [13], and Mark Goldberg and his students at Rensselaer Polytechnic Institute had implemented SetPlayer [1]. 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 Collectionhierarchy and co-designer
of the Graphhierarchy, 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
berryj@dimacs.rutgers.edu
email address will still be valid.