<graph-pickling procedures>= (U->) [D->]
void
pickle_graph(const std::string & fname, const graph_node * root) {
if (root == NULL) {
std::cerr << "pickle_graph() called with null root.\n";
exit(EXIT_FAILURE);
}
node_list nodes;
listify_nodes(nodes, const_cast<graph_node *>(root));
assert(nodes.front() == root);
ofstream ofs(fname.c_str());
if (!ofs.good()) {
std::cerr << "Can't open \"" << fname << "\".\n";
exit(EXIT_FAILURE);
}
write_nodes(ofs, nodes);
ofs.close();
}
Definespickle_graph(links are to index).
The linear order imposed on the graph nodes doesn't matter much, as long as the root node is the first node in the order. A depth-first order works as well as any other, and it's simple to implement.
<graph-pickling procedures>+= (U->) [<-D->]
static void
listify_nodes(node_list & nodes, graph_node * root) {
if (find_index(nodes, root) > -1)
return;
nodes.push_back(root);
std::for_each(root->children.begin(), root->children.end(),
listify_nodes_helper(nodes));
}
Defineslistify_nodes(links are to index).
This functor implements an indirectly recursive call to listify_nodes().
It should be possible to use direct recursion, but apparently the STL freaks
out when parameter functions have reference parameters, and listify_nodes()
needs to have the node list passed by reference so changes to it are carried
outside of listify_nodes().
<graph-pickling functors>= (U->) [D->]
struct
listify_nodes_helper {
node_list & nodes;
listify_nodes_helper(node_list & nodes) : nodes(nodes) { }
void operator () (graph_node * gnp) {
if (gnp)
listify_nodes(nodes, gnp);
else {
std::cerr << "pickle graph called with null child pointer.\n";
exit(EXIT_FAILURE);
}
}
};
Defineslistify_nodes_helper(links are to index).
As discussed in the Design section, the pickle-file format consists of the node count followed by the node data followed by the child data.
<graph-pickling procedures>+= (U->) [<-D->]
static void
write_nodes(ostream & os, node_list & nodes) {
write_unsigned(os, nodes.size());
std::for_each(nodes.begin(), nodes.end(), pickle_data_helper(os));
std::for_each(nodes.begin(), nodes.end(), pickle_children_helper(os, nodes));
}
Defineswrite_nodes(links are to index).
Another simple functor implementing a function that should be called directly but for a reference parameter.
<graph-pickling functors>+= (U->) [<-D->]
struct
pickle_data_helper {
ostream & os;
pickle_data_helper(ostream & os) : os(os) { }
void operator () (node_list::value_type gnp) {
if (gnp->data_ptr != NULL)
gnp->data_ptr->pickle(os);
else {
std::cerr << "pickle_graph called with null data pointer.\n";
exit(EXIT_FAILURE);
}
}
};
Definespickle_data_helper(links are to index).
A functor to write a nodes' child information. This needs to be a functor because it uses three arguments, and the STL lets you wrap at most one extra argument.
<graph-pickling functors>+= (U->) [<-D]
<the child-pickling functor>
struct
pickle_children_helper {
ostream & os;
node_list & nodes;
pickle_children_helper(ostream & os, node_list & nodes)
: os(os), nodes(nodes) { }
void operator() (node_list::value_type gnp) {
const unsigned child_cnt = gnp->children.size();
write_unsigned(os, child_cnt);
std::for_each(gnp->children.begin(), gnp->children.end(),
pickle_child_helper(os, nodes));
}
};
Definespickle_children_helper(links are to index).
A functor that maps a node pointer to its index and writes the index to the pickle file.
<the child-pickling functor>= (<-U)
struct
pickle_child_helper {
ostream & os;
node_list & nodes;
pickle_child_helper(ostream & os, node_list & nodes)
: os(os), nodes(nodes) { }
void operator() (graph_node * const gnp) {
if (gnp)
write_unsigned(os, find_index(nodes, gnp));
else {
std::cerr << "pickle graph called with null child pointer.\n";
exit(EXIT_FAILURE);
}
}
};
Definespickle_child_helper(links are to index).
The node-list is implemented as a vector of graph-node pointers.
<graph-pickling data types>= (U->) typedef std::vector<graph_node *> node_list;
Definesnode_list(links are to index).
Search the given node list for the given graph-node pointer, returning the index of the pointer if it's found or -1 if it isn't.
<graph-pickling procedures>+= (U->) [<-D->]
static int
find_index(const node_list & nodes, const graph_node * gnp) {
node_list::const_iterator
e = nodes.end(),
f = std::find(nodes.begin(), e, gnp);
return (f == e) ? -1 : f - nodes.begin();
}
Definesfind_index(links are to index).
Write an unsigned integer to the pickle file. Write the integer twice to provide a redundant safety check when reading it from the file.
<graph-pickling procedures>+= (U->) [<-D]
static void
write_unsigned(ostream & os, unsigned i) {
unsigned p[2] = { i, i };
os.write(reinterpret_cast<char *>(p), sizeof(p));
}
Defineswrite_unsigned(links are to index).
<pickle-graph.cc>=
#include <fstream>
#include <iostream>
#include <map>
#include <algorithm>
#include "graph.h"
using std::ostream;
using std::ofstream;
<graph-pickling data types>
// Deja vu c++ style.
static void listify_nodes(node_list &, graph_node *);
static void write_unsigned(ostream &, unsigned);
static void write_nodes(ostream &, node_list &);
static int find_index(const node_list &, const graph_node *);
<graph-pickling functors>
<graph-pickling procedures>
Definespickle-graph.cc(links are to index).
<unpickle-graph procedures>= (U->) [D->]
graph_node *
unpickle_graph(const std::string & fname, pfactory pmaker) {
ifstream ifs(fname.c_str());
if (!ifs.good()) {
std::cerr << "Can't open \"" << fname << "\".\n";
exit(EXIT_FAILURE);
}
graph_node * const root = read_nodes(ifs, pmaker);
ifs.close();
return root;
}
Definesunpickle_node(links are to index).
The first half of the pickle file contains the node data, and the second half contains the child data. The firs node in the file is the root of the graph.
<unpickle-graph procedures>+= (U->) [<-D->]
static graph_node *
read_nodes(istream & is, pfactory pmaker) {
const unsigned node_cnt = read_unsigned(is);
if (node_cnt == 0)
return 0;
node_list nodes;
for (unsigned i = 0; i < node_cnt; i++)
nodes.push_back(read_node(is, pmaker));
read_children(is, nodes);
return nodes[0];
}
Definesread_nodes(links are to index).
Read a node's data from the pickle file and return it in a new graph node.
<unpickle-graph procedures>+= (U->) [<-D->]
static graph_node *
read_node(istream & is, pfactory pmaker) {
pickleable * const pp = pmaker();
pp->unpickle(is);
return new graph_node(pp);
}
Definesread_node(links are to index).
The child data follows the node data in the pickle file, and is given in the same order as the node data.
<unpickle-graph procedures>+= (U->) [<-D->]
static void
read_children(istream & is, node_list & nodes) {
std::for_each(nodes.begin(), nodes.end(), read_children_helper(is, nodes));
}
Definesread_children(links are to index).
Each nodes child information is stored as a count followed by node indices,
which are translated into node pointers using nodes. A functor is best
here because three arguments are required to read child data (a pointer to a
graph-node, the node list, and the input stream).
<unpickle-graph functors>= (U->)
struct
read_children_helper {
istream & is;
node_list & nodes;
read_children_helper(istream & is, node_list & nodes) : is(is), nodes(nodes) { }
void operator ()(node_list::value_type gnp) {
unsigned child_cnt = read_unsigned(is);
const unsigned node_cnt = nodes.size();
while (child_cnt-- > 0) {
const unsigned child_i = read_unsigned(is);
assert(child_i < node_cnt);
gnp->children.push_back(nodes[child_i]);
}
}
};
Definesread_children_helper(links are to index).
Read and return an unsigned integer from the pickle file. The integer has been written twice to provide a sanity check on the data in the file.
<unpickle-graph procedures>+= (U->) [<-D]
static unsigned
read_unsigned(istream & is) {
unsigned p[2] = { 1, 2 };
is.read(reinterpret_cast<char *>(p), sizeof(p));
assert(is.good());
assert(p[0] == p[1]);
return p[0];
}
Definesread_unsigned(links are to index).
Re-assembling a graph from the pickle file requires translating node indicies (which represent node order in the file) into node pointers. This is most easily done using a vecotr of graph-node pointers and pushing the nodes pointers into the vector in the same order as the nodes are given in the file. The translation is then just indexing.
Also define an abbreviation for the pickle-factory prototype.
<unpickle-graph data types>= (U->) typedef std::vector<graph_node *> node_list; typedef pickleable * (* pfactory)(void);
Definesnode_list,pfactory(links are to index).
<unpickle-graph.cc>=
#include <fstream>
#include <iostream>
#include <map>
#include <algorithm>
#include "graph.h"
using std::istream;
using std::ifstream;
<unpickle-graph data types>
// Deja vu, c++ style.
static graph_node * read_nodes(istream &, pfactory);
static unsigned read_unsigned(istream &);
static void read_children(istream &, node_list &);
static graph_node * read_node(istream &, pfactory);
<unpickle-graph functors>
<unpickle-graph procedures>
Definesrectangle.h(links are to index).
<main procedures>= (U->) [D->]
int
main(int argc, char * argv[]) {
<handle command-line options>
const graph_node * const root = read_graph(std::cin);
if (pickle)
pickle_graph(fname, root);
if (unpickle) {
const graph_node * const copy = unpickle_graph(fname, pickle_factory);
dvecvec iv1 = depth_first_flatten(root);
dvecvec iv2 = depth_first_flatten(copy);
if (iv1.size() != iv2.size()) {
std::cerr << "The pickled graph has " << iv2.size() << " nodes, but the "
<< "original graph had " << iv1.size() << " nodes.\n";
exit(EXIT_FAILURE);
}
assert(iv1 == iv2);
}
}
Definesmain(links are to index).
The command-line options are
-p - Pickle the graph read from std-in; the default is to both
pickle and unpickle.
-u - Unpickle a graph and compare it to the graph read from
std-in; the default is to both pickle and unpickle.
-f fname - Read or write the pickle-graph file named
fname; the default is to read or write the file named
my-graph.pkl.
<handle command-line options>= (<-U)
options opts;
opts['p'] = "false";
opts['u'] = "false";
opts['f'] = "my-graph.pkl";
const int i = get_options(argc, argv, opts);
if (i != argc) {
std::cerr << "Command format is \"" << argv[0] << "\".\n";
return EXIT_FAILURE;
}
const std::string fname = opts['f'];
bool pickle = strlen(opts['p']) == 4;
bool unpickle = strlen(opts['u']) == 4;
if (!pickle and !unpickle)
pickle = unpickle = true;
Graphs are input as a sequence of lines, each line describing a node in the graph.
<main procedures>+= (U->) [<-D->]
static graph_node *
read_graph(istream & is) {
gnp_list nodes;
while (read_row(is, nodes)) { }
return nodes[1];
}
Definesread_graph(links are to index).
Read a node description from the given input stream, storing the node in the given node list. Return true if a node description was read; false otherwise.
Each line of graph input is a sequence of space-separated numbers. The first number is the number of the node being defined. The second number is the count of children for the node. The node numbers of the children, if any, follow.
<main procedures>+= (U->) [<-D->]
static bool
read_row(istream & is, gnp_list & nodes) {
const unsigned parent_i = read_node(is, nodes);
if (!is.good())
return false;
assert(nodes.count(parent_i) == 1);
unsigned child_cnt;
is >> child_cnt;
assert(is.good());
while (child_cnt-- > 0) {
const int child_i = read_node(is, nodes);
assert(is.good());
assert(nodes.count(child_i) == 1);
nodes[parent_i]->children.push_back(nodes[child_i]);
}
return true;
}
Definesread_row(links are to index).
Read a node number from the given input stream, storing it in the given node list if it isn't already there. Return the node's number or 0 if there no node numbers were read.
<main procedures>+= (U->) [<-D->]
static int
read_node(istream & is, gnp_list & nodes) {
unsigned n;
is >> n;
if (!is.good())
return 0;
assert(n > 0);
if (nodes.count(n) == 0)
nodes[n] = new_graph_node();
return n;
}
Definesread_node(links are to index).
Create a new graph node with randomly generated data; return a pointer to the new node.
<main procedures>+= (U->) [<-D->]
static graph_node *
new_graph_node(void) {
return new graph_node(new pickled_str(rand()));
}
Definesnew_graph_node(links are to index).
Each graph node conatins a string representation of a random integer. The string is pickled in three parts: the size (plus the null byte), followed by the string (including the null byte) followed by the size again to allow for a redundancy check.
<main data structures>= (U->)
struct
pickled_str : public pickleable {
std::string str;
pickled_str(int i) {
char n[20];
snprintf(n, sizeof(n), "%d", i);
str = std::string(n);
}
void pickle(std::ostream & os) {
const unsigned s = str.length() + 1;
os.write(reinterpret_cast<const char *>(&s), sizeof(s));
os.write(str.c_str(), s);
os.write(reinterpret_cast<const char *>(&s), sizeof(s));
}
void unpickle(istream & is) {
unsigned len1, len2;
is.read(reinterpret_cast<char *>(&len1), sizeof(len1));
assert(len1 <= 20);
char n[20];
is.read(n, len1);
str = std::string(n);
is.read(reinterpret_cast<char *>(&len2), sizeof(len2));
assert(len1 == len2);
}
virtual ~pickled_str() { }
};
Definespickled_str(links are to index).
Create and return pickleable node-data. This is an abuse of the term "factory", but the intention is close.
<main procedures>+= (U->) [<-D->]
static pickleable *
pickle_factory(void) {
return new pickled_str(0);
}
Definespickle_factory(links are to index).
Do a depth-first flatten on the graph rooted at r. Return the linearized
node data in a vector. Each node's data is described by a vector; the first
(index 0) element is the node's data, the following elements contain the
children's data in the left-to-right order given by the children vector.
<main procedures>+= (U->) [<-D->]
static dvecvec
depth_first_flatten(const graph_node * r) {
dvecvec v;
gnp_list nodes;
depth_first_flatten(r, v, nodes);
return v;
}
Definesdepth_first_flatten(links are to index).
Flatten the tree rooted at r into the data vector v; using the list of
nodes nodes. If r is listed in nodes, it has been (or is being)
processed and needs no further processing.
<main procedures>+= (U->) [<-D->]
static void
depth_first_flatten(const graph_node * r, dvecvec & v, gnp_list & nodes) {
const gnp_list::iterator e = nodes.end();
const gnp_list::iterator f =
std::find_if(nodes.begin(), e, std::bind2nd(std::ptr_fun(ptr_match), r));
if (f != e)
return;
nodes[nodes.size()] = const_cast<graph_node *>(r);
v.push_back(children_data(r));
std::for_each(r->children.begin(), r->children.end(),
flatten_helper(v, nodes));
}
Definesdepth_first_flatten(links are to index).
Test for a match between two pointers.
<main procedures>+= (U->) [<-D->]
static bool
ptr_match(gnp_list::value_type p, const graph_node * gnp) {
return p.second == gnp;
}
Definesptr_match(links are to index).
A functor to help create a vector of children data. This needs to be a functor because the changes made to the vector needs to be passed by reference.
<main functors>= (U->) [D->]
struct
children_data_helper {
dvec & v;
children_data_helper(dvec & v) : v(v) { }
void operator () (graph_node * gnp) {
pickled_str * const pip = dynamic_cast<pickled_str *>(gnp->data_ptr);
assert(pip);
v.push_back(pip->str);
}
};
Defineschildren_data_helper(links are to index).
<main procedures>+= (U->) [<-D]
static dvec
children_data(const graph_node * gnp) {
dvec v;
std::for_each(gnp->children.begin(), gnp->children.end(),
children_data_helper(v));
return v;
}
Defineschildren_data(links are to index).
A functor to help recurse over a node's children.
<main functors>+= (U->) [<-D]
struct
flatten_helper {
dvecvec & v;
gnp_list & nodes;
flatten_helper(dvecvec & v, gnp_list & nodes) : v(v), nodes(nodes) { }
void operator () (const graph_node * gnp) {
depth_first_flatten(gnp, v, nodes);
}
};
Definesflatten_helper(links are to index).
<main.cc>=
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <map>
#include <algorithm>
#include <functional>
#include "graph.h"
#include "get-options.h"
using std::istream;
<main data structures>
typedef std::vector<std::string> dvec;
typedef std::vector<dvec> dvecvec;
typedef std::map<unsigned, graph_node *> gnp_list;
// deja vu, c++ style.
static dvec children_data(const graph_node *);
static int read_node(istream &, gnp_list &);
static bool read_row(istream &, gnp_list &);
static graph_node * read_graph(istream &);
static graph_node * new_graph_node(void);
static void depth_first_flatten(const graph_node *, dvecvec &, gnp_list &);
static dvecvec depth_first_flatten(const graph_node *);
static pickleable * pickle_factory(void);
static bool ptr_match(gnp_list::value_type, const graph_node *);
<main functors>
<main procedures>
Definesmain.cc(links are to index).
main.cc>: D1
pickle-graph.cc>: D1
unpickle-graph.cc>: D1
This page last modified on 28 April 2002.