\section{\Graph\ and \GraphObject} The \Graph\ class and its descendants provide the programmer with 12 different types of graph and hypergraph objects. The following three types of restriction of a graph's edge set determine the graph classes. \begin{enumerate} \item {\em Multiset or not?} This determines whether the graph is a multigraph or a simple graph. \label{it:ms} \item {\em Cardinality of each edge equals 2?} This determines whether the graph is a graph (also called {\em binary graph}) or a hypergraph. \label{it:cd} \item {\em Directed, Undirected, or Mixed?} In directed graphs, every edge must consist of a \Sequence\ of vertices. In undirected graphs, each edge must consist of a \Set\ of vertices. LINK also offers the option of defining {\em mixed graphs}, in which both directed and undirected edges may occur in the same graph. \label{it:dum} \end{enumerate} Restrictions~\ref{it:ms} and \ref{it:dum} are implemented using specific objects of the \Collection\ hierarchy as the \Vertex\ sets of \Edges. Restriction~\ref{it:cd} is implemented with simple test. Each of the classes determined by these criteria is described in detail in Section~\ref{sec:gh}. \Graphs,\ \Vertices,\ and \Edges\ have some commonality in that they each have character string names and may have other attributes, and in that they each are ``owned'' by a \Graph\ object. \Graph\ objects may be owned by themselves, or by a parent \Graph\ through the subgraph mechanism (see Section~\ref{sec:subgraphs}). The \GraphObject\ class exists as an abstract parent to all three classes to avoid redefinition of common operations. It contains methods which the \Graph\ classes call access and modify attributes, but there is a more natural for the LINK programmer to use an alternate method, which will be described in Section~\ref{sec:attr}. \subsection{\Graph\ Representation} Simple graphs are commonly represented using adjacency lists, in which each vertex contains a pointer to a list of its neighbors. There is typically no explicit representation of edges; $v_i$ is said to be adjacent to $v_j$ if $v_j$ is in the adjacency list of $v_i$. In LINK, however, this representation is not sufficient. A hypergraph $G$ is a pair $(V,E)$, where $V = \{v_0, v_1,\ldots, v_{n-1}\}$ is a set of vertices and $E = \{e_0, e_2, \ldots, e_{m-1}\}$ is a collection of finite subsets of $V$. Since edges may have cardinalities not equal to 2, adjacency list membership is not sufficient to determine the neighbors of a vertex. In LINK, hypergraphs are represented by a \SortedArray\ of \Vertex\ pointers and an \MSet\ of \Edge\ pointers. The \Container\ object \SortedArray\ is used instead of {\em Set$<$Vertex*, SortedArray$<$Vertex*$>$ \ $>$} in order to allow the \label{page:rep} programmer to circumvent the \Iterator\ mechanism and iteration through the \Vertex\ set using fast pointer arithmetic. Membership checks prevent duplicate \Vertices\ from occurring. Each \Edge\ object contains a \Collection\ pointer which locates the set or sequence storing the \Vertices\ in that \Edge.\ The virtual functions of the \Collection\ class can allow a single algorithm code to work on many different classes of \Graph\ objects with no modification. The bottleneck in accomplishing this in general is being able to define an algorithm's performance on various classes of \Graph\ rather than language or system limitations. \subsection{\GraphObject\ Attributes} \label{sec:attr} \label{page:attr} Although there is an \Attribute\ class in the {\em graph} directory of LINK's file hierarchy, objects of this class are typically not instantiated by the programmer. The reason for this is that \Attribute\ objects, though owned by a specific \Graph\ object $G$, are accessible to any \GraphObject\ (\Vertex,\ \Edge,\ or \Subgraph) which belongs to $G$. The programmer's interface to the attribute mechanism consists of the following three templated functions. This is one of the very very instances of the use of non-member functions in LINK programming. \begin{alltt} template \(<\)class Item\(>\) int {\bf newAttribute}(Graph*, String name, const Item&); template \(<\)class Item\(>\) int {\bf setAttribute}(GraphObject*, String name, const Item&); template \(<\)class Item\(>\) int {\bf getAttribute}(GraphObject*, String name, Item&); \end{alltt} An example illustrating the use of these functions is presented in Figure~\ref{fig:Attr1}. The {\em newAttribute(...)} function dynamically allocates an {\em Attribute } object and associates it with the passed \Graph. \ The default value of the attribute is stored in this object and accessed with the {\em setAttribute(...) } function. The latter may take as its first argument not only a pointer to a \Graph\ object, but also a pointer to any instance of the \GraphObject\ hierarchy. Thus, even though the actual \Attribute\ object is ``owned'' by the graph, any of its vertices and edges may access its default value. \begin{figure}[tbp] \input{examples/graph/ProgAttr1.tex} \caption{Graph \Attributes} \label{fig:Attr1} \end{figure} In order to set differing attribute values for individual vertices and edges of a graph, the {\em setAttribute(...)} function is used. The call format is the same as in the other two. Recall that the \Attribute\ object itself is owned by the \Graph\ object. When a call to {\em setAttribute(...)} asks for some \Vertex\ or \Edge\ to replace the default value with a new value, a {\em copy} of the \Attribute\ object is obtained, associated with the \Vertex\ or \Edge,\ and given the new value. Subsequent calls to {\em getAttribute(...)} for the affected \Vertex\ or \Edge\ return the local attribute value rather than the graph's default value. Note that this implies that even if an attribute is intended to apply only to a graph's vertices, it does exist in the graph and can be given values for the graphs edges also. For example, it is unnecessary to employ two separated attributes {\em vertex\_weight} and {\em edge\_weight}. One {\em weight} attribute is sufficient. The \Attribute\ class imposes only one restriction on a data type $A$ used as an attribute value: that the operator function \verb+ostream& operator<<(ostream&, const A&)+ be defined. Subject to this requirement, any data type may be used as a graph attribute. However, there are restrictions in the types of attributes that can be stored in a file with the graph (See Section~\ref{sec:save-load}). {\bf Warning:} Since the three attribute functions described above are templated functions, the actual parameters in the a function call must match the formal parameters exactly. Otherwise, a ``{\em type unification failed}'' will result (g++). The first argument of each function is an abstract base class pointer, so it may seem natural to pass in addresses of descendent objects. This must be avoided. Note that the calls in Figure~\ref{fig:Attr1} use explicit typecasts to match the function template. \subsection{The Default Graph Object Attributes} \label{sec:def-attrs} \begin{itemize} \item {\em back} [int] Set by Depth-first search for each vertex $v$, this attribute stores the discovery time of the earliest ancestor which $v$ is adjacent to via a back edge. \item {\em color} [char *] This attribute, commonly associated with both vertices and edges, takes on string values representing Tk colors. See the Tk manual for details, but the values are typically very straightforward, e.g. "blue" or "green." The STk interface uses this value to determine the actual color of each vertex or edge (and can modify it). \item {\em direction} [int] This outdated attribute stores information indicating whether an edge object is directed or undirected. A more natural way to tell this is: {\em e->vertices()->sortedQ()}, where an answer of ``yes'' means undirected. \item {\em distance} [double] Distance calculations such as shortest paths use and modify this attribute, usually associated with vertices. \item {\em name} [char *] This attribute stores the name by which this graph or graph object is identified. This attribute should never change. \item {\em finishtime} [int] Depth-first search sets this attribute as it finishes searching the neighbors of each vertex. Ordering the vertices by {\em finishtime} yields a postorder walk. \item {\em label} [char *] The {\em label} of a vertex or edge is a string of text currently associated with the object. Users and algorithms may change this from the interface and from C++ programs. \item {\em low} [int] Set by Depth-first search for each vertex $v$, this attribute stores the discovery time of the earliest proper ancestor to which any child of $v$ is adjacent to via a back edge. \item {\em mark} [int] This general purpose attribute is provided to call attention to special vertices or edges. For example, the strongly connected components algorithm sets this mark for each component leader. \item {\em pred} [Vertex*] Graph searches induce a tree which is very useful for constructing more advanced algorithms. This tree is stored in the form of {\em predecessor} information for each vertex. The root of the search tree is found by following {\em pred} pointers as far as possible. \item {\em size} [int] This attribute is usually associated only with Vertex objects, and specifies the size in pixels of the vertex on the screen. \item {\em starttime} [int] Depth-first search sets this attribute as it discovers each vertex. Ordering the vertices by {\em starttime} yields a preorder walk. \item {\em type} [int] This is another general purpose attribute. One examples usage is to store the classification of an edge $e$ during and after a depth-first search. \item {\em width} [int] The {\em width} of an edge is the screen width in pixels. Common values range from 1 to 4. \item {\em weight} [double] Graphs with vertex and edge weights arise in many, many applications. This double- precision attribute stores the weight of a Vertex or Edge object. \item {\em x} [double] This is the ``x'' coordinate of a Vertex object or the label (and control point) of an Edge object. The value is expected to be in world coordinates, where the world ranges from 0 to 1 in each direction. \item {\em y} [double] Similar to ``x.'' \end{itemize} \subsection{Building Graphs} \input{graph/ProgGraphBuild.tbl.tex} \subsection{\Vertex Methods} Each \Vertex\ object contains an \MSet\ of \Edge\ pointers representing its incident edges. Note that the storage medium is a multiset rather than a set because, in a multigraph, an \Edge\ might be incident to the same \Vertex\ twice. \Vertex\ objects are never constructed explicitly by the programmer. See the \Graph\ methods for adding vertices. \operations \input{graph/ProgVertex.tbl.tex} \subsection{\Edge} \Edge\ objects use the flexibility of the \Collection\ hierarchy to allow any given edge to be directed or undirected. A pointer to a \Collection\ of \Vertex\ pointers is stored in the \Edge\ object. If this pointer points to a sequence, then the edge takes on properties of a directed edge. Otherwise the edge behaves as an undirected edge. Thus, {\em directed hyperedges} are simply defined to be sequences of vertices of varying length. As described briefly in the \Vertex\ methods above, the {\em inNeighbors()} of a \Vertex\ object $v$ with respect to a directed \Edge\ object $e$ are those \Vertices\ which occur {\em before} $v$ in the $e$'s vertex sequence. If, on the other hand, \Edge\ $e$ is undirected, the {\em inNeighbors()} of $v$ with respect to $e$ are defined to be all $\{w : (w \in e) \wedge (w \neq v)\}$. The {\em outNeighbors()} of $v$ with respect to $e$ are defined similarly, except that in the directed case, the neighboring vertices are those found {\em after} $v$ in $e$. Like \Vertex\ objects, \Edge\ objects are never constructed explicitly by the programmer. See the \Graph\ methods for adding vertices. \operations \input{graph/ProgEdge.tbl.tex} \subsection{\Graph} The \Graph\ class is an abstract class from which all graph types in LINK are derived. Like the \Collection\ class the \Graph\ class provides declarations for the core methods of the associated hierarchy of objects (this graph hierarchy is described in detail in Section~\ref{sec:gh}). Unlike class \Collection,\ however, the \Graph\ class also provides several method definitions. It can do this since the graph representation objects (see Page~\pageref{page:rep}) are available in the class (The \Collection\ implementation is not available in class \Collection;\ it is defined in \MSetBase). \begin{figure}[tbp] \input{examples/graph/ProgBinGraph1.tex} \caption{``Mixed'' Binary Graph} \label{fig:BinGraph1} \end{figure} \begin{figure}[tbp] \input{examples/graph/ProgDBinGraph1.tex} \caption{Directed Binary Graph} \label{fig:DBinGraph1} \end{figure} \begin{figure}[tbp] \input{examples/graph/ProgMDBinGraph1.tex} \caption{Directed Binary Multigraph} \label{fig:MDBinGraph1} \end{figure} \begin{figure}[tbp] \input{examples/graph/ProgMUBinGraph1.tex} \caption{Undirected Binary Multigraph} \label{fig:MUBinGraph1} \end{figure} \subsubsection{Subgraphs} \label{sec:subgraphs} Before describing the \Graph\ methods, it is necessary to give a description of the {\em subgraph} mechanism used in LINK. In applications which manipulate extremely large graphs, it is often a practical necessity to present the graph as a small, ``coarse'' graph in which certain areas of interest to the end user can be expanded to reveal finer detail. LINK's subgraph mechanism allows the user or programmer to identify the vertices of any {\em induced subgraph} of $G$~\footnote{An induced subgraph of a graph $G = (V,E)$ is another graph $G' = (V',E')$, where $V' \subseteq V$ and $E'$ consists of those edges in $E$ whose vertex sets are entirely contained in $V'$.} and replaced it with a single vertex, called a {\em supervertex}. This supervertex can later be expanded to reveal the hidden detail. This subgraph contraction in LINK is hierarchical, i.e., the programmer or user can create arbitrary numbers of subgraph layers (subgraphs contracted within subgraphs). An induced subgraph of a graph $G = (V,E)$ is contracted by selecting a subset of vertices $V'$ and calling the {\em addSubgraph(...)} method defined below. When contracted, the vertices of $V'$ and the edges of $E'$ are (apparently to the user or programmer) removed from the graph and replaced by a supervertex, which behaves as a normal vertex when processed by a graph algorithm. However, the subgraph information is maintained as an attribute of the supervertex. This attribute is itself an object from the \Graph\ hierarchy of the same type as its parent graph. An important restriction to keep in mind when creating subgraphs is the following: \begin{quote} Every vertex which is put into a subgraph must have the same parent. \end{quote} In other words, two vertices which reside on different levels of the implicit subgraph hierarchy cannot be placed together into a new subgraph. One might ask how this situation could ever arise in the first place, since the user would not be able to see vertices at different levels simultaneously. It {\em is} possible for this to happen, however. Once created, subgraphs may be ``opened'' without being ``dissolved.'' The user may want to view the expanded graph momentarily, then hide the subgraph again. The methods implementing this functionality are described in Section~\ref{sec:graph-methods} below. \subsubsection{Input Graph Language} \label{sec:save-load} It is possible to store and retrieve LINK graphs from disk along with certain associated attributes using the {\em Graph::saveToFile(...)} method and the {\em parseGraph(...)} function. Although the input graph language allows for the saving of attributes, it reduces to the format produced by the {\em Graph::display(...)} method if no attributes need to be saved. The system currently supports the saving and loading of {\em int, float, double,} and {\em String (char*)} attributes. Future modifications to the parser may allow the storage of general type information, allowing the programmer to add support a specific complex or pointer typed attributes. In the meantime, programmers who want to group all attribute information into a single class attribute to save calls to {\em setAttribute(...)} and {\em getAttribute(...)} are encouraged to write transformation routines which extract individual attribute fields and make them independent primitive attributes prior to storage on disk (and vice versa). Stored graphs are loaded into LINK using a parser which uses the grammar listed in Appendix~\ref{sec:file-format}. Several examples of graph input files are also included in Appendix~\ref{sec:example-files}. As stated previously, attributes of \GraphObjects\ can be stored in the graph input file. The parser will recognize and build attributes of the following types, which conform to the C language standard with stated exceptions: \begin{itemize} \item {\em int}: Signed integers, with leading 0's allowed. \item {\em double}: Double precision floating point constants, expressed exactly as in the C standard. \item {\em float}: Single precision floating point constants, expressed as in the C standard except that a trailing {\em f} or {\em F} to designate the constant as \verb+float+ and not the default \verb+double+ representation. \item {\em String}: Valid C string constants (enclosed in double quotes). \end{itemize} The graph input file format itself begins with an optional preamble which identifies the graph type and declares {\em all} attributes which should be associated with the graph and its \Vertex\ and \Edge\ objects. If the preamble is missing, the graph type is assumed to be the most specific type matching the edge set. For example, \DBinGraph\ (directed binary graph) is more specific than \DHyperGraph\ (directed hypergraph) or \BinGraph\ (binary graph where each edge may be either directed or undirected). A \DBinGraph\ {\em is a} \DHyperGraph\ and a \BinGraph\ at the same time. See Section~\ref{sec:gh} for a discussion. The parenthesized attribute declarations list consists of 0 or more attribute declarations of the following format (the names used here are not the actual names of nonterminals in the input language grammar): \begin{center} $<$attr\_name$>$ ( $<$attr\_value$>$ ) \end{center} The $<$attr\_name$>$ is a C language identifier (not a string constant). The $<$attr\_value$>$ may be any of the constants listed above (int, float, double, string constant), unless the given $<$attr\_name$>$ is one of the reserved words listed below, in which case the type must conform to the following table: \vspace*{2mm} \begin{tabular}{|l|l|} \hline reserved attribute name & required type of constant \\ \hline graph\_name & $<$string constant$>$ \\ \hline name & $<$string constant$>$ \\ \hline location & ($<$numeric constant$>$,$<$numeric constant$>$) \\ \hline vcolor & $<$int constant$>$ \\ \hline ecolor & $<$int constant$>$ \\ \hline direction & $<$int constant$>$ \\ \hline weight & $<$int constant$>$ \\ \hline open & $<$int constant$>$ \\ \hline \end{tabular} \vspace*{2mm} These attributes are reserved since they are fairly standard and are assumed to be the stated type by the underlying system. New reserved attributes may be added by adding reserved words to \verb+/src/interface/scanner.l+. The parser need not be changed unless the new reserved attribute must be of a type which is not currently supported. If the $<$attr\_name$>$ is not reserved, then the type of the $<$attr\_value$>$ determines the type of \Attribute\ object which will be created and associated with the graph. After the preamble, there is a square-bracket enclosed list of vertex names with optional associated attributes. Each vertex specification consists of an identifier, integer constant, or string constant naming the vertex and a square bracket enclosed list of attributes of the same format as that discussed above. The only difference is that {\em it is not permitted to declare new attributes outside of the preamble}. Any unrecognized attribute name outside of the preamble will be flagged as an undeclared attribute and the parse will be aborted. The final section of the graph input file identifies the \Edges.\ \ Undirected edges are specified with curly-brace enclosed lists of identifiers, integer constants, or string constants identifying vertices. There is no delimiter other than white space separating the vertex names in this list. {\em If any edge contains a vertex name which did not appear in the {\em Vertices} section, that vertex is reported to be undeclared and the parse fails.} Support for further attribute types can be obtained by studying and specializing the {\em AttributeElementOps} class in Attribute.h (for correct output) and the graph language grammar listed in Appendix~\ref{sec:file-format}, which is automatically generated from parser.y in the \verb+/src/interface+ directory. In order to allow arbitrary structure or pointer types to be stored and reloaded successfully, the graph input language would have to be augmented with more type recognizing power. Recall from Section~\ref{sec:subgraphs} that a \Subgraph\ is actually maintained as an \Attribute\ of a special vertex. The parser is designed so that it is possible to save and reload graphs with layers of subgraphs. However, this mechanism is not complete and bugs remain. An example of the process of saving a LINK graph is depicted in Figure~\ref{fig:Save1}. \begin{figure}[tbp] \input{examples/graph/ProgSave1.tex} \caption{Saving a LINK Graph} \label{fig:Save1} \end{figure} Now give an example with different types \\ \begin{figure}[tbp] \input{examples/graph/ProgLoad1.tex} \caption{Loading a LINK Graph from Disk} \label{fig:Load1} \end{figure} \begin{figure}[tbp] \input{examples/graph/ProgBinGraphCopy1.tex} \caption{Copying a Graph without its Attributes} \label{fig:BinGraphCopy1} \end{figure} \subsubsection{\Graph\ Methods} \label{sec:graph-methods} The \Graph\ class is abstract, so there are no objects of class \Graph\ to create. The methods used by objects of the derived graph hierarchy are listed below. Those ending in \verb+= 0+ lack definitions, which are generally provided by class \MHyperGraph\ (see Section~\ref{sec:gh}). \input{graph/ProgGraph.tbl.tex} \subsubsection{Adjacency Matrices} \input{graph/ProgAdjacencyMatrix.tbl.tex} \section{The Graph Hierarchy} \label{sec:gh} \begin{figure} \centerline{\psfig{figure=figures/graph_hier.ps,height=3in,width=4.5in}} \caption{The \Graph Hierarchy} \label{fig:graph-hier} \end{figure} %\subsection{\HyperGraph\ and \MHyperGraph} %\subsection{\UHyperGraph\ and \MUHyperGraph} %\subsection{\DHyperGraph\ and \MDHyperGraph} %\subsection{\BinGraph\ and \MBinGraph} %\subsection{\UBinGraph\ and \MUBinGraph} %\subsection{\DBinGraph\ and \MDBinGraph} %\subsection{Copying Various Types of Graph} \section{Graph Operations} The unary and binary graph operations are listed below. For a discussion of the meaning of each operation, see~\cite{bm76} (for example). Note that each operation returns \MHyperGraphn. This allows the programmer maximum flexibility with respect to graph type. The \Graph class constructors make it easy to convert the result into a more specific form. For example, suppose the programmer knows that the result should be treated as an undirected, binary graph. The following line of code produces a copy of the g's complement which is of the appropriate type: \begin{center} {\em UBinGraph ug = g->complement();} \end{center} \input{graph/ProgGraphOperations.tbl.tex}