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

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.

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 (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 (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 $(0\ldots n-1)$? O(1)

int rank (Edge* passed_edge)

Where does this edge rank in the current order of edges $(0\ldots m-1)$? 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.

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. $O(l\log n)$, 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 $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.

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.