Next: Adjacency Matrices Up: Graph Previous: Input Graph Language

### 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 `= 0` lack definitions, which are generally provided by class MHyperGraph (see Section ).

Figure 2.9: Copying a Graph without its Attributes
Graph* | newGraph() raph* g) = 0;

Dynamically allocate a new empty graph of the same type as g.

Graph* | copyGraph (Graph* g) = 0;

Dynamically allocate a new empty graph of the same type as g, and initialize it with g's contents. This is useful when the only access to g is through a Graph pointer. If the actual graph object is available, copy constructors can be used.

Graph* | newEmpty() const;

Return a dynamically allocated graph of the same type.

ASymMatrix<int> | adjacencyMatrix ();

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.

Bool isomorphicQ(const Graph* graph ); |
Bool isomorphicQ(const Graph& graph ); |

Return TRUE if the current graph is isomorphic to graph . 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.

Bool | binaryQ ();

Return TRUE if the every edge has size 2.

Bool | simpleQ ();

Return TRUE if the graph type is one of: M_MIXEDHYPERGRAPH, M_UNDHYPERGRAPH, M_DIRHYPERGRAPH, M_MIXEDBINARYGRAPH, M_UNDBINARYGRAPH, M_DIRBINARYGRAPH

Bool | directedQ ();

Return TRUE if the graph is directed (not undirected or mixed.

Vertex* | addVertex (String vname)

Creates and inserts a new vertex.

Edge* | addEdge (Vertex* v1, Vertex *v2) = 0;

Creates a new edge with a containing v1 and v2. If the graph is directed, the sequence of vertices will be (v1, v2); otherwise the new edge will be undirected.

Edge* | addEdge (Sequence<Vertex*> vs) = 0;

Creates a new (directed) edge with a pointer to a copy of vs and inserts the edge.

Edge* | addEdge (Collection<Vertex*>& vs) = 0;

Creates a new (undirected) edge with a pointer to a copy of vs and inserts the edge. Note that 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).

Edge* | addEdge (Edge *e) = 0;

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.

void | removeVertex (Vertex *v)

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.

void | removeEdge (Edge *v)

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.

void | deleteVertex (Vertex *v) = 0;

Remove v from the vertex set of each of its incident edges, then delete v and any newly-empty edges.

void | deleteEdge (Vertex *v1, Vertex *v2) = 0;

If e is an undirected edge containing only v1 and v2, or e is a directed edge containing v1 first, then v2, then remove e from the incident edge sets of each of its vertices, then delete it.

void | deleteEdge (Edge *e) = 0;

Remove e from the incident edge sets of each of its vertices, then delete it.

void | clear ()

Remove all edges and vertices from the graph.

int | rank (Vertex* passed_vertex)

Where does this vertex rank in the current order of vertices ? O(1)

int | rank (Edge* passed_edge)

Where does this edge rank in the current order of edges ? O(1)

Vertex* | vertex (int i)

Return a pointer to the ith vertex. O(1).

Vertex* | randomVertex ()

Return a pointer to a randomly-selected vertex. O(1).

Edge* | edge (int i)

Return a pointer to the ith edge. O(1).

friend ostream& | operator<< (ostream& os, const Graph& g)

Output graph g to output stream os.

ostream& | display (ostream& os)

Output graph g on stream os.

void | display (int indent)

This is called by the saveToFile() method to accommodate subgraphs.

void saveToFile(ofstream* fout) = 0; |
void saveToFile(ofstream* fout, int indent) = 0; |

Save the graph (including all of its subgraphs) to a file in the format described in Section A.

Vertex* | findVertexByName (String name)

Perform a binary search through the vertex array for a vertex with the given name. , where l is the length of the attribute list.

Vertex* | findVertexWithEdge (String name)

This method is used primary by the subgraph mechanism. IT IS BUGGED, AND IT, ALONG WITH A PORTION OF THE SUBGRAPH MECHANISM, REQUIRES ATTENTION.

GraphType | type ()

Return the graph type (enumerated in general.h). O(1)

GraphType | name ()

Fetch and return the graph's name attribute. O(l), where l is the length of the attribute list.

Bool | adjacentQ (Vertex* v1, Vertex* v2)

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.

Vertex** | vertexStart ()

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)

const SortedArray<Vertex*>& | vertices()

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 reference to a SortedArray. Otherwise the copy constructor will be invoked and the operation will take time = O(n).

const MSet<Edge*>& | edges ()

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)

MSet<Edge*> | incidentEdges (Vertex* v) const

Return the edges incident on passed_vertex. O(1)

MSet<Edge*> | inIncidentEdges (Vertex* v) const

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.

MSet<Edge*> | outIncidentEdges (Vertex* v) const

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 is listed first.'' O(ds), where d is the maximum degree of the graph and s is the maximum size of an edge.

int | order ()

Return number of vertices in graph. O(1)

int | size ()

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 last pointer with STk interface)

int | degree (Vertex* passed_vertex)

Return the degree of vertex in the graph.

int | inDegree() ertex* passed_vertex)

Return the indegree of passed_vertex (see inIncidentEdges()).

int | outDegree (Vertex* passed_vertex)

Return the outdegree of passed_vertex (see outIncidentEdges()).

int | maxDegree () const

Return the maximum degree of any vertex in the graph. O(n)

int | minDegree () const

Return the minimum degree of any vertex in the graph. O(n)

Sequence<Edge*> | pathEdges (Sequence<Vertex*>)

Given a sequence of vertices, return a sequence of binary edges that connect the vertices if one exists, otherwise return an empty sequence. O(n)

Sequence<Vertex*> | pathVertices (Sequence<Edge*>)

Given a sequence of binary edges, return the sequence of vertices that connect the vertices if one exists, otherwise return an empty sequence. O(n)

Sequence<Edge*> | treePath() ertex* descendent, Vertex* ancestor)

Assuming that the pred attribute has been set by a search or shortest paths algorithm, retrive a path of edges from the descendent to the ancestor via predecessor pointers. If the vertices do not lie on the same branch of the depth-first or shortest paths tree, return an empty sequence. O(n)

Vertex* | addSubgraph (Graph *owner, List<Vertex*>* l) = 0;

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 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.

Set<Vertex*> | dissolveSubgraph (Vertex *sv) = 0;

If 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.

Next: Adjacency Matrices Up: Graph Previous: Input Graph Language