\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<Item> } 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<T>} 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}
