It is useful to be able to generate random graphs of fairly large size with varied interconnection patterns. A first attempt is the following Graph class method Graph& Graph::GenerateRandomGraph(char *filename):
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;
}
Since these graphs can be so large, we have also altered our strategy for generating the visual object associated with the graph by rewriting the ReadInputFile method somewhat: we attempt to control how wide the graph visual object by using a spread parameter P:
//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 ++;
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
cout << "loop over last P nodes " << endl;
x_position += x_delta;
for(j=-Q/2;j<k;++j){
m = j+Q/2;
if( (whole+1+m)<number_of_nodes){
count ++;
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;
addNode(node_name[number_of_nodes-1],x_position,y_position);
}
This codes sets P to be the square root of the number of nodes and thus generates a reasonable visual.
Let's run this new version of the program and see its output: We are asked to input some information about our proposed graph:
How many nodes do you want in the graph? 32 You have chosen 32 for this graph We will generate a random number of edges between nodes. This number will be between a lower and upper bound. Enter the lower bound for the number of edges: 1 Enter the upper bound for the number of edges: 1 Your design parameter is 1 < number of edges < 1 We will generate a random edge weight between chosen nodes. This number will be between a lower and upper bound. Enter the lower bound for the edge weight: 2. Enter the upper bound for the edge weight: 5. Your design parameter is 2 < edge_weight < 5
This generates a graph of 32 nodes with only 1 edge allowed in our random creation process with the edge weights in the interval [2, 5].
The graph of this object, is represented visually by Figure 5.8.
