`class Graph<NodeType,ArcType>`

This class represents a graph with the specified node and arc types. 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 public fields required by the Graph package itself: The NodeType definition must include: - A string field called name - A Set<ArcType *> field called arcs The ArcType definition must include: - A NodeType * field called start - A NodeType * field called finish

Constructor
Graph()	Creates an empty `Graph` object.
Methods
size()	Returns the number of nodes in the graph.
isEmpty()	Returns `true` if the graph is empty.
clear()	Reinitializes the graph to be empty, freeing any heap storage.
addNode(name) addNode(node)	Adds a node to the graph.
removeNode(name) removeNode(node)	Removes a node from the graph, where the node can be specified either by its name or as a pointer value.
getNode(name)	Looks up a node in the name table attached to the graph and returns a pointer to that node.
nodeExists(name)	Returns `true` if a node with the given name exists.
addArc(s1, s2) addArc(n1, n2) addArc(arc)	Adds an arc to the graph.
removeArc(s1, s2) removeArc(n1, n2) removeArc(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.
isConnected(n1, n2) isConnected(s1, s2)	Returns `true` if the graph contains an arc from `n1` to `n2`.
getNodeSet()	Returns the set of all nodes in the graph.
getArcSet() getArcSet(node) getArcSet(name)	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.
getNeighbors(node) getNeighbors(name)	Returns the set of nodes that are neighbors of the specified node, which can be indicated either as a pointer or by name.

Constructor detail

Graph();

Creates an empty Graph object.

Usage:

Graph<NodeType,ArcType> g;

Method detail

int size();

Returns the number of nodes in the graph.

Usage:

int size = g.size();

bool isEmpty();

Returns true if the graph is empty.

Usage:

if (g.isEmpty()) . . .

void clear();

Reinitializes the graph to be empty, freeing any heap storage.

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.

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.

Usage:

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

NodeType *getNode(string name);

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 signals an error.

Usage:

NodeType *node = g.getNode(name);

bool nodeExists(string name);

Returns true if a node with the given name exists.

Usage:

if (g.nodeExists(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.

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. If more than one arc connects the specified endpoints, all of them are removed.

Usage:

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

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

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.

Usage:

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

Set<NodeType *> & getNodeSet();

Returns the set of all nodes in the graph.

Usage:

foreach (NodeType *node in g.getNodeSet()) . . .

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

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.

Usage:

foreach (ArcType *arc in g.getArcSet()) . . .
foreach (ArcType *arc in g.getArcSet(node)) . . .
foreach (ArcType *arc in g.getArcSet(name)) . . .

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

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

Usage:

foreach (NodeType *node in g.getNeighbors(node)) . . .
foreach (NodeType *node in g.getNeighbors(name)) . . .