Let's begin with an example. Assuming that LINK has been properly installed on your system, you can start it by typing \verb+Link+ at the command line prompt of your operating system (or by double-clicking the appropriate icon). You may now enter commands and start building graphs. This tutorial will give you several examples so that you can get started right away. When you need to learn the system more thoroughly, the later chapters will provide much more detail. Our first example is shown in Figure~\ref{fig:g1}. \begin{figure}[tbh] \input{examples/intro/Userdefine-graph} \caption{Our first graph: the empty graph} \label{fig:define-graph} \end{figure} This example may not be very exciting, but don't worry; things will get more interesting shortly! Even though our graph is not very interesting, there are many things to note about this example. First of all, note that the commands we input are enclosed in parentheses. This is a characteristic of %\begin{figure}[tbh] %\input{examples/intro/Userubingraph} %\caption{Creating an undirected binary graph} %\label{fig:ubingraph} %\end{figure} \begin{figure}[tbh] \input{examples/intro/Useruhypergraph} \caption{Creating an undirected hypergraph} \label{fig:uhypergraph} \end{figure} \begin{figure}[tbh] \input{examples/intro/Usergraph-sum} \caption{Computing the sum of two graphs} \label{fig:graph-sum} \end{figure} Scheme, the computer language used by Link. Scheme is a {\em functional language}. Programs in this type of programming language are generally constructed by {\em composing} functions together rather than by stringing sequences of statments together. To compose two functions means to use the output of one function as input to the other. For example, in Figure~\ref{fig:g1}, the function which creates the graph is {\em graph}, and its output is then passed to the function {\em define} as an argument. The result of the command is that the symbol {\em g} new refers to the newly created graph. There are many other ways to create graphs, but we will describe those later. This example shows the simplest way. \begin{figure}[tbh] \input{examples/intro/Useradd-vertex} \caption{Adding Vertices One by One} \label{fig:add-vertex} \end{figure} A graph without any vertices isn't much fun, so let's add some vertices. Link allows you to name your vertices with integers, symbols, or character strings. The example in Figure~\ref{fig:add-vertex} shows the addition of three vertices, one with each type of name. Of course, it might be quite inconvenient to have to add each vertex individually if we want to build a big graph. One solution to this problem is to use the \verb+add-vertices!+ command shown in Figure~\ref{add-vertices}. \begin{figure}[tbh] \input{examples/intro/Useradd-vertices} \caption{Adding Ranges of Vertices} \label{fig:add-vertices} \end{figure} This command allows you to specify a range of integers, then creates a vertex for each integer in the range. Another solution to this problem, and one which will be the solution to many problems, is to use the Scheme command language. We can write a short program to add our vertices for us. \begin{figure}[tbh] \input{examples/intro/Useradd-vertex-loop} \caption{A Short Program to Add Vertices} \label{fig:add-vertex-loop} \end{figure} This program uses a Scheme {\em do} loop, which will not be described in detail here. There is a tutorial on programming in Scheme in Section~\ref{sec:scheme}. Also, the STk Reference Manual contains more complete information. Now that we have given our graph some vertices, it is time to add edges. An edge is a collection of vertices. The only type of edge we will discuss here has exactly two vertices, and there is no ordering of the vertices. Such an edge is usually drawn as a line connecting the two vertices. Our next task will be to construct some edges from the vertex set. First, we must obtain the vertex set from the graph so that we can pick out the vertices we want for our edges. The vertex set of a graph is returned by the {\em vertices} function. This is shown in Figure~\ref{fig:k4-edges}. The figure also shows the construction of $V \choose 2$, which is a set containing every subset of the vertex set $V$ which has size 2. This set represents all possible lines connecting vertices in our graph. %\begin{figure}[tbh] %\input{examples/intro/} %\caption{Creating Subsets of the Vertex Set} %\label{fig:add-vertex} %\end{figure} %********************WHAT ABOUT THIS? ``About LINK'' in the preface %or at the back of the book?**************************************** %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, it is essential to have a set of libraries %that are efficient, easy to use, robust, and extensible. Second, a %sophisticated GUI and command-line interface are vital for %interaction, visualization, testing, and experimentation. Third, %having a large set of standard algorithms and data structures is %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 its compiler immaturity. % %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. % %By January 1994, the LINKGUI interface had moved from XView code to %Motif, and LINK was working with both the AT\&T and GNU compilers. The %latter was a special challenge since the two compilers process templates %completely differently. Also at this time, the initial implementation %of an attribute manager was completed. From this point, laboratory %support for the project came through LINK's use in applications. By %October 1994 LINK had its first two applications, presenting new %challenges to its design. The applications were an interface to %Mosaic for effective network navigation and a fraud detection project %for the IRS.