Programming Assignment 6 - Pickling Graphs

See the assignment turn-in page for instructions on turning in your assignment.

Several programming languages provide a facility to write data to a file and then read it in again, either by a later run of the same program or a different program. In Modula-3 such a facility is called pickling; in Java it's called serialization.

void 
pickle_graph(const std::string & fname, const graph_node * root);

graph_node * 
unpickle_graph(const std::string & fname, pickleable * (* pmaker)(void));

The fname argument gives the name of the file to which the graph will be pickled or from which the graph will be unpickled. The pmaker argument is a function that, when called, returns a new instance of the data stored in each graph node. Each file contains one graph. Any errors that occur during file operations should result in an informative error message and program termination.

The root argument to pickle_graph() is a node from the graph to pickle (despite the suggestive name, the graph need not be a tree). Only those nodes reachable from the root need to be pickled. Given a file name f, the node returned by unpickle_graph() should be the equivalent to the node passed into the most recent invocation of pickle_graph() with the same file name f.

A graph is constructed from nodes with the structure

struct graph_node {
  pickleable * data_ptr;
  std::vector<graph_node *> children;
  };

all nodes in a graph are graph_nodes. A graph node may have any number of children, including none; the left-to-right order of children in a graph node is significant. Edges are directed; they point to the children but not back to the parent. The file /export/home/class/cs-509/pa6/graph.h contains declarations for graph_node, pickle_graph(), and unpickle_graph().

The data stored in each graph node can be pickled and unpickled by calling the the member functions

void pickleable::pickle(std::ostream &);

void pickleable::unpickle(std::istream &);

The data to pickle is written to the given ostream; the data to unpickle is read from the given istream. These member functions are defined in /export/home/class/cs-509/pa6/pickle.h, included by graph.h.

The graph returned by unpickle_graph() should be equivalent to the graph passed into pickle_graph(). Two graphs are equivalent if there exists a one-to-one correspondence between the nodes and edges of one graph and the nodes and edges of the other graph.

Two nodes are equivalent if they have the same data and the their children are equivalent in the left-to-right order given in each node. Two edges are equivalent if the nodes at their heads and tails are equivalent.