The implementation code is fairly standard and we will only show the methods that are rewritten for this case. Let's begin with the Gedge constructor. Essentially what we do here is to draw a box from the center of the from node to the to node of a fixed width. This involves a rotation of the box.
//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,
double weight) : Edge(weight), d_from_p(from), d_to_p(to)
{
//set BOX Data
//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 +- 2 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);
}
The Gnode constructor simply draws a circle of
a specified radius about the node center.
//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) : Node(name)
{
//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);
}
Now that we can display graphs visually, it is fun to try to generate Random Graphs for a variety of purposes: for example, parametric testing of algorithms being developed. Consider this first attempt:
Graph& Graph::GenerateRandomGraph(char *filename)
{
long value;
int SEED = 4450;
int seed_type = 1;
if(seed_type == 1)
srand((unsigned)time(&value));
else
srand(SEED);
int i;
int from_node, to_node;
float edge_weight;
int current_node;
int *number_of_current_edges;
int lower_edge_bound;
int upper_edge_bound;
int number_of_nodes;
int number_of_edges = 0;
char prefix = 'n';
int *ListArray;
int ListIndex;
int *HitArray;
float percent;
float lower_edge_weight;
float upper_edge_weight;
int get_from_node;
//ask user about RandomGraph parameters
cout << "How many nodes do you want in the graph?" << endl;
cin >> number_of_nodes;
cout << "You have chosen " << number_of_nodes << " for this graph" << endl;
cout << "We will generate a random number of edges between nodes. " << endl;
cout << "This number will be between a lower and upper bound." << endl;
cout << "Enter the lower bound for the number of edges:" << endl;
cin >> lower_edge_bound;
cout << "Enter the upper bound for the number of edges:" << endl;
cin >> upper_edge_bound;
cout << "Your design parameter is "
<< lower_edge_bound << " < number of edges < "
<< upper_edge_bound << endl;
cout << "We will generate a random edge weight between chosen nodes." << endl;
cout << "This number will be between a lower and upper bound." << endl;
cout << "Enter the lower bound for the edge weight:" << endl;
cin >> lower_edge_weight;
cout << "Enter the upper bound for the edge weight:" << endl;
cin >> upper_edge_weight;
cout << "Your design parameter is "
<< lower_edge_weight << " < edge_weight < "
<< upper_edge_weight << endl;
ofstream outfile(filename,ios::out);
cout << "number_of_nodes = " << number_of_nodes << endl;
ListArray = new (int)[number_of_nodes+1];
HitArray = new (int)[number_of_nodes];
number_of_current_edges = new (int)[number_of_nodes];
//Starting with the goal node, generate its preimage set
ListIndex = 0;
ListArray[0] = 1;
for(current_node=number_of_nodes;current_node>=2; current_node --){
//Pick a random number of edges between lower and upper edge bound
percent = (float)(rand())/(float)RAND_MAX;
number_of_current_edges[ListIndex]
= lower_edge_bound + (upper_edge_bound-lower_edge_bound)*percent;
//update the number of edges in the graph
number_of_edges += number_of_current_edges[ListIndex];
ListArray[++ListIndex] = number_of_edges + 1;
}
ListArray[number_of_nodes-1] = number_of_edges+1;
ListArray[number_of_nodes] = number_of_edges+1;
//output first line of GraphFile
outfile << number_of_nodes << " " << number_of_edges << endl;
//output lines for ListArray
int whole = 5*((number_of_nodes+1)/5);
int remainder = number_of_nodes - whole;
for(i=0;i<whole; i+=5){
outfile << ListArray[i] << " "
<< ListArray[i+1] << " "
<< ListArray[i+2] << " "
<< ListArray[i+3] << " "
<< ListArray[i+4] << " ";
outfile << endl;
}
for(i=whole;i<number_of_nodes+1;++i){
outfile << ListArray[i] << endl;
}
//now generate from nodes and edge weights
ListIndex = 0;
for(current_node=number_of_nodes;current_node>=2; current_node --){
//initialize the HitArray
for(i=0;i<number_of_nodes;++i)
HitArray[i] = 0;
//choose a random from node and assign a random weight
for(i=0;i<number_of_current_edges[ListIndex];++i){
get_from_node = 1;
while(get_from_node == 1){
//pick a from node
percent = (float)(rand())/(float)RAND_MAX;
from_node = number_of_nodes*percent;
if(from_node==number_of_nodes) --from_node;
if(from_node==0) ++from_node;
//see if we can accept this node
if(HitArray[from_node]==0){
HitArray[from_node] = 1;
//Pick edge weight
percent = (float)(rand())/(float)RAND_MAX;
edge_weight = lower_edge_weight +
(upper_edge_weight-lower_edge_weight)*percent;
//write to the file
outfile << current_node << " " << from_node << " " << edge_weight << endl;
get_from_node = 0;
}
}//get random from_node that is not already taken
}//loop on number of current edges
}//loop on the number of nodes
outfile.close();
return *this;
}
We also need a function to read in the parameters of the randomly generated graph from a file.
Graph& Graph::ReadInputFile(char *filename)
{
int i,j,k,m;
int from_node, to_node;
float edge_cost;
int number_of_nodes;
int number_of_edges;
char prefix = 'n';
int *ListArray;
ifstream infile(filename,ios::in);
infile >> number_of_nodes >> number_of_edges;
cout << "number_of_nodes = " << number_of_nodes << endl;
cout << "number_of_edges = " << number_of_edges << endl;
ListArray = new (int)[number_of_nodes+1];
for(i=0;i<=number_of_nodes;++i){
infile >> ListArray[i];
cout << "ListArray[" << i << "] = " << ListArray[i] << endl;
}
char **node_name = new (char *)[number_of_nodes];
for(i = 0;i< number_of_nodes; ++i)
node_name[i] = new (char)[20];
//create name list for nodes:
for(i=0; i<number_of_nodes; ++i){
sprintf(node_name[i],"%c%d",prefix,i+1);
printf("%s%\n",node_name[i]);
}
//create nodes
float x_position, y_position;
float x_delta,y_delta;
x_position = 100.0;
y_position = 200.0;
x_delta = 100.0;
y_delta = 200.0;
//create node at default position
cout << "Creating node " << node_name[0] << endl;
addNode(node_name[0],x_position,y_position);
//The spread of the graph is P nodes
int P = (int) sqrt( (float)number_of_nodes );
int count = 0;
int whole = P*(number_of_nodes/P);
if(P%2==0) k = P/2;
else k = P/2+1;
for(i=1; i<whole; i+=P){
x_position += x_delta;
for(j=-P/2;j<k;++j){
m = j+P/2;
if( (i+m) < number_of_nodes ){
count ++;
cout << "Creating node " << node_name[i+m] << endl;
addNode(node_name[i+m],x_position,y_position+j*y_delta);
}
}
}
int Q = number_of_nodes-1-whole;
if(Q%2==0) k = Q/2;
else k = Q/2+1;
//there are < P nodes left
x_position += x_delta;
for(j=-Q/2;j<k;++j){
m = j+Q/2;
if( (whole+1+m)<number_of_nodes){
count ++;
cout << "Creating node " << node_name[whole+1+m] << endl;
addNode(node_name[whole+1+m],x_position,y_position+j*y_delta);
}
}
if(count<number_of_nodes-1){
//create node at final position
x_position += x_delta;
cout << "Creating node " << node_name[number_of_nodes-1] << endl;
addNode(node_name[number_of_nodes-1],x_position,y_position);
}
//create edges
char from[20];
char to[20];
for(i=0; i<number_of_edges; ++i){
infile >> from_node >> to_node >> edge_cost;
sprintf(from,"%c%d",prefix,from_node);
sprintf(to,"%c%d",prefix,to_node);
addEdge(findNode(from),findNode(to),edge_cost);
}
infile.close();
return *this;
}
The Graph object constructor is implemented as follows:
//Constructor
Graph::Graph(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)
{
//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;
}
It is easy to build the needed draw(), rotate() and so forth methods using the built in edge and node bag iterators and the already developed visualization methods for the BOX and CIRCLE classes.
//Graph Visual
Graph& Graph::draw(Drawable D)
{
GnodePtrBagIter nit(nodes());
if(nit){
for( ; nit; ++nit){
nit()->C->draw(D);
}
}
for(GedgePtrBagIter eit(edges());eit;++eit){
//create edge visual
eit()->E->draw(D);
}
return *this;
}
Graph& Graph::erase(Drawable D)
{
//switch foreground and background colors
XSetForeground(display,gc,background_color);
//fill rectangle
XFillRectangle(display,D,gc,0,0,1200,1200);
//reset foreground to original color
XSetForeground(display,gc,foreground_color);
return *this;
}
Graph& Graph::translate(int xoffset, int yoffset)
{
GnodePtrBagIter nit(nodes());
if(nit){
for( ; nit; ++nit){
nit()->C->translate(xoffset,yoffset);
}
}
for(GedgePtrBagIter eit(edges());eit;++eit){
eit()->E->translate(xoffset,yoffset);
}
return *this;
}
Graph& Graph::find_center(Vertex *V)
{
float avgx, avgy;
avgx = 0.0;
avgy = 0.0;
Vertex NC;
int count = 0;
GnodePtrBagIter nit(nodes());
if(nit){
for( ; nit; ++nit){
count++;
nit()->C->getcenter(&NC);
avgx += NC.x;
avgy += NC.y;
}
}
V->x = avgx/(float)count;
V->y = avgy/(float)count;
return *this;
}
Graph& Graph::rotate(float axis_x,float axis_y,float angle)
{
GnodePtrBagIter nit(nodes());
if(nit){
for( ; nit; ++nit){
nit()->C->rotate(axis_x,axis_y,angle);
}
}
for(GedgePtrBagIter eit(edges());eit;++eit){
eit()->E->rotate(axis_x,axis_y,angle);
}
return *this;
}
Graph& Graph::scale(float scale_factor)
{
GnodePtrBagIter nit(nodes());
Vertex CC;
if(nit){
for( ; nit; ++nit){
nit()->C->scale(scale_factor);
nit()->C->getcenter(&CC);
}
}
//Scale edges.
//This moves center of nodes
//so we must update the centers.
Vertex V[5];
Vertex C;
Vertex sum;
BOX *B;
Gnode *F;
Gnode *T;
for(GedgePtrBagIter eit(edges());eit;++eit){
B = eit()->E;
F = eit()->from();
T = eit()->to();
B->scale(scale_factor);
//get vertices of the edge box
B->getvertices(V);
//V[0] and V[3] are the attachments to the
//center of the "from node"
C.x = V[0].x;
C.y = 0.5*(V[0].y+V[3].y);
//now load this center into the from node
F->C->loadcenter(&C);
F->C->getcenter(&C);
//V[1] and V[2} are the attachments to the
//center of the "to node"
C.x = V[1].x;
C.y = 0.5*(V[1].y+V[2].y);
//now load this center into the to node
T->C->loadcenter(&C);
T->C->getcenter(&C);
}
return *this;
}
Graph& Graph::CenteredScale(float scale_factor)
{
GnodePtrBagIter nit(nodes());
if(nit){
for( ; nit; ++nit){
nit()->C->CenteredScale(scale_factor);
}
}
Vertex V[5];
Vertex C;
BOX *B;
Gnode *F;
Gnode *T;
for(GedgePtrBagIter eit(edges());eit;++eit){
B = eit()->E;
F = eit()->from();
T = eit()->to();
B->CenteredScale(scale_factor);
//get vertices of the edge box
B->getvertices(V);
//V[0] and V[3] are the attachments to the
//center of the "from node"
C.x = V[0].x;
C.y = 0.5*(V[0].y+V[3].y);
//now load this center into the from node
F->C->loadcenter(&C);
F->C->getcenter(&C);
//V[1] and V[2} are the attachments to the
//center of the "to node"
C.x = V[1].x;
C.y = 0.5*(V[1].y+V[2].y);
//now load this center into the to node
T->C->loadcenter(&C);
T->C->getcenter(&C);
}
return *this;
}
Graph& Graph::ScaleTranslate(float scale_factor,int xoffset,int yoffset)
{
GnodePtrBagIter nit(nodes());
if(nit){
for( ; nit; ++nit){
nit()->C->ScaleTranslate(scale_factor,xoffset,yoffset);
}
}
Vertex V[5];
Vertex C;
BOX *B;
Gnode *F;
Gnode *T;
for(GedgePtrBagIter eit(edges());eit;++eit){
B = eit()->E;
F = eit()->from();
T = eit()->to();
B->ScaleTranslate(scale_factor,xoffset,yoffset);
//get vertices of the edge box
B->getvertices(V);
//V[0] and V[3] are the attachments to the
//center of the "from node"
C.x = V[0].x;
C.y = 0.5*(V[0].y+V[3].y);
//now load this center into the from node
F->C->loadcenter(&C);
F->C->getcenter(&C);
//V[1] and V[2} are the attachments to the
//center of the "to node"
C.x = V[1].x;
C.y = 0.5*(V[1].y+V[2].y);
//now load this center into the to node
T->C->loadcenter(&C);
T->C->getcenter(&C);
}
return *this;
}
The add node and edge methods need to be updated to take into account the new visual information:
Gnode* Graph::addNode(const char *nodeName,float x,float y)
{
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);
d_nodes.add(p);
return p;
}
Gedge *Graph::addEdge(Gnode* from,Gnode* to,double weight)
{
Gedge *p = new Gedge(foreground_color,
background_color,
edge_inside_color,
edge_border_color,
display,
drawable,
gc,
pixmap,
pixmap2,
from,to,weight);
d_edges.add(p);
from->add(p);
to->add(p);
return p;
}