`class Graph<NodeType, ArcType>`

This class represents a directed, unweighted graph that allows you to parameterize the type of data that is stored at each node (vertex) and arc (edge). The NodeType and ArcType parameters indicate the structure type or class used for nodes and arcs, respectively. These types can contain any fields or methods required by the client, but must contain the following fields required by the Graph package itself:

The NodeType definition must include:

A parameterless constructor
A string field called name
A Set<ArcType*> field called arcs

The ArcType definition must include:

A parameterless constructor
A NodeType* field called start
A NodeType* field called finish

For most usage, the BasicGraph class may be preferable to this class. It contains a default implementation of the above types, named Vertex and Edge respectively, and provides additional members for convenience.

If you want to use this class to represent an undirected graph, doubly add each arc. For example, every time you call addArc(a, b);, also call addArc(b, a);. If you want to use this class to represent a weighted graph, one way to do so is to add a field such as cost to your ArcType and use it in your own graph algorithms.

The internal representation of this graph is an adjacency list, which is very efficient for iterating over neighbors of a given node, but less efficient for asking whether two given nodes are neighbors.

Until the 2014/10/20 version of the library, unlike with several of the other collections, you could not directly perform a for-each loop over a Graph. You can, however, for-each over the nodes by calling getNodeSet on the Graph, or over the arcs by calling getArcSet on the Graph. Since 2014/10/20 version of the library, performing a for-each loop over a Graph is supported and is equivalent to looping over the node set.

Note about pointers: Several Graph members return various pointers to nodes and arcs. Any such pointers returned are direct pointers to the internal structures inside of this graph. If the graph itself falls out of scope, is cleared, etc., or if the given node/arc is removed from the graph, this pointer will become invalid. Undefined behavior and crashes will result if you retain pointers to node/arcs that live on beyond the life span of the graph.

For the purposes of Big-Oh listing, some members are proportional to the number of nodes N, and some are proportional to the number of arcs A.

Constructor
Graph()	O(1)	Creates an empty `Graph` object.
Methods
addArc(`s1`, `s2`) addArc(`node1`, `node2`) addArc(`arc`)	O(log N + log A)	Adds an arc to the graph.
addNode(`name`) addNode(`node`)	O(log N)	Adds a node to the graph.
clear()	O(N + A)	Reinitializes the graph to be empty, freeing any heap storage.
getArcSet()	O(1)	Returns the set of all arcs in the graph.
getArcSet(`node`) getArcSet(`name`)	O(log N)	Returns the set of arcs that start at the specified node, which can be indicated either as a pointer or by name.
getNeighbors(`node`) getNeighbors(`name`)	O(log N)	Returns the set of nodes that are neighbors of the specified node, which can be indicated either as a pointer or by name.
getNode(`name`)	O(log N)	Looks up a node in the name table attached to the graph and returns a pointer to that node.
getNodeSet()	O(1)	Returns the set of all nodes in the graph.
isConnected(`node1`, `node2`) isConnected(`s1`, `s2`)	O(log N)	Returns `true` if the graph contains an arc from `n1` to `n2`.
isEmpty()	O(1)	Returns `true` if the graph contains no nodes or arcs.
removeArc(`s1`, `s2`) removeArc(`node1`, `node2`) removeArc(`arc`)	O(A + log N)	Removes an arc from the graph, where the arc can be specified in any of three ways: by the names of its endpoints, by the node pointers at its endpoints, or as an arc pointer.
removeNode(`name`) removeNode(`node`)	O(A + log N)	Removes a node from the graph, where the node can be specified either by its name or as a pointer value.
size()	O(1)	Returns the number of nodes in the graph.
toString()	O(N + A)	Converts the graph to a printable string representation.
Operators
`ostream` << `graph`	O(V + E)	Outputs the contents of the graph to the given output stream.
`istream` >> `graph`	O(V log V + E log E)	Reads the contents of the given input stream into the graph.

Constructor detail

Graph();

Creates an empty Graph object.

Usage:

Graph<NodeType,ArcType> g;

Method detail

int size() const;

Returns the number of nodes in the graph.

Usage:

int size = g.size();

bool isEmpty() const;

Returns true if the graph contains no nodes.

Usage:

if (g.isEmpty()) ...

void clear();

Reinitializes the graph to be empty of all nodes and arcs, freeing any heap storage. (The heap memory associated with all nodes and arcs that have been previously added to the graph will be freed.)

Usage:

g.clear();

NodeType* addNode(string name);
NodeType* addNode(NodeType* node);

Adds a node to the graph. The first version of this method creates a new node of the appropriate type and initializes its fields; the second assumes that the client has already created the node and simply adds it to the graph. Both versions of this method return a pointer to the node.

The nodes in a graph must have unique names. If this graph already contains a node with the given name, or if NULL is passed to the second version of this function, addNode throws an error.

The pointer returned is a direct pointer to the internal structure inside this graph, and will become invalid if the node is removed or if the graph itself falls out of scope.

Usage:

NodeType* node = g.addNode(name);
NodeType* node = g.addNode(node);

void removeNode(string name);
void removeNode(NodeType* node);

Removes a node from the graph, where the node can be specified either by its name or as a pointer value. Removing a node also removes all arcs that contain that node.

If NULL is passed to the second version of this function, or this graph does not contain the given node or a node with the given name, the function throws an error.

Usage:

g.removeNode(name);
g.removeNode(node);

NodeType* getNode(string name) const;

Looks up a node in the name table attached to the graph and returns a pointer to that node. If no node with the specified name exists, getNode returns NULL.

The pointer returned is a direct pointer to the internal structure inside this graph, and will become invalid if the node is removed or if the graph itself falls out of scope.

Usage:

NodeType* node = g.getNode(name);

ArcType* addArc(string s1, string s2);
ArcType* addArc(NodeType* n1, NodeType* n2);
ArcType* addArc(ArcType* arc);

Adds an arc to the graph. The endpoints of the arc can be specified either as strings indicating the names of the nodes or as pointers to the node structures. Alternatively, the client can create the arc structure explicitly and pass that pointer to the addArc method. All three of these versions return a pointer to the arc in case the client needs to capture this value. Note that it is allowed to have multiple arcs between the same pair of nodes.

When calling either of the two-parameter versions of addArc, if either of the nodes supplied is NULL or is not found in the graph, the function will throw an error.

The pointer returned is a direct pointer to the internal structure inside this graph, and will become invalid if the arc is removed or if the graph itself falls out of scope.

Usage:

g.addArc(s1, s2);
g.addArc(n1, n2);
g.addArc(arc);

void removeArc(string s1, string s2);
void removeArc(NodeType* n1, NodeType* n2);
void removeArc(ArcType* arc);

Removes an arc from the graph, where the arc can be specified in any of three ways: by the names of its endpoints, by the node pointers at its endpoints, or as an arc pointer.

When calling the single-parameter version of removeArc, only that single arc is removed. When calling either of the two-parameter versions of removeArc, if more than one arc connects the specified endpoints, all of them are removed.

When calling the single-parameter version of removeArc, if the arc supplied is NULL or is not found in the graph, calling this function will have no effect on the graph.

When calling either of the two-parameter versions of removeArc, if either of the nodes supplied is NULL or is not found in the graph, calling this function will have no effect on the graph.

Usage:

g.removeArc(s1, s2);
g.removeArc(n1, n2);
g.removeArc(arc);

bool isConnected(NodeType* n1, NodeType* n2) const;
bool isConnected(string s1, string s2) const;

Returns true if the graph contains an arc from n1 to n2. As in the addArc method, nodes can be specified either as node pointers or by name.

If either of the nodes supplied is NULL or is not found in the graph, the function will return false.

Usage:

if (g.isConnected(n1, n2)) ...
if (g.isConnected(s1, s2)) ...

const Set<NodeType* > & getNodeSet() const;

Returns the set of all nodes in the graph.

The pointers returned are direct pointers to the internal structures inside this graph, and will become invalid if any node is removed or if the graph itself falls out of scope.

Usage:

for (NodeType* node : g.getNodeSet()) ...

const Set<ArcType* > & getArcSet() const;
const Set<ArcType* > & getArcSet(NodeType* node) const;
const Set<ArcType* > & getArcSet(string name) const;

Returns the set of all arcs in the graph or, in the second and third forms, the arcs that start at the specified node, which can be indicated either as a pointer or by name.

When calling the two versions of this function that accept a node parameter, if the node supplied is NULL or is not found in the graph, the function will throw an error.

The pointers returned are direct pointers to the internal structures inside this graph, and will become invalid if any arc is removed or if the graph itself falls out of scope.

Usage:

for (ArcType* arc : g.getArcSet()) ...
for (ArcType* arc : g.getArcSet(node)) ...
for (ArcType* arc : g.getArcSet(name)) ...

const Set<NodeType* > getNeighbors(NodeType* node) const;
const Set<NodeType* > getNeighbors(string node) const;

Returns the set of nodes that are neighbors of the specified node, which can be indicated either as a pointer or by name.

If the node supplied is NULL or is not found in the graph, the function will throw an error.

The pointers returned are direct pointers to the internal structures inside this graph, and will become invalid if any node is removed or if the graph itself falls out of scope.

Usage:

for (NodeType* node : g.getNeighbors(node)) ...
for (NodeType* node : g.getNeighbors(name)) ...

string toString() const;

Converts the graph to a printable string representation, listing all node names followed by the start/finish of all arcs, such as "{A, B, C, D, E, A -> B, C -> A, D -> E}".

Usage:

string str = g.toString();