The SimpleCxxLib package

#include "graph.h"

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 fields required by the Graph package itself:

The NodeType definition must include:

The ArcType definition must include:

Constructor
Graph() Creates an empty Graph object.
Methods
addArc(s1, s2)
addArc(n1, n2)
addArc(arc) 		Adds an arc to the graph.
addNode(name)
addNode(node) 		Adds a node to the graph.
clear() Reinitializes the graph to be empty, freeing any heap storage.
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.
getNode(name) Looks up a node in the name table attached to the graph and returns a pointer to that node.
getNodeSet() Returns the set of all nodes in the graph.
isConnected(n1, n2)
isConnected(s1, s2) 		Returns true if the graph contains an arc from n1 to n2.
isEmpty() Returns true if the graph is empty.
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.
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.
size() Returns the number of nodes in the graph.
toString() Converts the graph to a printable string representation.

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

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.

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

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.

Usage:

foreach (NodeType *node in 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.

Usage:

foreach (ArcType *arc in g.getArcSet()) ...
foreach (ArcType *arc in g.getArcSet(node)) ...
foreach (ArcType *arc in 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.

Usage:

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

string toString();
Converts the graph to a printable string representation.

Usage:

string str = g.toString();