\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Graph*  & newGraph()\index{Graph!newGraph()}raph* g) = 0;
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Dynamically allocate a new empty graph of the same type as
		 {\em g}.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Graph*  & copyGraph\index{Graph!copyGraph}(Graph* g) = 0;
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Dynamically allocate a new empty graph of the same type as
		 {\em g}, and initialize it with {\em g}'s contents.  This
		 is useful when the only access to {\em g} is through a 
		 \Graph\ pointer.  If the actual graph object is available,
		 copy constructors can be used.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Graph*  & newEmpty()\index{Graph!newEmpty()} const;
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return a dynamically allocated graph of the same type. \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
ASymMatrix$<$int$>$  & adjacencyMatrix\index{Graph!adjacencyMatrix}(); 
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return an adjacency matrix representation of the graph.
		  If the graph is a hypergraph, it will not be reconstructable
		  from the matrix, but the adjacency information will 
		  still be correct.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool isomorphicQ(const Graph* \graphn); 
  \\
Bool isomorphicQ(const Graph\& \graphn); 
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return TRUE if the current graph is isomorphic to \graphn.
		  The nauty system is used for isomorphism testing, and the
		  symbolic constant MAXN determines the maximum allowable
		  graph size.  As a default, MAXN is set to 30, since 
		  nauty performs major code optimizations if the graphs
		  are smaller than the word size.  MAXN should be reset 
		  if bigger graphs need to be compared.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & binaryQ\index{Graph!binaryQ}(); 
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return TRUE if the every edge has size 2.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & simpleQ\index{Graph!simpleQ}(); 
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return TRUE if the graph type is one of:
                        M\_MIXEDHYPERGRAPH,
                        M\_UNDHYPERGRAPH,
                        M\_DIRHYPERGRAPH,
                        M\_MIXEDBINARYGRAPH,
                        M\_UNDBINARYGRAPH,
                        M\_DIRBINARYGRAPH\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & directedQ\index{Graph!directedQ}(); 
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return TRUE if the graph is directed (not undirected or
		  mixed. \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Vertex*  & addVertex\index{Graph!addVertex}(String vname)
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Creates and inserts a new vertex.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Edge*  & addEdge\index{Graph!addEdge}(Sequence$<$Vertex*$>$ vs) = 0;
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Creates a new (directed) edge with a pointer to a copy 
		 of {\em vs} and inserts the edge.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Edge*  & addEdge\index{Graph!addEdge}(Collection$<$Vertex*$>$\& vs) = 0;
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Creates a new (undirected) edge with a pointer to a copy 
		 of {\em vs} and inserts the edge.  Note that {\em vs}
		 is copied into a \Set\ object, so even though multisets 
		 of vertices may be passed in,
		 no duplicate vertices will exist in the edge
		 (the \Collection\ reference argument allows sets using
		 representations other than DEFAULT\_SET\_IMPL to be passed).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Edge*  & addEdge\index{Graph!addEdge}(Edge *e) = 0;
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Used by the subgraph mechanism to move edges between
		 parent graphs and subgraphs.  Should never be called by
		 the programmer.  SHOULD BE PRIVATE, BUT ACCESS PROBLEMS
		 WITH THE PARSER.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & removeVertex\index{Graph!removeVertex}(Vertex *v)
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Used by the subgraph mechanism to move vertices between
		 parent graphs and subgraphs.  Should never be called by
		 the programmer.  SHOULD BE PRIVATE, BUT ACCESS PROBLEMS
		 WITH THE PARSER.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & removeEdge\index{Graph!removeEdge}(Edge *v)
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Used by the subgraph mechanism to move edges between
		 parent graphs and subgraphs.  Should never be called by
		 the programmer.  SHOULD BE PRIVATE, BUT ACCESS PROBLEMS
		 WITH THE PARSER.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & deleteVertex\index{Graph!deleteVertex}(Vertex *v) = 0;
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Remove $v$ from the vertex set of each of its
		 incident edges, then delete $v$ and 
		any newly-empty edges.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & deleteEdge\index{Graph!deleteEdge}(Edge *e) = 0;
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Remove $e$ from the incident edge sets of each of its
		 vertices, then delete it.\end{minipage}
\end{minipage}
\vspace{0.2in}



\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & clear\index{Graph!clear}()
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Remove all edges and vertices from the graph.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & rank\index{Graph!rank}(Vertex* passed\_vertex)
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Where does this vertex rank in the current order of vertices 
	$(0\ldots n-1)$? $O(1)$ \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & rank\index{Graph!rank}(Edge* passed\_edge)
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Where does this edge rank in the current order of edges 
	$(0\ldots m-1)$? $O(1)$ \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Vertex*  & vertex\index{Graph!vertex}(int i)
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return a pointer to the $i$th vertex. $O(1)$.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Edge*  & edge\index{Graph!edge}(int i)
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return a pointer to the $i$th edge. $O(1)$.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
friend ostream\&  & operator$<$$<$\index{Graph!operator$<$$<$}(ostream\& os, const Graph\& g)
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Output graph $g$ to output stream {\em os}.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
ostream\&  & display\index{Graph!display}(ostream\& os)
\end{tabular}\\
 
	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Output graph $g$ on stream {\em os}.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & display\index{Graph!display}(int indent)
\end{tabular}\\
 
	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}This is called by the saveToFile() method to accommodate
	 subgraphs.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void saveToFile(ofstream* fout) = 0; 
  \\
void saveToFile(ofstream* fout, int indent) = 0;
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Save the graph (including all of its subgraphs) to a file 
	 in the format described in Section \ref{sec:file-format}.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Vertex*  & findVertexByName\index{Graph!findVertexByName}(String name)
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Perform a binary search through the vertex array for a vertex
	 with the given name. $O(l\log n)$, where $l$ is the length of
	 the attribute list.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Vertex*  & findVertexWithEdge\index{Graph!findVertexWithEdge}(String name)
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}This method is used primary by the subgraph mechanism.  IT
	 IS BUGGED, AND IT, ALONG WITH A PORTION OF THE SUBGRAPH 
	 MECHANISM, REQUIRES ATTENTION.\end{minipage}
\end{minipage}
\vspace{0.2in}



\begin{minipage}[t]{8in}
\begin{tabular}{ll}
GraphType  & type\index{Graph!type}()
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the graph type (enumerated in general.h). $O(1)$\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
GraphType  & name\index{Graph!name}()
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Fetch and return the graph's {\em name} attribute. $O(l)$,
		  where $l$ is the length of the attribute list.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & adjacentQ\index{Graph!adjacentQ}(Vertex* v1, Vertex* v2)
\end{tabular}\\
 
	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return TRUE if the two vertices $v1$ and $v2$ are adjacent. 
	 This is the case if there is an edge which contains both $v1$ 
	 and $v2$.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Vertex**  & vertexStart\index{Graph!vertexStart}()
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return a pointer to the first \Vertex\ pointer in the
		 graph's vertex array.  Iteration through the vertices
		 is almost always begun this way (and carried out by a 
		 for loop). $O(1)$\end{minipage}
\end{minipage}
\vspace{0.2in}
 

\begin{minipage}[t]{8in}
\begin{tabular}{ll}
const SortedArray$<$Vertex*$>$\&  & vertices()\index{Graph!vertices()}
\end{tabular}\\
  
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return a reference to the graphs array of vertices $O(1)$.
		 Note: in order for this operation to be efficient,
		 the receiving lvalue must be a {\em reference} to a
		 \SortedArray.\ Otherwise the copy constructor will
		 be invoked and the operation will take time = $O(n)$.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
const MSet$<$Edge*$>$\&  & edges\index{Graph!edges}()
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the \MSet\ containing the graph's edges.
			Note that receiving the return value with object
			is still efficient to due reference counting in
			the \Collection\ hierarchy. $O(1)$\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
MSet$<$Edge*$>$  & incidentEdges\index{Graph!incidentEdges}(Vertex* v) const
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the edges incident on {\em passed\_vertex}. $O(1)$\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
MSet$<$Edge*$>$  & inIncidentEdges\index{Graph!inIncidentEdges}(Vertex* v) const
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the edges in which $v$ is 
		 a ``sink.'' For directed binary graphs, this is a 
		 straightforward
		 operation explained simply as ``all edges pointing to 
		 $v$.  For all hypergraphs and undirected graphs, though,
		 the more abstract explanation is ``all edges in which
		 $v$ is not listed first.''  
		 $O(ds)$, where $d$ is the
		 maximum degree of the graph and $s$ is the maximum size
		 of an edge.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
MSet$<$Edge*$>$  & outIncidentEdges\index{Graph!outIncidentEdges}(Vertex* v) const
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the edges in which $v$ is 
		 a ``source.'' For directed binary graphs, this is a 
		 straightforward
		 operation explained simply as ``all edges pointing away 
		 from $v$.  For all hypergraphs and undirected graphs, though,
		 the more abstract explanation is ``all edges in which
		 $v$ {\em is} listed first.'' 
		 $O(ds)$, where $d$ is the
		 maximum degree of the graph and $s$ is the maximum size
		 of an edge.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & order\index{Graph!order}()
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return number of vertices in graph. $O(1)$\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & size\index{Graph!size}()
\end{tabular}\\
  
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return number of edges in graph. Time complexity 
		  depends on the \Container\ used to implement \MSet.\ 
		  This is specified by DEFAULT\_SET\_IMPL in MSet.h. 
		  With the current \SortedList\ default, the complexity
		  is $O(n)$  (no {\em last} pointer with STk interface)\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & degree\index{Graph!degree}(Vertex* passed\_vertex)
\end{tabular}\\


 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the degree of vertex in the graph.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & inDegree()\index{Graph!inDegree()}ertex* passed\_vertex)
\end{tabular}\\
 

 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the indegree of passed\_vertex (see inIncidentEdges()).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & outDegree\index{Graph!outDegree}(Vertex* passed\_vertex)
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the outdegree
of passed\_vertex (see outIncidentEdges()).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Vertex*  & addSubgraph\index{Graph!addSubgraph}(Graph *owner, List$<$Vertex*$>$* l) = 0;
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Given the passed list of vertices $l$, this method creates a 
	 graph object $g$ of the same type as the current graph and moves
	 the vertices of $l$ and all induced edges into $g$.  A new
	 ``supervertex,'' which contains a pointer to $g$ as an
	 attribute, is then created and inserted into the current graph,
	 then a pointer to it is returned.
	 The supervertex is adjacent to a vertex $v$ in the current graph
	 if and only if there exists $w \in V(g)$ such that $w$ was adjacent
	 to $v$ in the original graph.  Supervertices are treated
         as a normal vertices and can become members of additional
   	 subgraphs.  \end{minipage}
\end{minipage}
\vspace{0.2in}

	 
\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Set$<$Vertex*$>$  & dissolveSubgraph\index{Graph!dissolveSubgraph}(Vertex *sv) = 0;
\end{tabular}\\

	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}If {\em sv} is a supervertex, then it hides a subgraph.  This
	 method extracts the vertices and edges from the subgraph and
	 adds them back to the current graph such that the latter is restored
	 to the same adjacency structure it had before the subgraph was
	 created.  The return value is the set of subgraph vertices.\end{minipage}
\end{minipage}
\vspace{0.2in}

	 
