getNeighbors(std::string node) const;
/*
* Method: toString
* Usage: string str = g.toString();
* ---------------------------------
* Converts the graph to a printable string representation.
*/
std::string toString();
/*
* Friend method: writeNodeData
* Usage: writeNodeData(os, NodeType *node);
* -----------------------------------------
* Writes the data for the node to the output stream. The default
* implementation of this method is empty. Clients that want to store
* other fields from the node must override this method so that it
* writes that data in a form that scanNodeData can read.
*/
virtual void writeNodeData(std::ostream &, NodeType *) const {
/* Empty */
}
/*
* Friend method: writeArcData
* Usage: writeArcData(os, ArcType *arc);
* --------------------------------------
* Writes the data for the arc to the output stream. The default
* implementation of this method is empty. Clients that want to store
* other fields from the arc must override this method so that it writes
* that data in a form that scanArcData can read.
*/
virtual void writeArcData(std::ostream &, ArcType *) const {
/* Empty */
}
/*
* Friend method: scanGraphEntry
* Usage: while (g.scanGraphEntry(scanner)) { }
* --------------------------------------------
* This method reads one "entry" for the graph, which is either a node
* description or an arc description. The scanGraphEntry
* method returns true if it reads an entry, and
* false at the end of file or at text that cannot be
* recognized as a graph entry.
*
* Node entries consist of the name of a node (which may be quoted
* if it contains special characters), optionally followed by data for
* the node. Arc descriptions have one of the following forms:
*
*
* n1 -> n2
* n1 - n2
*
*
* either of which can be followed by data for the arc. The first form
* creates a single directed arc; the second creates two arcs, one in
* each direction.
*
* Clients who want to read node or arc data must override the empty
* versions of scanNodeData and scanArcData
* included in this interface.
*/
virtual bool scanGraphEntry(TokenScanner & scanner);
/*
* Friend method: scanNodeData
* Usage: scanNodeData(scanner, NodeType *node);
* ---------------------------------------------
* Reads the data for the specified node from the scanner. The default
* implementation of this method is empty. Clients that want to initialize
* other fields in the node from the token stream must override this method.
*/
virtual void scanNodeData(TokenScanner &, NodeType *) {
/* Empty */
}
/*
* Friend method: scanArcData
* Usage: scanArcData(scanner, ArcType *forward, ArcType *backward);
* -----------------------------------------------------------------
* Reads the data for an arc from the scanner. The forward
* argument points to the arc in the forward direction. If the arc is
* undirected, backward points to the reverse arc; for
* directed arcs, the backward pointer is NULL.
* The default implementation of this method is empty. Clients that want
* to initialize other fields in the arc must override this method so
* that it initializes one or both arc, as appropriate.
*/
virtual void scanArcData(TokenScanner &, ArcType *, ArcType *) {
/* Empty */
}
/* Private section */
/**********************************************************************/
/* Note: Everything below this point in the file is logically part */
/* of the implementation and should not be of interest to clients. */
/**********************************************************************/
/*
* Private class: GraphComparator
* ------------------------------
* This template class establishes the ordering for nodes and arcs.
* Nodes are processed in alphabetical order by node name; arcs are
* compared in much the same way, looking first at the start node and
* then continuing on to look at the finish node if the start nodes
* match. These functions, however, indicate equality only if the
* arguments are identical, in the sense that they are at the same
* address. If two distinct arcs, for example, connect the same pair
* of nodes (which is perfectly legal in the graph abstraction and can
* be used, for example, to represent multiple modes of travel between
* two nodes), those arcs are not the same.
*/
class GraphComparator {
public:
bool operator()(NodeType *n1, NodeType *n2) {
return compare(n1, n2) < 0;
}
bool operator()(ArcType *a1, ArcType *a2) {
return compare(a1, a2) < 0;
}
};
private:
/* Instance variables */
Set nodes; /* The set of nodes in the graph */
Set arcs; /* The set of arcs in the graph */
Map nodeMap; /* A map from names to nodes */
GraphComparator comparator; /* The comparator for this graph */
/*
* Functions: operator=, copy constructor
* --------------------------------------
* These functions are part of the public interface of the class but are
* defined here to avoid adding confusion to the Graph class.
*/
public:
Graph & operator=(const Graph & src);
Graph(const Graph & src);
static int compare(NodeType *n1, NodeType *n2) {
if (n1 == n2) return 0;
if (n1->name < n2->name) return -1;
if (n1->name > n2->name) return +1;
return (n1 < n2) ? -1 : +1;
}
static int compare(ArcType *a1, ArcType *a2) {
if (a1 == a2) return 0;
NodeType *n1 = a1->start;
NodeType *n2 = a2->start;
if (n1 != n2) return compare(n1, n2);
n1 = a1->finish;
n2 = a2->finish;
if (n1 != n2) return compare(n1, n2);
return (a1 < a2) ? -1 : +1;
}
private:
void deepCopy(const Graph & src);
NodeType *getExistingNode(std::string name) const;
NodeType *scanNode(TokenScanner & scanner);
};
extern void error(std::string msg);
/*
* Implementation notes: Graph constructor
* ---------------------------------------
* Even though the body of the Graph constructor is empty, important
* work is done by the initializers, which ensure that the nodes and
* arcs set are given the correct comparison functions.
*/
template
Graph::Graph() {
comparator = GraphComparator();
nodes = Set(comparator);
arcs = Set(comparator);
}
/*
* Implementation notes: Graph destructor
* --------------------------------------
* The destructor must free all heap storage used by this graph to
* represent the nodes and arcs. The clear metho must also reclaim
* this memory, which means that the destructor can simply call
* clear to do the work.
*/
template
Graph::~Graph() {
clear();
}
/*
* Implementation notes: size, isEmpty
* -----------------------------------
* These methods are defined in terms of the node set, so the implementation
* simply forwards the request there. Note that it is impossible for a
* graph to have arcs if it has no nodes.
*/
template
int Graph::size() const {
return nodes.size();
}
template
bool Graph::isEmpty() const {
return nodes.isEmpty();
}
/*
* Implementation notes: clear
* ---------------------------
* The implementation of clear first frees the nodes and arcs in
* their respective sets and then uses the Set class clear method
* to ensure that these sets are empty.
*/
template
void Graph::clear() {
foreach (NodeType *node in nodes) {
delete node;
}
foreach (ArcType *arc in arcs) {
delete arc;
}
arcs.clear();
nodes.clear();
nodeMap.clear();
}
/*
* Implementation notes: addNode
* -----------------------------
* The addNode method appears in two forms: one that creates a node
* from its name and one that assumes that the client has created
* the new node. In each case, the implementation must add the node
* the set of nodes for the graph and add the name-to-node association
* to the node map.
*/
template
NodeType *Graph::addNode(std::string name) {
NodeType *node = new NodeType();
node->arcs = Set(comparator);
node->name = name;
return addNode(node);
}
template
NodeType *Graph::addNode(NodeType *node) {
if (nodeMap.containsKey(node->name)) {
error("addNode: node " + node->name + " already exists");
}
nodes.add(node);
nodeMap[node->name] = node;
return node;
}
/*
* Implementation notes: removeNode
* --------------------------------
* The removeNode method must remove the specified node but must
* also remove any arcs in the graph containing the node. To avoid
* changing the node set during iteration, this implementation creates
* a vector of arcs that require deletion.
*/
template
void Graph::removeNode(std::string name) {
removeNode(getExistingNode(name));
}
template
void Graph::removeNode(NodeType *node) {
Vector toRemove;
foreach (ArcType *arc in arcs) {
if (arc->start == node || arc->finish == node) {
toRemove.add(arc);
}
}
foreach (ArcType *arc in toRemove) {
removeArc(arc);
}
nodes.remove(node);
}
/*
* Implementation notes: getNode, getExistingNode
* ----------------------------------------------
* The getNode method simply looks up the name in the map, which correctly
* returns NULL if the name is not found. Other methods in the
* implementation call the private method getExistingNode instead,
* which checks for a NULL value and signals an error.
*/
template
NodeType *Graph::getNode(std::string name) const {
return nodeMap.get(name);
}
template
NodeType *Graph::getExistingNode(std::string name) const {
NodeType *node = nodeMap.get(name);
if (node == NULL) error("Graph class: No node named " + name);
return node;
}
/*
* Implementation notes: addArc
* ----------------------------
* The addArc method appears in three forms, as described in the
* interface. The code for each form of the method, however, is
* quite straightforward.
*/
template
ArcType *Graph::addArc(std::string s1, std::string s2) {
return addArc(getExistingNode(s1), getExistingNode(s2));
}
template
ArcType *Graph::addArc(NodeType *n1, NodeType *n2) {
ArcType *arc = new ArcType();
arc->start = n1;
arc->finish = n2;
return addArc(arc);
}
template
ArcType *Graph::addArc(ArcType *arc) {
arc->start->arcs.add(arc);
arcs.add(arc);
return arc;
}
/*
* Implementation notes: removeArc
* -------------------------------
* These methods remove arcs from the graph, which is ordinarily simply
* a matter of removing the arc from two sets: the set of arcs in the
* graph as a whole and the set of arcs in the starting node. The
* methods that remove an arc specified by its endpoints, however,
* must take account of the fact that there might be more than one
* such arc and delete all of them.
*/
template
void Graph::removeArc(std::string s1, std::string s2) {
removeArc(getExistingNode(s1), getExistingNode(s2));
}
template
void Graph::removeArc(NodeType *n1, NodeType *n2) {
Vector toRemove;
foreach (ArcType *arc in arcs) {
if (arc->start == n1 && arc->finish == n2) {
toRemove.add(arc);
}
}
foreach (ArcType *arc in toRemove) {
removeArc(arc);
}
}
template
void Graph::removeArc(ArcType *arc) {
arc->start->arcs.remove(arc);
arcs.remove(arc);
}
/*
* Implementation notes: isConnected
* ---------------------------------
* Node n1 is connected to n2 if any of the arcs leaving n1 finish at n2.
* The two versions of this method allow nodes to be specified either as
* node pointers or by name.
*/
template
bool Graph::isConnected(NodeType *n1, NodeType *n2) const {
foreach (ArcType *arc in n1->arcs) {
if (arc->finish == n2) return true;
}
return false;
}
template
bool Graph::isConnected(std::string s1,
std::string s2) const {
return isConnected(getExistingNode(s1), getExistingNode(s2));
}
/*
* Implementation notes: getNodeSet, getArcSet
* -------------------------------------------
* These methods simply return the set requested by the client. The
* sets are returned by reference for efficiency, because doing so
* eliminates the need to copy the set.
*/
template
const Set & Graph::getNodeSet() const {
return nodes;
}
template
const Set & Graph::getArcSet() const {
return arcs;
}
template
const Set &
Graph::getArcSet(NodeType *node) const {
return node->arcs;
}
template
const Set &
Graph::getArcSet(std::string name) const {
return getArcSet(getExistingNode(name));
}
/*
* Implementation notes: getNeighbors
* ----------------------------------
* This implementation recomputes the set each time, which is reasonably
* efficient if the degree of the node is small.
*/
template
const Set
Graph::getNeighbors(NodeType *node) const {
Set nodes = Set(comparator);
foreach (ArcType *arc in node->arcs) {
nodes.add(arc->finish);
}
return nodes;
}
template
const Set
Graph::getNeighbors(std::string name) const {
return getNeighbors(getExistingNode(name));
}
/*
* Implementation notes: operator=, copy constructor
* -------------------------------------------------
* These methods ensure that copying a graph creates an entirely new
* parallel structure of nodes and arcs.
*/
template
Graph
& Graph::operator=(const Graph & src) {
if (this != &src) {
clear();
deepCopy(src);
}
return *this;
}
template
Graph::Graph(const Graph & src) {
nodes = Set(comparator);
arcs = Set(comparator);
deepCopy(src);
}
/*
* Private method: deepCopy
* ------------------------
* Common code factored out of the copy constructor and operator= to
* copy the contents from the other graph.
*/
template
void Graph::deepCopy(const Graph & src) {
foreach (NodeType *oldNode in src.nodes) {
NodeType *newNode = new NodeType();
*newNode = *oldNode;
newNode->arcs.clear();
addNode(newNode);
}
foreach (ArcType *oldArc in src.arcs) {
ArcType *newArc = new ArcType();
*newArc = *oldArc;
newArc->start = getExistingNode(oldArc->start->name);
newArc->finish = getExistingNode(oldArc->finish->name);
addArc(newArc);
}
}
template
std::string Graph::toString() {
ostringstream os;
os << *this;
return os.str();
}
/*
* Implementation notes: scanGraphEntry
* ------------------------------------
* The scanGraphEntry and its helper methods take a scanner that is
* initialized to the input stream and has the options ignoreWhitespace,
* scanStrings, and scanNumbers set.
*/
template
bool Graph::scanGraphEntry(TokenScanner & scanner) {
NodeType *n1 = scanNode(scanner);
if (n1 == NULL) return false;
std::string op = scanner.nextToken();
if (op != "-" && op != "->") {
scanner.saveToken(op);
return true;
}
NodeType *n2 = scanNode(scanner);
if (n2 == NULL) error("scanGraphEntry: Missing node after " + op);
ArcType *forward = new ArcType();
forward->start = n1;
forward->finish = n2;
addArc(forward);
ArcType *backward = NULL;
if (op == "-") {
backward = new ArcType();
backward->start = n2;
backward->finish = n1;
addArc(backward);
}
scanArcData(scanner, forward, backward);
return true;
}
template
NodeType *Graph::scanNode(TokenScanner & scanner) {
std::string token = scanner.nextToken();
switch (scanner.getTokenType(token)) {
case WORD: break;
case STRING: token = scanner.getStringValue(token); break;
default: scanner.saveToken(token); return NULL;
}
NodeType *node = getNode(token);
if (node == NULL) {
node = new NodeType();
node->name = token;
scanNodeData(scanner, node);
addNode(node);
}
return node;
}
/*
* Implementation notes: << and >>
* -------------------------------
* The insertion and extraction operators for graphs are more complicated
* than for the standard collection types because the nodes and arcs can
* contain client-specific data. To ensure that this information is
* correctly written and read by these operators, clients must override
* the methods writeNodeData, writeArcData, scanNodeData, and scanArcData.
*/
template
std::ostream & operator<<(std::ostream & os,
const Graph & g) {
os << "{";
bool started = false;
foreach (NodeType *node in g.getNodeSet()) {
if (started) os << ", ";
writeGenericValue(os, node->name, false);
g.writeNodeData(os, node);
started = true;
}
foreach (ArcType *arc in g.getArcSet()) {
os << ", ";
writeGenericValue(os, arc->start->name, false);
os << " -> ";
writeGenericValue(os, arc->finish->name, false);
g.writeArcData(os, arc);
}
return os << "}";
}
template
std::istream & operator>>(std::istream & is, Graph & g) {
TokenScanner scanner(is);
scanner.ignoreWhitespace();
scanner.scanNumbers();
scanner.scanStrings();
scanner.addOperator("->");
std::string token = scanner.nextToken();
if (token != "{") error("operator >>: Missing {");
g.clear();
while (g.scanGraphEntry(scanner)) {
token = scanner.nextToken();
if (token == "}") {
scanner.saveToken(token);
} else if (token != ",") {
error("operator >>: Unexpected token " + token);
}
}
token = scanner.nextToken();
if (token != "}") error("operator >>: Missing }");
return is;
}
#endif