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