\contentsline {part}{\uppercase {i}\hspace {1em}Getting Started with Link}{8}
\contentsline {section}{\numberline {1}Initial Remark}{8}
\contentsline {section}{\numberline {2}Forward}{8}
\contentsline {section}{\numberline {3}Downloading the System}{8}
\contentsline {subsection}{\numberline {0.1}Getting Link}{8}
\contentsline {subsection}{\numberline {0.2}Installing Link}{9}
\contentsline {subsection}{\numberline {0.3}Mailing List}{9}
\contentsline {section}{\numberline {1}Introduction}{10}
\contentsline {part}{\uppercase {ii}\hspace {1em}Graphical User Interface}{11}
\contentsline {section}{\numberline {1}General}{12}
\contentsline {section}{\numberline {2}Graph Creation, Copying, and File Operations}{12}
\contentsline {subsection}{\numberline {2.1}Defining Graphs}{12}
\contentsline {subsubsection}{\numberline {2.1.1}Graph Creation and Copying}{12}
\contentsline {subsection}{\numberline {2.2}Loading and Saving Graphs}{13}
\contentsline {section}{\numberline {3}Graph Editing}{13}
\contentsline {subsection}{\numberline {3.1}Creating Vertices and Edges}{13}
\contentsline {subsection}{\numberline {3.2}Moving Vertices and Edges}{13}
\contentsline {subsection}{\numberline {3.3}Selecting Vertices and Edges}{14}
\contentsline {subsection}{\numberline {3.4}Deleting Vertices and Edges}{14}
\contentsline {subsection}{\numberline {3.5}Changing Attributes}{14}
\contentsline {section}{\numberline {4}Graph Layout}{14}
\contentsline {subsection}{\numberline {4.1}Layout of Graphs}{14}
\contentsline {section}{\numberline {5}Graph Algorithms}{15}
\contentsline {subsection}{\numberline {5.1}Algorithm Specifications}{15}
\contentsline {subsubsection}{\numberline {5.1.1}Searches and Sorts}{16}
\contentsline {subsubsection}{\numberline {5.1.2}Components}{17}
\contentsline {subsubsection}{\numberline {5.1.3}Shortest Paths}{17}
\contentsline {subsubsection}{\numberline {5.1.4}Minimum Spanning Tree}{18}
\contentsline {subsubsection}{\numberline {5.1.5}Network Flows and Matching}{19}
\contentsline {section}{\numberline {6}Graph Operations}{19}
\contentsline {subsection}{\numberline {6.1}Graph Operations}{19}
\contentsline {subsection}{\numberline {6.2}Unary Operations}{19}
\contentsline {subsubsection}{\numberline {6.2.1}Binary Operations}{20}
\contentsline {part}{\uppercase {iii}\hspace {1em}User's Manual}{21}
\contentsline {section}{\numberline {7}Introduction}{22}
\contentsline {section}{\numberline {8}Basic Objects}{23}
\contentsline {subsection}{\numberline {8.1}{\em Collections}}{26}
\contentsline {subsection}{\numberline {8.2}Typed Vectors}{29}
\contentsline {subsection}{\numberline {8.3}Typed Lists}{41}
\contentsline {section}{\numberline {9}Graph Objects}{42}
\contentsline {subsection}{\numberline {9.1}{\em Graphs}}{42}
\contentsline {subsubsection}{\numberline {9.1.1}Graph Creation}{42}
\contentsline {subsubsection}{\numberline {9.1.2}Graph Modification}{44}
\contentsline {subsubsection}{\numberline {9.1.3}Graph Information}{44}
\contentsline {subsubsection}{\numberline {9.1.4}Graph Vertex Information}{45}
\contentsline {subsubsection}{\numberline {9.1.5}Graph Queries}{46}
\contentsline {subsection}{\numberline {9.2}Graph Views}{47}
\contentsline {subsection}{\numberline {9.3}Vertex Graphics}{52}
\contentsline {subsection}{\numberline {9.4}Edge Graphics}{54}
\contentsline {part}{\uppercase {iv}\hspace {1em}Programmer's Manual}{59}
\contentsline {section}{\numberline {10}Compiling LINK Programs}{60}
\contentsline {section}{\numberline {2}Extending the System}{60}
\contentsline {subsection}{\numberline {2.1}The Makefile}{60}
\contentsline {subsection}{\numberline {2.2}Adding a Menu Option}{61}
\contentsline {subsection}{\numberline {2.3}An Example Wrapper}{63}
\contentsline {section}{\numberline {3}Algorithms}{63}
\contentsline {subsection}{\numberline {3.1}Algorithm Specifications}{64}
\contentsline {section}{\numberline {4}Basic Objects}{65}
\contentsline {section}{\numberline {2}{\em Containers}}{65}
\contentsline {subsection}{\numberline {2.1}Adding New {\em Containers}}{65}
\contentsline {subsection}{\numberline {2.2}Iterators}{68}
\contentsline {subsubsection}{\numberline {2.2.1}{\em ContainerNode}}{68}
\contentsline {subsection}{\numberline {2.3}{\em List}}{70}
\contentsline {subsection}{\numberline {2.4}{\em SortedList}}{74}
\contentsline {subsection}{\numberline {2.5}{\em DList}}{78}
\contentsline {subsection}{\numberline {2.6}{\em Deque}}{82}
\contentsline {subsubsection}{\numberline {2.6.1}{\em Queue}}{83}
\contentsline {subsubsection}{\numberline {2.6.2}Stack}{84}
\contentsline {subsection}{\numberline {2.7}Arrays}{86}
\contentsline {subsection}{\numberline {2.8}{\em SortedArray}}{89}
\contentsline {subsection}{\numberline {2.9}Priority Queue Dictionary Structures}{93}
\contentsline {subsubsection}{\numberline {2.9.1}{\em BinaryHeap}}{93}
\contentsline {subsubsection}{\numberline {2.9.2}{\em BinomialHeap}}{96}
\contentsline {subsection}{\numberline {2.10}General Dictionary Structures}{99}
\contentsline {section}{\numberline {3}{\em Collections}}{102}
\contentsline {subsection}{\numberline {3.1}Discussion}{102}
\contentsline {subsubsection}{\numberline {3.1.1}Organization}{102}
\contentsline {subsubsection}{\numberline {3.1.2}Reference Counting}{103}
\contentsline {subsubsection}{\numberline {3.1.3}Comparisons}{105}
\contentsline {subsubsection}{\numberline {3.1.4}Set Primitive Operations}{105}
\contentsline {subsubsection}{\numberline {3.1.5}Interface}{111}
\contentsline {subsection}{\numberline {3.2}{\em MSetBase}\ and {\em MSet}}{114}
\contentsline {subsection}{\numberline {3.3}{\em SetBase}\ and {\em Set}}{121}
\contentsline {subsection}{\numberline {3.4}{\em SequenceBase}\ and {\em Sequence}}{122}
\contentsline {section}{\numberline {4}Combinatorial Objects}{126}
\contentsline {subsection}{\numberline {4.1}Commonalities Among Combinatorial Objects}{126}
\contentsline {subsection}{\numberline {4.2}Permutations}{126}
\contentsline {section}{\numberline {5}Graph Objects}{129}
\contentsline {section}{\numberline {2}{\em Graph}\ and {\em GraphObject}}{129}
\contentsline {subsection}{\numberline {2.1}{\em Graph}\ Representation}{130}
\contentsline {subsection}{\numberline {2.2}{\em GraphObject}\ Attributes}{130}
\contentsline {subsection}{\numberline {2.3}The Default Graph Object Attributes}{132}
\contentsline {subsection}{\numberline {2.4}Building Graphs}{133}
\contentsline {subsection}{\numberline {2.5}{\em Vertex}Methods}{134}
\contentsline {subsection}{\numberline {2.6}{\em Edge}}{136}
\contentsline {subsection}{\numberline {2.7}{\em Graph}}{138}
\contentsline {subsubsection}{\numberline {2.7.1}Subgraphs}{138}
\contentsline {subsubsection}{\numberline {2.7.2}Input Graph Language}{143}
\contentsline {subsubsection}{\numberline {2.7.3}{\em Graph}\ Methods}{145}
\contentsline {subsubsection}{\numberline {2.7.4}Adjacency Matrices}{154}
\contentsline {section}{\numberline {3}The Graph Hierarchy}{154}
\contentsline {section}{\numberline {4}Graph Operations}{154}
\contentsline {section}{\numberline {5}Algorithms}{156}
\contentsline {section}{\numberline {2}Algorithms}{156}
\contentsline {subsection}{\numberline {2.1}Algorithm Specifications}{156}
\contentsline {part}{\uppercase {v}\hspace {1em}Internals}{159}
\contentsline {section}{\numberline {1}The Directory Structure}{159}
\contentsline {part}{\uppercase {vi}\hspace {1em}Acknowledgements}{159}
\contentsline {section}{\numberline {A}Graph File Format}{161}
\contentsline {subsection}{\numberline {A.1}Lexical Tokens}{161}
\contentsline {subsection}{\numberline {A.2}Language Grammar}{162}
\contentsline {subsection}{\numberline {A.3}Language Grammar}{164}