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