path: root/labb8/lib/StanfordCPPLib/graph.h

/*
 * 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