


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.
