changed from rand() to CrnRand() and so on.
[charm.git] / src / conv-ldb / generate.c
1 /* Generate a random graph, given the number of nodes, the number of
2    connections per node.
3
4 Output form: directory graphN/ containing files graph0 ... graphN-1
5              file graphK has C, the number of connections, followed by
6              a list of C vertices that K is connected to
7
8 Modified from the original: changed output format, and converted main to a parametered function
9 */
10 #ifdef WIN32
11 #include <stdio.h>
12 #include <stdlib.h>
13 #else
14 #include "stdio.h"
15 #endif
16 /* comment this out to test and change CmiPrintf to printf */
17 #include "converse.h"
18 #include "typedefs.h"
19
20 #ifdef WIN32
21 extern int edgeExists(int, int);
22 int isEmpty(Q*);
23 int dequeue(Q*);
24 #endif
25
26 #define VMAX 2050
27 int V; /* no. of vertices */
28 int E; /* no. of edges */
29 int C; /* no. of connections per vertex */
30 int seed;
31
32 VerticesListType graph;
33
34 VerticesListType * InitVertices();
35
36
37 /* For testing... 
38 main(int argc, char **argv)
39 {
40   gengraph(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]));
41 }
42 */
43
44 void printOut(VerticesListType *vertices);
45 void initGraph(void);
46 void diameter(void);
47 void AddEdges(EdgeListType *EdgeList, int V, int n);
48
49 void gengraph(int pV, int pC, int pseed)
50 { int i;
51   EdgeListType * EdgeList;
52   /* VerticesListType * vertices; */
53   extern EdgeListType * InitEdgeList();
54   extern addEdge();
55   char dircmd[20], dirname[10];
56
57
58   V = pV;
59   C = pC;
60   seed = pseed;
61   
62   CmiPrintf("for %d PEs, connectivity %d... ", V, C);
63
64   /* make a directory */
65   sprintf(dirname, "graph%d", V);
66   sprintf(dircmd, "mkdir %s", dirname);
67   system(dircmd);
68   
69   /* for (i=0; i<seed; i++) rand(); */
70   for (i=0; i<seed; i++) CrnRand();
71   if ((V*C %2) != 0) printf("V*C must be even\n");
72   E = V*C/2;
73   initGraph();
74   EdgeList = InitEdgeList(E);
75   AddEdges(EdgeList, V, E); 
76   /*  vertices = (VerticesListType *) InitVertices(EdgeList, V,E); */
77
78   printOut(&graph); 
79   diameter();
80 }
81
82
83 void AddEdges(EdgeListType *EdgeList, int V, int n)
84    /* Add more edges to make up a total of E edges */
85 {int i,j,w,x,y;
86 /* first add edges for a C-way spanning tree.*/
87 int c1;
88 c1 = C-1;
89
90 for (i=0; i< V/c1; i++)
91   for (j=0; j<c1; j++) {
92     w = c1*i + j +1; 
93     /*      printf("considering (%d, %d)\n", i, w); */
94       if (w < V) {
95         addEdge(EdgeList,i,w);
96         /* printf(" --- added.\n");*/
97       }
98       /*      else printf(" not added.\n"); */
99   }
100 n -= (V-1);
101
102  for (i=0; i<n; i++) 
103    {
104      do {
105        do {
106          /* x = rand() % V; */
107          x = CrnRand() % V;
108        } while (connections(x) >= C);
109        do {
110          /* y = rand() % V; */
111          y = CrnRand() % V; 
112        } while ((y == x) || connections(y) >= C);
113      } while (edgeExists(x,y));
114      addEdge(EdgeList, x, y);
115    }
116 }
117
118 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E);
119 void sortAdjArrays(VerticesListType *vlist);
120 void sort(int *adj, int fromIndex, int toIndex);
121 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E);
122
123 VerticesListType * 
124 InitVertices(EdgeList, V,E)
125      EdgeListType * EdgeList;
126      int V;
127      int E;
128 { /* returns a structure of type VerticesListType, which contains an arry of 
129      vertex records, and an array of adjacency information. See typedef. */
130   /* First allocate the adjacency subarray of size E, and vertex subarray size V.
131      Then count the occurences of each vertex in the Edgelist in vertex.degree.
132      Then compute the real adjListInd = sum from 0 to i-1 of the previous degrees.
133      Then, traverse edge list, and enter each edge in two adj lists.
134      Then sort individual adj-lists, separately. */
135   VerticesListType * vlist;
136
137   vlist = (VerticesListType *) malloc(sizeof(VerticesListType));
138   _MEMCHECK(vlist);
139   vlist->numVertices = V;
140   vlist->vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
141   _MEMCHECK(vlist->vertexArray);
142   vlist->adjArray = (int *) malloc(2*E*sizeof(int)); 
143                     /* as each edge is entered twice */
144   _MEMCHECK(vlist->adjArray);
145   countDegrees(EdgeList->edges, vlist->vertexArray, V, E);
146   fillAdjArray(EdgeList->edges, vlist, V, E);
147   sortAdjArrays(vlist);
148   return(vlist);
149 }
150
151 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E)
152 { /* initialize the degrees of all vertices to 0. 
153      Traverse the edge list, incrementing the degree of the 2 nodes for each edge.
154      */
155  int i, count;
156  
157  for (i=0; i<V; i++)
158    { vertRecs[i].degree = 0;
159      vertRecs[i].next = 0;}
160  for (i=0; i<E; i++)
161    {vertRecs[ edges[i].node1 ].degree++;
162     vertRecs[ edges[i].node2 ].degree++;}
163
164 /* now fill adjListInd, by starting a counter at 0, and adding degrees of visited
165    nodes. */
166  count = 0;
167  for (i=0; i<V; i++)
168    { vertRecs[i].adjListInd = count;
169      count += vertRecs[i].degree;
170    }
171 }
172
173 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E)
174 { /* Insert each edge <x,y> as an entry y in x's adj list, and vice versa. */
175   int i, x,y;
176  int * adj;
177  Vertex * vertexRecs;
178
179  adj = vlist->adjArray;
180  vertexRecs = vlist->vertexArray;
181
182   for (i=0; i<E; i++)
183     { x = edges[i].node1; y = edges[i].node2;
184       adj[ vertexRecs[x].adjListInd + vertexRecs[x].next ] = y;
185       vertexRecs[x].next++;
186       adj[ vertexRecs[y].adjListInd + vertexRecs[y].next ] = x;
187       vertexRecs[y].next++;
188     }
189 }
190
191 void sortAdjArrays(VerticesListType *vlist)
192 { /* sort each section of the array corresponding to each vertex. */
193   int V, i;
194   int dupcount;
195
196   V = vlist->numVertices;
197   for (i=0; i<V; i++)
198     { sort(vlist->adjArray, 
199            vlist->vertexArray[i].adjListInd,
200            vlist->vertexArray[i].adjListInd + vlist->vertexArray[i].degree -1);
201     }
202   /* eliminate duplicates. May be should be merged with above? */
203   dupcount = 0;
204   for (i=0; i<V; i++)
205     { int m,n, limit;
206       int * adj;
207
208       m = vlist->vertexArray[i].adjListInd;
209       n = m+1;
210       limit = m + vlist->vertexArray[i].degree; /* this is the first index
211                                                    not belonging to this vertex.*/
212       adj = vlist->adjArray;
213       /* do this in 2 phases. First phase: m and n are exactly one away.
214          goes on until the first duplicate is found. In this phase, there
215          is no need to assign values (no shifting is going on.) */
216       while ((adj[m] != adj[n]) && (n < limit)) {m++; n++;}
217       /* Phase 2: */
218       while (n<limit) {
219         while ((adj[m] == adj[n]) && (n<limit)) 
220           { n++; dupcount++; vlist->vertexArray[i].degree--;}
221         adj[m+1] = adj[n]; /*move the non duplicate back to its new position*/
222         m++; n++;
223       }
224     }
225 /* printf("number of duplicate edges removed = %d\n", dupcount/2);*/
226 /* Here is an assignment to a global variable.... */
227 if ((dupcount % 2) != 0) {printf("error. duplicates not even.\n"); }
228 E -= dupcount/2;
229 }
230
231 void sort(int *adj, int fromIndex, int toIndex)
232 { int i,j, tmp;
233   short changed;
234   changed = 1;
235   for (i=toIndex; ((i>fromIndex) && changed); i--)
236     { changed = 0;
237       for (j=fromIndex; j<i; j++)
238         { if (adj[j] > adj[j+1])
239             { /* swap */
240               changed = 1;
241               tmp = adj[j];
242               adj[j] = adj[j+1];
243               adj[j+1] = tmp;
244             }
245         }
246     }
247 }
248
249 void printOut(VerticesListType *vertices)
250 {int i,j;
251  int * adj;
252  Vertex * vertexRecs;
253  FILE *fp;
254  char filename[20];
255  
256  adj = vertices->adjArray;
257  vertexRecs = vertices->vertexArray;
258
259  for (i=0; i<vertices->numVertices; i++)
260    {
261      /* Open graphN/graphi */
262      sprintf(filename, "graph%d/graph%d", vertices->numVertices, i);
263      fp = fopen(filename, "w");
264      fprintf(fp, "%d ", vertexRecs[i].degree);
265      for (j=0; j<vertexRecs[i].degree; j++)
266        fprintf(fp, "%d ", adj[ vertexRecs[i].adjListInd + j ]);
267      fprintf(fp, "\n");
268      fclose(fp);
269    }
270 }
271
272 void initGraph(void)
273 { int i;
274   graph.numVertices = V;
275   graph.vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
276   _MEMCHECK(graph.vertexArray);
277   graph.adjArray = (int *) malloc(2*E*sizeof(int));
278   _MEMCHECK(graph.adjArray);
279
280   for (i=0; i< V; i++) {
281     graph.vertexArray[i].degree = 0;
282     graph.vertexArray[i].next = i*C;
283     graph.vertexArray[i].adjListInd = i*C;
284   }
285 }
286
287 void enqueue(Q *q, int i);
288
289 void diameter(void)
290 {
291   Q * makeQueue();
292   int i,j, k, v, w, start;
293   int *distance;
294   int *histogram;
295   Q * q;
296   int dia;
297   float average;
298
299   distance = (int *)calloc(V, sizeof(int));
300   histogram = (int *)calloc(V, sizeof(int));
301
302   for (i=0; i<V; i++) {
303     histogram[i] = 0; 
304   }
305   
306   dia = 0;
307   average = 0.0;
308   q = makeQueue();
309   for (i=0; i<V; i++) {
310     /* run non-weighted shortes distance algorithm for each vertex i */
311     for (j=0; j<V; j++) distance[j] = -1;
312     distance[i] = 0;
313     enqueue(q, i);
314     while (! (isEmpty(q))) {
315       v = dequeue(q);
316       
317       start=graph.vertexArray[v].adjListInd;
318       for (k=0; k< graph.vertexArray[i].degree; k++) {
319         w = graph.adjArray[k+start];
320         if (distance[w] == -1) {
321           distance[w] = distance[v] + 1;
322           enqueue(q, w);
323         }
324       }
325     }
326     for (j=0; j<V; j++) {
327       if (distance[j] > dia) dia = distance[j];
328       average += distance[j];
329       histogram[ distance[j]]++;
330     }
331   }
332   average = average / (V*V);
333   printf("the diameter is: %d, average internode distance = %f\n", 
334          dia, average);
335   /*   for (i = 0; i< 6; i++) printf("histo[%d] = %d\n", i, histogram[i]);*/
336 }
337
338 /* ------------------------------------------------- */
339 /* The queue ADT */
340
341 Q * makeQueue()
342 {
343   Q *q = (Q *) malloc(sizeof(Q));
344   _MEMCHECK(q);
345   q->size = VMAX;
346   q->head = 1;
347   q->tail = 0;
348   q->buf = (int *) malloc(VMAX*sizeof(int));
349   _MEMCHECK(q->buf);
350   return q;
351 }
352
353 void enqueue(Q * q, int i) {
354   q->tail++;
355   if (q->tail == q->size) q->tail = 0; /* no overflows possible */
356   q->buf[q->tail] = i;
357   q->numElements++;
358 }
359
360 int dequeue(Q *q) {
361   int r;
362   r = q->buf[q->head++];
363   if (q->head == q->size) q->head = 0;
364   q->numElements--;
365   return r;
366 }
367
368 int isEmpty(Q * q) {
369   return (q->numElements == 0) ;
370 }