Consider the following rewrite of the Graph class:
We begin with the usual shrouding of header files to prevent unnecessary inclusions:
//voidgraph.h #ifndef INCLUDE_VOIDGRAPH #define INCLUDE_VOIDGRAPH #ifndef INCLUDE_NODE #include "node.h" #endif #ifndef INCLUDE_EDGE #include "edge.h" #endif #ifndef INCLUDE_GNODEPTRBAG #include "gnodeptrbag.h" #endif #ifndef INCLUDE_GEDGEPTRBAG #include "gedgeptrbag.h" #endif #ifndef BOX_H #include "box.h" #endif #ifndef CIRCLE_H #include "circle.h" #endif
We forward define a few relevant classes:
class Graph; class Gedge; class ostream; class istream;
Next, we typedef what we will call access methods that will enable us to understand our void * data:
typedef void *Arbent; typedef int(* EQ_FN)(Arbent,Arbent); //Are object types the same? typedef ostream&(* DISP_FN)(ostream&, Arbent); //How do we display this type? typedef void(* ENTRY_FN)(Arbent *,Arbent); //How do we type the data?
We then define the Gnode and Gedge classes:
class Gnode : public Node{
friend Graph;
private:
GedgePtrBag d_edges;
Gnode(const Gnode&); //not implemented
Gnode& operator=(const Gnode&); //not implemented
Gnode(Pixel foreground_color_in,
Pixel background_color_in,
Pixel inside_color_in,
Pixel border_color_in,
Display *display_in,
Drawable drawable_in,
GC gc_in,
Pixmap pixmap_in,
Pixmap pixmap2_in,
float node_radius_in,
Vertex *node_center_in,
const char *name_in,
EQ_FN equal_in,DISP_FN show_in,ENTRY_FN entry_in,
Arbent data_in);
~Gnode();
void add(Gedge *edgeptr);
void remove(Gedge *edgeptr);
//add new data
CIRCLE *C;
Vertex node_center;
float node_radius;
EQ_FN equal;
DISP_FN show;
ENTRY_FN entry;
Arbent data;
public:
Vertex *center(){return &node_center;};
const GedgePtrBag& edges() const;
};
class Gedge : public Edge{
friend Graph;
private:
BOX *E;
EQ_FN equal;
DISP_FN show;
ENTRY_FN entry;
Arbent data;
Gnode *d_from_p;
Gnode *d_to_p;
Gedge(const Gedge&); //not implemented
Gedge& operator=(const Gedge&); //not implemented
Gedge(Pixel foreground_color_in,
Pixel background_color_in,
Pixel inside_color_in,
Pixel border_color_in,
Display *display_in,
Drawable drawable_in,
GC gc_in,
Pixmap pixmap_in,
Pixmap pixmap2_in,
Gnode *from,
Gnode *to,
EQ_FN equal_in,DISP_FN show_in,ENTRY_FN entry_in,
double weight,
Arbent data_in);
~Gedge();
public:
Gnode *from();
Gnode *to();
};
Finally, we define the Graph class:
class Graph{
friend istream& operator>>(istream& in, Graph& A);
friend istream& operator>>(istream& in, Graph* A);
friend ostream& operator<<(ostream& out,const Graph& A);
friend ostream& operator<<(ostream& out,const Graph* A);
private:
GnodePtrBag d_nodes;
GedgePtrBag d_edges;
Pixel foreground_color;
Pixel background_color;
Pixel node_inside_color;
Pixel node_border_color;
Pixel edge_inside_color;
Pixel edge_border_color;
Display *display;
Drawable drawable;
GC gc;
Pixmap pixmap;
Pixmap pixmap2;
float node_radius;
EQ_FN edge_equal,node_equal;
DISP_FN edge_show,node_show;
ENTRY_FN edge_entry,node_entry;
Vertex node_center;
Graph(const Graph&);
Graph& operator=(const Graph&);
public:
Graph(EQ_FN edge_equal_in,DISP_FN edge_show_in,ENTRY_FN edge_entry_in,
EQ_FN node_equal_in,DISP_FN node_show_in,ENTRY_FN node_entry_in,
float radius_in,Vertex node_center_in, //node circle
Pixel in_foreground_color, //colors
Pixel in_background_color,
Pixel *graph_colors,
Display *display_in, //graphics
Drawable drawable_in,
Pixmap pixmap_in,
Pixmap pixmap2_in,
GC gc_in);
~Graph();
Gnode *addNode(const char *nodeName,float x,float y,Arbent data);
Gnode *findNode(const char *nodeName);
void removeNode(Gnode *node);
Gedge *addEdge(Gnode *from,Gnode *to,double weight,Arbent data);
Gedge *findEdge(Gnode *from,Gnode *to);
void removeEdge(Gedge *edge);
const GnodePtrBag& nodes() const;
const GedgePtrBag& edges() const;
istream& grab(istream& in);
ostream& print(ostream& out) const;
int NumberNodes(void);
int NumberEdges(void);
Graph& FillData(Arbent node_data,int size_node,
Arbent edge_data,int size_edge);
Graph& draw(Drawable D);
Graph& erase(Drawable D);
Graph& translate(int xoffset,int yoffset);
Graph& rotate(float axis_x,float axis_y,float angle);
Graph& scale(float scale_factor);
Graph& CenteredScale(float scale_factor);
Graph& ScaleTranslate(float scale_factor,int xoffset,int yoffset);
Graph& find_center(Vertex *V);
Graph& ReadInputFile(char *filename);
Graph& GenerateRandomGraph(char *filename);
};
#endif
As mentioned above, the most significant additions are the typedefs
typedef void *Arbent; typedef int(* EQ_FN)(Arbent,Arbent); //Are object types the same? typedef ostream&(* DISP_FN)(ostream&, Arbent); //How do we display this type? typedef void(* ENTRY_FN)(Arbent *,Arbent); //How do we type the data?
which allow us to handle the void * data. There are 3 new functions which enable us to print the unknown data (typedef ostream&(* DISP_FN)(ostream&, Arbent)), check to see if two data values are equal (typedef int(* EQ_FN)(Arbent,Arbent)), and input unknown data (void(* ENTRY_FN)(Arbent *,Arbent) ).
Most of the implementation code is unaltered, other than obvious changes to constructors and so forth. In a moment we will show the full source, but here are some highlights:
A typical constructor call, say for a Gedge, now needs information about the new access functions mentioned above.
Gedge::Gedge(Pixel foreground_color_in,
Pixel background_color_in,
Pixel inside_color_in,
Pixel border_color_in,
Display *display_in,
Drawable drawable_in,
GC gc_in,
Pixmap pixmap_in,
Pixmap pixmap2_in,
Gnode *from,
Gnode *to,
EQ_FN equal_in,DISP_FN show_in,ENTRY_FN entry_in,
double weight,
Arbent data_in) : data(data_in),
equal(equal_in), show(show_in), entry(entry_in),
Edge(weight), d_from_p(from), d_to_p(to)
{
if(data_in!=NULL)
entry(&data,data_in);
...body here..
}
Note that we can initialize the incoming functions simply prior to entering the method body. The void * data here is first simply initialized to the incoming pointer value given by data_in. Then it is allocated as the proper type by the access function entry.
The Graph object construct now is a bit more busy as it must properly initialize many access functions:
//Constructor
Graph::Graph(EQ_FN edge_equal_in,DISP_FN edge_show_in,ENTRY_FN edge_entry_in,
EQ_FN node_equal_in,DISP_FN node_show_in,ENTRY_FN node_entry_in,
float radius_in,Vertex node_center_in, //node circle
Pixel in_foreground_color,
Pixel in_background_color,
Pixel *graph_colors,
Display *display_in,
Drawable drawable_in,
Pixmap pixmap_in,
Pixmap pixmap2_in,
GC gc_in) :
edge_entry(edge_entry_in), edge_equal(edge_equal_in),
edge_show(edge_show_in),
node_entry(node_entry_in), node_equal(node_equal_in),
node_show(node_show_in)
The addNode methods are almost the same with a small change to handle the new void * data:
Gnode* Graph::addNode(const char *nodeName,float x,float y,Arbent data)
{
Vertex node_center_in;
node_center_in.x = x;
node_center_in.y = y;
Gnode *p= new Gnode(foreground_color,
background_color,
node_inside_color,
node_border_color,
display,
drawable,
gc,
pixmap,
pixmap2,
node_radius,
&node_center_in,
nodeName,
node_equal,
node_show,
node_entry,
data);
d_nodes.add(p);
return p;
}
The void * data really makes no appreciable impact in most of the code. Only in methods where the data needs to be fed into a constructor is there a change. Consider the ReadInputFile method from Chapter 5: the changes are fairly simple; since we don't know what the data's type is we initialize the data to NULL.
addNode(node_name[i+m],x_position,y_position+j*y_delta,NULL); addEdge(findNode(from),findNode(to),edge_cost,NULL);
We do not know what the type of the data is, so any particular instantiation of the graph class must be built using access functions of a particular type. Consider the print method: the access function show must be used in the overloaded cout operator via the print method:
ostream& Graph::print(ostream& output) const
{
output << "Graph: " << endl;
GnodePtrBagIter nit(nodes());
if(nit){
output << "Nodes: " << endl;
}
for( ; nit; ++nit){
output << " " << nit()->name() << " ";
nit()->show(output,nit()->data);
}
const char *p = " Edges: ";
const char *q = " ";
for(GedgePtrBagIter eit(edges());eit;++eit){
output << endl << p << eit()->from()->name()
<< "-----(" << eit()->weight() << ")---> "
<< eit()->to()->name() << " " ;
eit()->show(output,eit()->data);
p = q;
}
output << endl << "End Graph " << endl;
return output;
}
Note the lines
nit()->show(output,nit()->data); eit()->show(output,eit()->data);
Each node obtained by the iterator nit() has associated with it a set of three access functions which enable the node to allocate, understand and output the void * data assigned to the node. Here nit()->data gets the node data and show(output,nit()->data) uses the proper display method to print the data to the ostream output. Hence, we can ouput the void * data without knowing what it is! A similar approach handles the edge data.
Relevant portions of the full code for the implementation of the void * based graph class are given below: code that is not changed from the original graph node is not listed.
//Gedge Constructor
Gedge::Gedge(Pixel foreground_color_in,
Pixel background_color_in,
Pixel inside_color_in,
Pixel border_color_in,
Display *display_in,
Drawable drawable_in,
GC gc_in,
Pixmap pixmap_in,
Pixmap pixmap2_in,
Gnode *from,
Gnode *to,
EQ_FN equal_in,DISP_FN show_in,ENTRY_FN entry_in,
double weight,
Arbent data_in) : data(data_in),
equal(equal_in), show(show_in), entry(entry_in),
Edge(weight), d_from_p(from), d_to_p(to)
{
if(data_in!=NULL)
entry(&data,data_in);
//set BOX Object
//center of from node is from()->node_center
//center of to node is to()->node_center
//
// (0.x,0.y) ---- (1.x,1.y)
// (3,x,3.y) ---- (2.x,2.y)
// (0.x,0.y) = (4.x,4.y)
//
//construct a box from the center of the from
//node to the center of the to node offset
//by +- 5 from the centers.
//
Vertex Data[5];
Vertex *axis = from->center();
Vertex *end = to->center();
//
float delta_x = end->x-axis->x;
float delta_y = end->y-axis->y;
float length = sqrt( delta_x*delta_x + delta_y*delta_y);
Data[0].x = axis->x;
Data[0].y = axis->y-2.0;
Data[1].x = axis->x + length;
Data[1].y = Data[0].y;
Data[2].x = Data[1].x;
Data[2].y = axis->y+2.0;
Data[3].x = Data[0].x;
Data[3].y = Data[2].y;
Data[4].x = Data[0].x;
Data[4].y = Data[0].y;
//create edge visual
E = new BOX(5, Data,display_in,drawable_in,pixmap_in,pixmap2_in,gc_in);
//set color of edge visual
E->color(inside_color_in,border_color_in,
foreground_color_in,background_color_in);
//rotate box so it goes "from node" to "to node"
float angle = atan2(end->y-axis->y,end->x-axis->x);
E->rotate(axis->x,axis->y,angle);
}
//construct a visual node
Gnode::Gnode(Pixel foreground_color_in,
Pixel background_color_in,
Pixel inside_color_in,
Pixel border_color_in,
Display *display_in,
Drawable drawable_in,
GC gc_in,
Pixmap pixmap_in,
Pixmap pixmap2_in,
float node_radius_in,
Vertex *node_center_in,
const char* name,
EQ_FN equal_in,DISP_FN show_in,ENTRY_FN entry_in,
Arbent data_in) : data(data_in),
Node(name), equal(equal_in), show(show_in),
entry(entry_in)
{
if(data_in!=NULL)
entry(&data,data_in);
//set node center
node_center.x = node_center_in->x;
node_center.y = node_center_in->y;
//set node radius
node_radius = node_radius_in;
//create node visual
C = new CIRCLE(node_radius_in,node_center_in,display_in,
drawable_in,pixmap_in,pixmap2_in,gc_in);
//set color of node visual
C->color(inside_color_in,border_color_in,
foreground_color_in,background_color_in);
}
Graph& Graph::FillData(Arbent node_data,int size_node,
Arbent edge_data,int size_edge)
{
int i = 0;
GnodePtrBagIter nit(nodes());
for( ; nit; ++nit){
nit()->entry(&(nit()->data),node_data + i*size_node);
nit()->show(cout,nit()->data);
++i;
}
i = 0;
for(GedgePtrBagIter eit(edges());eit;++eit){
eit()->entry(&(eit()->data), edge_data + i*size_edge);
eit()->show(cout,eit()->data);
++i;
}
return *this;
}
int Graph::NumberNodes(void)
{
int i = 0;
GnodePtrBagIter nit(nodes());
for( ; nit; ++nit){
++i;
}
return i;
}
int Graph::NumberEdges(void)
{
int i = 0;
for(GedgePtrBagIter eit(edges());eit;++eit){
++i;
}
return i;
}
ostream& Graph::print(ostream& output) const
{
output << "Graph: " << endl;
GnodePtrBagIter nit(nodes());
if(nit){
output << "Nodes: " << endl;
}
for( ; nit; ++nit){
output << " " << nit()->name() << " ";
nit()->show(output,nit()->data);
}
const char *p = " Edges: ";
const char *q = " ";
for(GedgePtrBagIter eit(edges());eit;++eit){
output << endl << p << eit()->from()->name()
<< "-----(" << eit()->weight() << ")---> "
<< eit()->to()->name() << " " ;
eit()->show(output,eit()->data);
p = q;
}
output << endl << "End Graph " << endl;
return output;
}
//Constructor
Graph::Graph(EQ_FN edge_equal_in,DISP_FN edge_show_in,ENTRY_FN edge_entry_in,
EQ_FN node_equal_in,DISP_FN node_show_in,ENTRY_FN node_entry_in,
float radius_in,Vertex node_center_in, //node circle
Pixel in_foreground_color,
Pixel in_background_color,
Pixel *graph_colors,
Display *display_in,
Drawable drawable_in,
Pixmap pixmap_in,
Pixmap pixmap2_in,
GC gc_in) :
edge_entry(edge_entry_in), edge_equal(edge_equal_in),
edge_show(edge_show_in),
node_entry(node_entry_in), node_equal(node_equal_in),
node_show(node_show_in)
{
//set default radius of a node
node_radius = radius_in;
//set default center of a node
node_center.x = node_center_in.x;
node_center.y = node_center_in.y;
//set colors
foreground_color = in_foreground_color;
background_color = in_background_color;
node_inside_color = graph_colors[0];
node_border_color = graph_colors[1];
edge_inside_color = graph_colors[2];
edge_border_color = graph_colors[3];
//set visuals
gc = gc_in;
drawable = drawable_in;
pixmap = pixmap_in;
pixmap2 = pixmap2_in;
display = display_in;
}
Gnode* Graph::addNode(const char *nodeName,float x,float y,Arbent data)
{
Vertex node_center_in;
node_center_in.x = x;
node_center_in.y = y;
Gnode *p= new Gnode(foreground_color,
background_color,
node_inside_color,
node_border_color,
display,
drawable,
gc,
pixmap,
pixmap2,
node_radius,
&node_center_in,
nodeName,
node_equal,
node_show,
node_entry,
data);
d_nodes.add(p);
return p;
}
Gedge *Graph::addEdge(Gnode* from,Gnode* to,double weight,Arbent data)
{
Gedge *p = new Gedge(foreground_color,
background_color,
edge_inside_color,
edge_border_color,
display,
drawable,
gc,
pixmap,
pixmap2,
from,to,
edge_equal,
edge_show,
edge_entry,
weight,data);
d_edges.add(p);
from->add(p);
to->add(p);
return p;
}