\relax \@writefile{toc}{\contentsline {section}{\numberline {10}Compiling LINK Programs}{60}} \@writefile{toc}{\contentsline {section}{\numberline {2}Extending the System}{60}} \newlabel{sec:compiling}{{2}{60}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.1}The Makefile}{60}} \@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Makefile macros intended to be modified by the LINK library programmer.}}{61}} \newlabel{fig:make-demo}{{2.2}{61}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Adding a Menu Option}{61}} \@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces An example wrapper routine}}{62}} \newlabel{fig:even-odd}{{2.3}{62}} \@writefile{lof}{\contentsline {figure}{\numberline {3.4}{\ignorespaces Depth-First Search}}{63}} \newlabel{fig:dfs}{{3.4}{63}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.3}An Example Wrapper}{63}} \@writefile{toc}{\contentsline {section}{\numberline {3}Algorithms}{63}} \@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Algorithm Specifications}{64}} \@writefile{toc}{\contentsline {section}{\numberline {4}Basic Objects}{65}} \@writefile{toc}{\contentsline {section}{\numberline {2}{\em Containers}}{65}} \newlabel{sec:container}{{2}{65}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Adding New {\em Containers}}{65}} \@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces The {\em ElementOps}\ Class}}{66}} \newlabel{fig:ElementOps}{{2.2}{66}} \newlabel{page:container}{{2.1}{68}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Iterators}{68}} \newlabel{sec:iterator}{{2.2}{68}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1}{\em ContainerNode}}{68}} \@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces Use of {\em Iterator}}}{69}} \newlabel{fig:iterator1}{{2.3}{69}} \@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces {\em List}\ objects}}{70}} \newlabel{fig:List1}{{2.4}{70}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.3}{\em List}}{70}} \newlabel{sec:list}{{2.3}{70}} \@writefile{lof}{\contentsline {figure}{\numberline {2.5}{\ignorespaces {\em List}\ constructors}}{71}} \newlabel{fig:List3}{{2.5}{71}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.4}{\em SortedList}}{74}} \@writefile{lof}{\contentsline {figure}{\numberline {2.6}{\ignorespaces {\em List}\ and {\em SortedList}}}{75}} \newlabel{fig:List4}{{2.6}{75}} \@writefile{lof}{\contentsline {figure}{\numberline {2.7}{\ignorespaces Comparisons of {\em Containers}}}{76}} \newlabel{fig:List5}{{2.7}{76}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.5}{\em DList}}{78}} \@writefile{lof}{\contentsline {figure}{\numberline {2.8}{\ignorespaces {\em DList}}}{79}} \newlabel{fig:DList1}{{2.8}{79}} \@writefile{lof}{\contentsline {figure}{\numberline {2.9}{\ignorespaces Special {\em DList}\ operations}}{80}} \newlabel{fig:DList3}{{2.9}{80}} \@writefile{lof}{\contentsline {figure}{\numberline {2.10}{\ignorespaces Comparisons of {\em List}\ and {\em DList}}}{81}} \newlabel{fig:DList2}{{2.10}{81}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.6}{\em Deque}}{82}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.6.1}{\em Queue}}{83}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.6.2}Stack}{84}} \@writefile{lof}{\contentsline {figure}{\numberline {2.11}{\ignorespaces Iteration and {\em Array}\ objects}}{86}} \newlabel{fig:Array1}{{2.11}{86}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.7}Arrays}{86}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.8}{\em SortedArray}}{89}} \@writefile{lof}{\contentsline {figure}{\numberline {2.12}{\ignorespaces {\em Arrays}\ and {\em SortedArrays}}}{90}} \newlabel{fig:Array2}{{2.12}{90}} \@writefile{lof}{\contentsline {figure}{\numberline {2.13}{\ignorespaces {\em BinaryHeap}}}{93}} \newlabel{fig:BinaryHeap1}{{2.13}{93}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.9}Priority Queue Dictionary Structures}{93}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.9.1}{\em BinaryHeap}}{93}} \@writefile{lof}{\contentsline {figure}{\numberline {2.14}{\ignorespaces Another {\em BinaryHeap}\ example}}{94}} \newlabel{fig:BinaryHeap2}{{2.14}{94}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.9.2}{\em BinomialHeap}}{96}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.10}General Dictionary Structures}{99}} \@writefile{lof}{\contentsline {figure}{\numberline {2.15}{\ignorespaces {\em BinarySearchTree}}}{100}} \newlabel{fig:BinarySearchTree1}{{2.15}{100}} \@writefile{lof}{\contentsline {figure}{\numberline {2.16}{\ignorespaces {\em RedBlackTree}}}{101}} \newlabel{fig:RedBlackTree1}{{2.16}{101}} \@writefile{lof}{\contentsline {figure}{\numberline {3.17}{\ignorespaces The {\em Collection}\ Hierarchy}}{102}} \newlabel{fig:coll}{{3.17}{102}} \@writefile{toc}{\contentsline {section}{\numberline {3}{\em Collections}}{102}} \newlabel{sec:collection}{{3}{102}} \@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Discussion}{102}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {3.1.1}Organization}{102}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {3.1.2}Reference Counting}{103}} \@writefile{lof}{\contentsline {figure}{\numberline {3.18}{\ignorespaces Reference Counting in {\em Collections}}}{104}} \newlabel{fig:MSet0}{{3.18}{104}} \@writefile{lof}{\contentsline {figure}{\numberline {3.19}{\ignorespaces Reference Counting and Modifications in {\em Collections}}}{105}} \newlabel{fig:MSet1}{{3.19}{105}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {3.1.3}Comparisons}{105}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {3.1.4}Set Primitive Operations}{105}} \@writefile{lof}{\contentsline {figure}{\numberline {3.20}{\ignorespaces Passing and Returning Collection Objects}}{106}} \newlabel{fig:MSet7}{{3.20}{106}} \@writefile{lof}{\contentsline {figure}{\numberline {3.21}{\ignorespaces Comparisons Between {\em Collections}\ and {\em Containers}}}{107}} \newlabel{fig:MSet2}{{3.21}{107}} \@writefile{lof}{\contentsline {figure}{\numberline {3.22}{\ignorespaces Comparisons between {\em Collections}}}{108}} \newlabel{fig:MSet5}{{3.22}{108}} \@writefile{lof}{\contentsline {figure}{\numberline {3.23}{\ignorespaces The Set Primitive Operations}}{109}} \newlabel{fig:MSet3}{{3.23}{109}} \@writefile{lof}{\contentsline {figure}{\numberline {3.24}{\ignorespaces Set Primitives with Set and Sequence Operands }}{110}} \newlabel{fig:MSet6}{{3.24}{110}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {3.1.5}Interface}{111}} \@writefile{toc}{\contentsline {subsection}{\numberline {3.2}{\em MSetBase}\ and {\em MSet}}{114}} \newlabel{sec:set}{{3.2}{114}} \@writefile{lof}{\contentsline {figure}{\numberline {3.25}{\ignorespaces {\em MSetBase}\ and {\em MSet}}}{115}} \newlabel{fig:MSet4}{{3.25}{115}} \@writefile{toc}{\contentsline {subsection}{\numberline {3.3}{\em SetBase}\ and {\em Set}}{121}} \@writefile{toc}{\contentsline {subsection}{\numberline {3.4}{\em SequenceBase}\ and {\em Sequence}}{122}} \newlabel{sec:sequence}{{3.4}{122}} \@writefile{lof}{\contentsline {figure}{\numberline {3.26}{\ignorespaces {\em Sequence}}}{123}} \newlabel{fig:Sequence1}{{3.26}{123}} \@writefile{lof}{\contentsline {figure}{\numberline {3.27}{\ignorespaces Another {\em Sequence}\ Example}}{124}} \newlabel{fig:Sequence2}{{3.27}{124}} \@writefile{toc}{\contentsline {section}{\numberline {4}Combinatorial Objects}{126}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Commonalities Among Combinatorial Objects}{126}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Permutations}{126}} \@writefile{toc}{\contentsline {section}{\numberline {5}Graph Objects}{129}} \@writefile{toc}{\contentsline {section}{\numberline {2}{\em Graph}\ and {\em GraphObject}}{129}} \newlabel{it:ms}{{1}{129}} \newlabel{it:cd}{{2}{129}} \newlabel{it:dum}{{3}{129}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.1}{\em Graph}\ Representation}{130}} \newlabel{page:rep}{{2.1}{130}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.2}{\em GraphObject}\ Attributes}{130}} \newlabel{sec:attr}{{2.2}{130}} \newlabel{page:attr}{{2.2}{130}} \@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Graph {\em Attributes}}}{131}} \newlabel{fig:Attr1}{{2.2}{131}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.3}The Default Graph Object Attributes}{132}} \newlabel{sec:def-attrs}{{2.3}{132}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Building Graphs}{133}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.5}{\em Vertex}Methods}{134}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.6}{\em Edge}}{136}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.7}{\em Graph}}{138}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.7.1}Subgraphs}{138}} \newlabel{sec:subgraphs}{{2.7.1}{138}} \@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces ``Mixed'' Binary Graph}}{139}} \newlabel{fig:BinGraph1}{{2.3}{139}} \@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces Directed Binary Graph}}{140}} \newlabel{fig:DBinGraph1}{{2.4}{140}} \@writefile{lof}{\contentsline {figure}{\numberline {2.5}{\ignorespaces Directed Binary Multigraph}}{141}} \newlabel{fig:MDBinGraph1}{{2.5}{141}} \@writefile{lof}{\contentsline {figure}{\numberline {2.6}{\ignorespaces Undirected Binary Multigraph}}{142}} \newlabel{fig:MUBinGraph1}{{2.6}{142}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.7.2}Input Graph Language}{143}} \newlabel{sec:save-load}{{2.7.2}{143}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.7.3}{\em Graph}\ Methods}{145}} \newlabel{sec:graph-methods}{{2.7.3}{145}} \@writefile{lof}{\contentsline {figure}{\numberline {2.7}{\ignorespaces Saving a LINK Graph}}{146}} \newlabel{fig:Save1}{{2.7}{146}} \@writefile{lof}{\contentsline {figure}{\numberline {2.8}{\ignorespaces Loading a LINK Graph from Disk}}{147}} \newlabel{fig:Load1}{{2.8}{147}} \@writefile{lof}{\contentsline {figure}{\numberline {2.9}{\ignorespaces Copying a Graph without its Attributes}}{148}} \newlabel{fig:BinGraphCopy1}{{2.9}{148}} \citation{bm76} \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.7.4}Adjacency Matrices}{154}} \@writefile{toc}{\contentsline {section}{\numberline {3}The Graph Hierarchy}{154}} \newlabel{sec:gh}{{3}{154}} \@writefile{toc}{\contentsline {section}{\numberline {4}Graph Operations}{154}} \@writefile{lof}{\contentsline {figure}{\numberline {3.10}{\ignorespaces The {\em Graph}Hierarchy}}{155}} \newlabel{fig:graph-hier}{{3.10}{155}} \@writefile{toc}{\contentsline {section}{\numberline {5}Algorithms}{156}} \@writefile{toc}{\contentsline {section}{\numberline {2}Algorithms}{156}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Algorithm Specifications}{156}} \@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Depth-First Search}}{157}} \newlabel{fig:dfs}{{2.2}{157}} \@setckpt{PROGRAMMERS_MANUAL/progman}{ \setcounter{page}{159} \setcounter{equation}{0} \setcounter{enumi}{3} \setcounter{enumii}{0} \setcounter{enumiii}{0} \setcounter{enumiv}{0} \setcounter{footnote}{2} \setcounter{mpfootnote}{0} \setcounter{part}{4} \setcounter{section}{2} \setcounter{subsection}{1} \setcounter{subsubsection}{0} \setcounter{paragraph}{0} \setcounter{subparagraph}{0} \setcounter{figure}{2} \setcounter{table}{0} }