add initial files l8

1 files changed, 836 insertions, 0 deletions

diff --git a/labb8/lib/StanfordCPPLib/graph.h b/labb8/lib/StanfordCPPLib/graph.h
new file mode 100755
index 0000000..30fae8f
--- /dev/null
+++ b/labb8/lib/StanfordCPPLib/graph.h
@@ -0,0 +1,836 @@
+/*
+ * File: graph.h
+ * -------------
+ * This file exports a parameterized <code>Graph</code> class used
+ * to represent <b><i>graphs,</i></b> which consist of a set of
+ * <b><i>nodes</i></b> and a set of <b><i>arcs</i></b>.
+ */
+
+#ifndef _graph_h
+#define _graph_h
+
+#include <string>
+#include "map.h"
+#include "set.h"
+#include "tokenscanner.h"
+
+/*
+ * Class: Graph<NodeType,ArcType>
+ * ------------------------------
+ * This class represents a graph with the specified node and arc types.
+ * The <code>NodeType</code> and <code>ArcType</code> 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 <code>Graph</code>
+ * package itself:
+ *
+ * <p>The <code>NodeType</code> definition must include:
+ * <ul>
+ *   <li>A <code>string</code> field called <code>name</code>
+ *   <li>A <code>Set&lt;ArcType *&gt;</code> field called <code>arcs</code>
+ * </ul>
+ *
+ * <p>The <code>ArcType</code> definition must include:
+ * <ul>
+ *   <li>A <code>NodeType *</code> field called <code>start</code>
+ *   <li>A <code>NodeType *</code> field called <code>finish</code>
+ * </ul>
+ */
+
+template <typename NodeType,typename ArcType>
+class Graph {
+
+public:
+
+/*
+ * Constructor: Graph
+ * Usage: Graph<NodeType,ArcType> g;
+ * ---------------------------------
+ * Creates an empty <code>Graph</code> object.
+ */
+
+   Graph();
+
+/*
+ * Destructor: ~Graph
+ * ------------------
+ * Frees the internal storage allocated to represent the graph.
+ */
+
+   virtual ~Graph();
+
+/*
+ * Method: size
+ * Usage: int size = g.size();
+ * ---------------------------
+ * Returns the number of nodes in the graph.
+ */
+
+   int size() const;
+
+/*
+ * Method: isEmpty
+ * Usage: if (g.isEmpty()) ...
+ * ---------------------------
+ * Returns <code>true</code> if the graph is empty.
+ */
+
+   bool isEmpty() const;
+
+/*
+ * Method: clear
+ * Usage: g.clear();
+ * -----------------
+ * Reinitializes the graph to be empty, freeing any heap storage.
+ */
+
+   void clear();
+
+/*
+ * Method: addNode
+ * Usage: NodeType *node = g.addNode(name);
+ *        NodeType *node = g.addNode(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.
+ */
+
+   NodeType *addNode(std::string name);
+   NodeType *addNode(NodeType *node);
+
+/*
+ * Method: removeNode
+ * Usage: g.removeNode(name);
+ *        g.removeNode(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.
+ */
+
+   void removeNode(std::string name);
+   void removeNode(NodeType *node);
+
+/*
+ * Method: getNode
+ * Usage: NodeType *node = g.getNode(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, <code>getNode</code> returns <code>NULL</code>.
+ */
+
+   NodeType *getNode(std::string name) const;
+
+/*
+ * Method: addArc
+ * Usage: g.addArc(s1, s2);
+ *        g.addArc(n1, n2);
+ *        g.addArc(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 <code>addArc</code>
+ * method.  All three of these versions return a pointer to the arc in
+ * case the client needs to capture this value.
+ */
+
+   ArcType *addArc(std::string s1, std::string s2);
+   ArcType *addArc(NodeType *n1, NodeType *n2);
+   ArcType *addArc(ArcType *arc);
+
+/*
+ * Method: removeArc
+ * Usage: g.removeArc(s1, s2);
+ *        g.removeArc(n1, n2);
+ *        g.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.  If more than one arc
+ * connects the specified endpoints, all of them are removed.
+ */
+
+   void removeArc(std::string s1, std::string s2);
+   void removeArc(NodeType *n1, NodeType *n2);
+   void removeArc(ArcType *arc);
+
+/*
+ * Method: isConnected
+ * Usage: if (g.isConnected(n1, n2)) ...
+ *        if (g.isConnected(s1, s2)) ...
+ * -------------------------------------
+ * Returns <code>true</code> if the graph contains an arc from
+ * <code>n1</code> to <code>n2</code>.  As in the <code>addArc</code>
+ * method, nodes can be specified either as node pointers or by name.
+ */
+
+   bool isConnected(NodeType *n1, NodeType *n2) const;
+   bool isConnected(std::string s1, std::string s2) const;
+
+/*
+ * Method: getNodeSet
+ * Usage: foreach (NodeType *node in g.getNodeSet()) ...
+ * -----------------------------------------------------
+ * Returns the set of all nodes in the graph.
+ */
+
+   const Set<NodeType *> & getNodeSet() const;
+
+/*
+ * Method: getArcSet
+ * Usage: foreach (ArcType *arc in g.getArcSet()) ...
+ *        foreach (ArcType *arc in g.getArcSet(node)) ...
+ *        foreach (ArcType *arc in g.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.
+ */
+
+   const Set<ArcType *> & getArcSet() const;
+   const Set<ArcType *> & getArcSet(NodeType *node) const;
+   const Set<ArcType *> & getArcSet(std::string name) const;
+
+/*
+ * Method: getNeighbors
+ * Usage: foreach (NodeType *node in g.getNeighbors(node)) ...
+ *        foreach (NodeType *node in g.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.
+ */
+
+   const Set<NodeType *> getNeighbors(NodeType *node) const;
+   const Set<NodeType *> 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 <code>scanGraphEntry</code>
+ * method returns <code>true</code> if it reads an entry, and
+ * <code>false</code> at the end of file or at text that cannot be
+ * recognized as a graph entry.
+ *
+ * <p>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:
+ *
+ *<pre>
+ *    n1 -> n2
+ *    n1 - n2
+ *</pre>
+ *
+ * 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.
+ *
+ * <p>Clients who want to read node or arc data must override the empty
+ * versions of <code>scanNodeData</code> and <code>scanArcData</code>
+ * 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 <code>forward</code>
+ * argument points to the arc in the forward direction.  If the arc is
+ * undirected, <code>backward</code> points to the reverse arc; for
+ * directed arcs, the <code>backward</code> pointer is <code>NULL</code>.
+ * 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<NodeType *> nodes;                 /* The set of nodes in the graph */
+   Set<ArcType *> arcs;                   /* The set of arcs in the graph  */
+   Map<std::string, NodeType *> 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 <typename NodeType,typename ArcType>
+Graph<NodeType,ArcType>::Graph() {
+   comparator = GraphComparator();
+   nodes = Set<NodeType *>(comparator);
+   arcs = Set<ArcType *>(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 <typename NodeType,typename ArcType>
+Graph<NodeType,ArcType>::~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 <typename NodeType,typename ArcType>
+int Graph<NodeType,ArcType>::size() const {
+   return nodes.size();
+}
+
+template <typename NodeType,typename ArcType>
+bool Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+void Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+NodeType *Graph<NodeType,ArcType>::addNode(std::string name) {
+   NodeType *node = new NodeType();
+   node->arcs = Set<ArcType *>(comparator);
+   node->name = name;
+   return addNode(node);
+}
+
+template <typename NodeType,typename ArcType>
+NodeType *Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+void Graph<NodeType,ArcType>::removeNode(std::string name) {
+   removeNode(getExistingNode(name));
+}
+
+template <typename NodeType,typename ArcType>
+void Graph<NodeType,ArcType>::removeNode(NodeType *node) {
+   Vector<ArcType *> 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 <typename NodeType,typename ArcType>
+NodeType *Graph<NodeType,ArcType>::getNode(std::string name) const {
+   return nodeMap.get(name);
+}
+
+template <typename NodeType,typename ArcType>
+NodeType *Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+ArcType *Graph<NodeType,ArcType>::addArc(std::string s1, std::string s2) {
+   return addArc(getExistingNode(s1), getExistingNode(s2));
+}
+
+template <typename NodeType,typename ArcType>
+ArcType *Graph<NodeType,ArcType>::addArc(NodeType *n1, NodeType *n2) {
+   ArcType *arc = new ArcType();
+   arc->start = n1;
+   arc->finish = n2;
+   return addArc(arc);
+}
+
+template <typename NodeType,typename ArcType>
+ArcType *Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+void Graph<NodeType,ArcType>::removeArc(std::string s1, std::string s2) {
+   removeArc(getExistingNode(s1), getExistingNode(s2));
+}
+
+template <typename NodeType,typename ArcType>
+void Graph<NodeType,ArcType>::removeArc(NodeType *n1, NodeType *n2) {
+   Vector<ArcType *> toRemove;
+   foreach (ArcType *arc in arcs) {
+      if (arc->start == n1 && arc->finish == n2) {
+         toRemove.add(arc);
+      }
+   }
+   foreach (ArcType *arc in toRemove) {
+      removeArc(arc);
+   }
+}
+
+template <typename NodeType,typename ArcType>
+void Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+bool Graph<NodeType,ArcType>::isConnected(NodeType *n1, NodeType *n2) const {
+   foreach (ArcType *arc in n1->arcs) {
+      if (arc->finish == n2) return true;
+   }
+   return false;
+}
+
+template <typename NodeType,typename ArcType>
+bool Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+const Set<NodeType *> & Graph<NodeType,ArcType>::getNodeSet() const {
+   return nodes;
+}
+
+template <typename NodeType,typename ArcType>
+const Set<ArcType *> & Graph<NodeType,ArcType>::getArcSet() const {
+   return arcs;
+}
+
+template <typename NodeType,typename ArcType>
+const Set<ArcType *> &
+      Graph<NodeType,ArcType>::getArcSet(NodeType *node) const {
+   return node->arcs;
+}
+
+template <typename NodeType,typename ArcType>
+const Set<ArcType *> &
+      Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+const Set<NodeType *>
+          Graph<NodeType,ArcType>::getNeighbors(NodeType *node) const {
+   Set<NodeType *> nodes = Set<NodeType *>(comparator);
+   foreach (ArcType *arc in node->arcs) {
+      nodes.add(arc->finish);
+   }
+   return nodes;
+}
+
+template <typename NodeType,typename ArcType>
+const Set<NodeType *>
+          Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+Graph<NodeType,ArcType>
+           & Graph<NodeType,ArcType>::operator=(const Graph & src) {
+   if (this != &src) {
+      clear();
+      deepCopy(src);
+   }
+   return *this;
+}
+
+template <typename NodeType,typename ArcType>
+Graph<NodeType,ArcType>::Graph(const Graph & src) {
+   nodes = Set<NodeType *>(comparator);
+   arcs = Set<ArcType *>(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 <typename NodeType,typename ArcType>
+void Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+std::string Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+bool Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+NodeType *Graph<NodeType,ArcType>::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 <typename NodeType,typename ArcType>
+std::ostream & operator<<(std::ostream & os,
+                          const Graph<NodeType,ArcType> & 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 <typename NodeType,typename ArcType>
+std::istream & operator>>(std::istream & is, Graph<NodeType,ArcType> & 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