Some compilers such as VC++ donot support multi dimension variable size array declara...
[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 dump graph if "tofile" is true
12 Output form: directory graphN/ containing files graph0 ... graphN-1
13              file graphK has C, the number of connections, followed by
14              a list of C vertices that K is connected to
15
16 Modified from the original: changed output format, and converted main to a parametered function
17 */
18 #include <stdio.h>
19 #include <stdlib.h>
20
21 /* comment this out to test and change CmiPrintf to printf */
22 #include "converse.h"
23 #include "typedefs.h"
24
25 int addEdge(EdgeListType *l,int fm,int to);
26 void addspEdge(EdgeListType *, int, int);
27 int edgeExists(int fm, int to);
28 static Q * makeQueue();
29 static int isEmpty(Q*);
30 static int dequeue(Q*);
31
32 #define VMAX 2050
33 int V; /* no. of vertices */
34 int E; /* no. of edges */
35 int C; /* no. of connections per vertex */
36 int seed;
37
38 VerticesListType graph;
39
40 VerticesListType * InitVertices();
41
42
43 /* For testing... 
44 main(int argc, char **argv)
45 {
46   gengraph(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]));
47 }
48 */
49
50 static void printOut(VerticesListType *vertices);
51 static void copyOut(VerticesListType *vertices, int *npe, int *pes);
52 static void initGraph(void);
53 static void diameter(void);
54 static void AddEdges(EdgeListType *EdgeList, int V, int n);
55
56 void gengraph(int pV, int pC, int pseed, int *pes, int *npe, int tofile)
57 { int i;
58   EdgeListType * EdgeList;
59   /* VerticesListType * vertices; */
60   extern EdgeListType * InitEdgeList();
61   char dircmd[20], dirname[10];
62
63   V = pV;
64   C = pC;
65   seed = pseed;
66   
67   if (CmiMyPe() == 0)
68   CmiPrintf("for %d PEs, connectivity %d... \n", V, C);
69
70   /* make a directory */
71   if (tofile && CmiMyPe() == 0) {
72   sprintf(dirname, "graph%d", V);
73   sprintf(dircmd, "mkdir %s", dirname);
74   system(dircmd);
75   }
76   
77   /* for (i=0; i<seed; i++) rand(); */
78   for (i=0; i<seed; i++) CrnRand();
79   if ((V*C %2) != 0) printf("V*C must be even\n");
80   E = V*C/2;
81   initGraph();
82   EdgeList = InitEdgeList(E);
83   AddEdges(EdgeList, V, E); 
84   /*  vertices = (VerticesListType *) InitVertices(EdgeList, V,E); */
85
86   if (tofile) {
87     if (CmiMyPe()==0) printOut(&graph);
88   }
89   else copyOut(&graph, npe, pes);
90
91   if (CmiMyPe()==0) diameter();
92 }
93
94 #if 0
95 static void AddEdges(EdgeListType *EdgeList, int V, int n)
96    /* Add more edges to make up a total of E edges */
97 {int i,j,w,x,y;
98 /* first add edges for a C-way spanning tree.*/
99 int c1;
100 if (C>1) c1 = C-1;
101
102 for (i=0; i< V/c1; i++)
103   for (j=0; j<c1; j++) {
104       w = c1*i + j +1; 
105       /* printf("considering (%d, %d)\n", i, w);  */
106       if (w < V) {
107         addEdge(EdgeList,i,w);
108         /* printf(" --- added.\n"); */
109       }
110       else /*printf(" not added.\n")*/; 
111   }
112 n -= (V-1);
113
114  for (i=0; i<n; i++) 
115    {
116      do {
117        do {
118          x = CrnRand() % V;
119        } while (connections(x) >= C);
120        do {
121          y = CrnRand() % V;
122        } while ((y== x) || connections(y) >= C);
123      } while (edgeExists(x,y));
124      addEdge(EdgeList, x, y);
125    }
126 }
127 #endif
128
129 static void AddEdges(EdgeListType *EdgeList, int V, int n)
130         /* Add more edges to make up a total of E edges */
131   {     int i,j,w,x,y,k;
132         int c1,max,maxi;
133         int **varr;
134         int varrlen,count=0;
135         int flag=0;
136
137         /* first add edges for a C-way spanning tree.*/
138         varr=(int **)calloc(V, sizeof(int*));
139         for (i=0;i<V;i++)
140             varr[i]=calloc(2, sizeof(int));
141         
142         if (C>1) c1 = C-1;
143
144         for (i=0; i< V/c1; i++)
145           for (j=0; j<c1; j++) {
146               w = c1*i + j +1; 
147               if (w < V) {
148                 addEdge(EdgeList,i,w);
149                 count++;
150                               }
151                   }
152         
153         /*varr is array of vertices and free connection for each vertex*/
154         j=0;
155         for (i=0;i<V;i++)
156                 if(connections(i)<C)
157                 {
158                  varr[j][0]=i;
159                  varr[j][1]=C-connections(i);
160                  j++;
161                 }
162         varrlen=j;
163         
164         /*for all edges except last 10 , edge is formed by randomly selecting vertices from varr*/
165
166         n -= count;
167
168         /*if (n>10)
169         for (j=0; j<n-10; j++) 
170            {
171                 flag=0;
172                 do {
173                      x = rand() % varrlen;
174                      do {
175                              y = rand() % varrlen;
176                         } while (y == x) ;
177                 }while (edgeExists(varr[x][0],varr[y][0]));
178              addEdge(EdgeList, varr[x][0], varr[y][0]);
179              
180              varr[x][1]=varr[x][1]-1;
181              varr[y][1]=varr[y][1]-1;
182
183              //If no free connections left for a vertex remove it from varr     
184
185              if (varr[x][1]==0) {
186                                  flag=1;
187                                  for (i=x;i<varrlen-1;i++)
188                                         {       
189                                          varr[i][0]=varr[i+1][0];
190                                          varr[i][1]=varr[i+1][1];
191                                         }
192                                  varrlen--;
193                                 }
194              if ((y>x)&&(flag)) {
195                                          
196                                         if (varr[y-1][1]==0)   
197                                                         {
198                                                           for (i=y-1;i<varrlen-1;i++)
199                                                                 {       
200                                                                  varr[i][0]=varr[i+1][0];
201                                                                  varr[i][1]=varr[i+1][1];
202                                                                 }
203                                                           varrlen--;
204                                                         }
205                                 }                               
206              else if (varr[y][1]==0) {
207                                  for (i=y;i<varrlen-1;i++)
208                                         {       
209                                          varr[i][0]=varr[i+1][0];
210                                          varr[i][1]=varr[i+1][1];
211                                         }
212                                  varrlen--;
213                                 }
214            }
215
216         //for last 10 edges, first vertex is one with max free connections and other vertex is randomly chosen 
217
218         if (n>10) k=10; else k = n;*/
219
220         k=n;
221         for (j=0;j<k;j++)
222                 {
223                                 flag=0;
224                                 max=0;
225                                 maxi=0;
226                                 for (i=0;i<varrlen;i++)
227                                         if (varr[i][1]>max) { max=varr[i][1];maxi=i;}
228                                 x = maxi;
229                                 do {
230                                      y = rand() % varrlen;
231                                    } while (y == x) ;
232
233                                 if (edgeExists(varr[x][0],varr[y][0])) 
234                                         if (j==k-1) addspEdge(EdgeList,varr[x][0],varr[y][0]);
235                                         else do {
236                                                         y = rand() % varrlen;
237                                                  } while (y == x);
238                                 else addEdge(EdgeList,varr[x][0],varr[y][0]); 
239
240                                 varr[x][1]=varr[x][1]-1;
241                                 varr[y][1]=varr[y][1]-1;
242                                                 
243                                 if (varr[x][1]==0) 
244                                         {
245                                          flag=1;
246                                          for (i=x;i<varrlen-1;i++)
247                                                 {       
248                                                  varr[i][0]=varr[i+1][0];
249                                                  varr[i][1]=varr[i+1][1];
250                                                 }
251                                          varrlen--;
252                                         }       
253                                 if ((y>x)&&(flag))         
254                                         {
255                                          if (varr[y-1][1]==0)   
256                                                         {
257                                                           for (i=y-1;i<varrlen-1;i++)
258                                                                 {       
259                                                                  varr[i][0]=varr[i+1][0];
260                                                                  varr[i][1]=varr[i+1][1];
261                                                                 }
262                                                           varrlen--;
263                                                         }
264                                         }                               
265                                 else if (varr[y][1]==0)
266                                         {
267                                                  for (i=y;i<varrlen-1;i++)
268                                                         {       
269                                                          varr[i][0]=varr[i+1][0];
270                                                          varr[i][1]=varr[i+1][1];
271                                                         }
272                                                  varrlen--;
273                                         }
274                         }             
275         for (i=0;i<V;i++) free(varr[i]);
276         free(varr);
277 }
278
279
280 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E);
281 void sortAdjArrays(VerticesListType *vlist);
282 static void sort(int *adj, int fromIndex, int toIndex);
283 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E);
284
285 VerticesListType * 
286 InitVertices(EdgeList, V,E)
287      EdgeListType * EdgeList;
288      int V;
289      int E;
290 { /* returns a structure of type VerticesListType, which contains an arry of 
291      vertex records, and an array of adjacency information. See typedef. */
292   /* First allocate the adjacency subarray of size E, and vertex subarray size V.
293      Then count the occurences of each vertex in the Edgelist in vertex.degree.
294      Then compute the real adjListInd = sum from 0 to i-1 of the previous degrees.
295      Then, traverse edge list, and enter each edge in two adj lists.
296      Then sort individual adj-lists, separately. */
297   VerticesListType * vlist;
298
299   vlist = (VerticesListType *) malloc(sizeof(VerticesListType));
300   _MEMCHECK(vlist);
301   vlist->numVertices = V;
302   vlist->vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
303   _MEMCHECK(vlist->vertexArray);
304   vlist->adjArray = (int *) malloc(2*E*sizeof(int)); 
305                     /* as each edge is entered twice */
306   _MEMCHECK(vlist->adjArray);
307   countDegrees(EdgeList->edges, vlist->vertexArray, V, E);
308   fillAdjArray(EdgeList->edges, vlist, V, E);
309   sortAdjArrays(vlist);
310   return(vlist);
311 }
312
313 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E)
314 { /* initialize the degrees of all vertices to 0. 
315      Traverse the edge list, incrementing the degree of the 2 nodes for each edge.
316      */
317  int i, count;
318  
319  for (i=0; i<V; i++)
320    { vertRecs[i].degree = 0;
321      vertRecs[i].next = 0;}
322  for (i=0; i<E; i++)
323    {vertRecs[ edges[i].node1 ].degree++;
324     vertRecs[ edges[i].node2 ].degree++;}
325
326 /* now fill adjListInd, by starting a counter at 0, and adding degrees of visited
327    nodes. */
328  count = 0;
329  for (i=0; i<V; i++)
330    { vertRecs[i].adjListInd = count;
331      count += vertRecs[i].degree;
332    }
333 }
334
335 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E)
336 { /* Insert each edge <x,y> as an entry y in x's adj list, and vice versa. */
337   int i, x,y;
338  int * adj;
339  Vertex * vertexRecs;
340
341  adj = vlist->adjArray;
342  vertexRecs = vlist->vertexArray;
343
344   for (i=0; i<E; i++)
345     { x = edges[i].node1; y = edges[i].node2;
346       adj[ vertexRecs[x].adjListInd + vertexRecs[x].next ] = y;
347       vertexRecs[x].next++;
348       adj[ vertexRecs[y].adjListInd + vertexRecs[y].next ] = x;
349       vertexRecs[y].next++;
350     }
351 }
352
353 void sortAdjArrays(VerticesListType *vlist)
354 { /* sort each section of the array corresponding to each vertex. */
355   int V, i;
356   int dupcount;
357
358   V = vlist->numVertices;
359   for (i=0; i<V; i++)
360     { sort(vlist->adjArray, 
361            vlist->vertexArray[i].adjListInd,
362            vlist->vertexArray[i].adjListInd + vlist->vertexArray[i].degree -1);
363     }
364   /* eliminate duplicates. May be should be merged with above? */
365   dupcount = 0;
366   for (i=0; i<V; i++)
367     { int m,n, limit;
368       int * adj;
369
370       m = vlist->vertexArray[i].adjListInd;
371       n = m+1;
372       limit = m + vlist->vertexArray[i].degree; /* this is the first index
373                                                    not belonging to this vertex.*/
374       adj = vlist->adjArray;
375       /* do this in 2 phases. First phase: m and n are exactly one away.
376          goes on until the first duplicate is found. In this phase, there
377          is no need to assign values (no shifting is going on.) */
378       while ((adj[m] != adj[n]) && (n < limit)) {m++; n++;}
379       /* Phase 2: */
380       while (n<limit) {
381         while ((adj[m] == adj[n]) && (n<limit)) 
382           { n++; dupcount++; vlist->vertexArray[i].degree--;}
383         adj[m+1] = adj[n]; /*move the non duplicate back to its new position*/
384         m++; n++;
385       }
386     }
387 /* printf("number of duplicate edges removed = %d\n", dupcount/2);*/
388 /* Here is an assignment to a global variable.... */
389 if ((dupcount % 2) != 0) {printf("error. duplicates not even.\n"); }
390 E -= dupcount/2;
391 }
392
393 static void sort(int *adj, int fromIndex, int toIndex)
394 { int i,j, tmp;
395   short changed;
396   changed = 1;
397   for (i=toIndex; ((i>fromIndex) && changed); i--)
398     { changed = 0;
399       for (j=fromIndex; j<i; j++)
400         { if (adj[j] > adj[j+1])
401             { /* swap */
402               changed = 1;
403               tmp = adj[j];
404               adj[j] = adj[j+1];
405               adj[j+1] = tmp;
406             }
407         }
408     }
409 }
410
411 static void copyOut(VerticesListType *vertices, int *npe, int *pes)
412
413  int i;
414  int * adj;
415  Vertex * vertexRecs;
416  
417  adj = vertices->adjArray;
418  vertexRecs = vertices->vertexArray;
419
420  *npe = vertexRecs[CmiMyPe()].degree;
421  for (i=0; i<vertexRecs[CmiMyPe()].degree; i++)
422        pes[i] = adj[ vertexRecs[CmiMyPe()].adjListInd + i ];
423 }
424
425 static void printOut(VerticesListType *vertices)
426 {int i,j;
427  int * adj;
428  Vertex * vertexRecs;
429  FILE *fp;
430  char filename[20];
431  
432  adj = vertices->adjArray;
433  vertexRecs = vertices->vertexArray;
434
435  for (i=0; i<vertices->numVertices; i++)
436    {
437      /* Open graphN/graphi */
438      sprintf(filename, "graph%d/graph%d", vertices->numVertices, i);
439      fp = fopen(filename, "w");
440      fprintf(fp, "%d ", vertexRecs[i].degree);
441      for (j=0; j<vertexRecs[i].degree; j++)
442        fprintf(fp, "%d ", adj[ vertexRecs[i].adjListInd + j ]);
443      fprintf(fp, "\n");
444      fclose(fp);
445    }
446 }
447
448 static void initGraph(void)
449 { int i;
450   graph.numVertices = V;
451   graph.vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
452   _MEMCHECK(graph.vertexArray);
453   graph.adjArray = (int *) malloc(2*E*sizeof(int));
454   _MEMCHECK(graph.adjArray);
455
456   for (i=0; i< V; i++) {
457     graph.vertexArray[i].degree = 0;
458     graph.vertexArray[i].next = i*C;
459     graph.vertexArray[i].adjListInd = i*C;
460   }
461 }
462
463 static void enqueue(Q *q, int i);
464
465 static void diameter(void)
466 {
467   Q * makeQueue();
468   int i,j, k, v, w, start;
469   int *distance;
470   int *histogram;
471   Q * q;
472   int dia;
473   float average;
474
475   distance = (int *)calloc(V, sizeof(int));
476   histogram = (int *)calloc(V, sizeof(int));
477
478   for (i=0; i<V; i++) {
479     histogram[i] = 0; 
480   }
481   
482   dia = 0;
483   average = 0.0;
484   q = makeQueue();
485   for (i=0; i<V; i++) {
486     /* run non-weighted shortes distance algorithm for each vertex i */
487     for (j=0; j<V; j++) distance[j] = -1;
488     distance[i] = 0;
489     enqueue(q, i);
490     while (! (isEmpty(q))) {
491       v = dequeue(q);
492       
493       start=graph.vertexArray[v].adjListInd;
494       for (k=0; k< graph.vertexArray[i].degree; k++) {
495         w = graph.adjArray[k+start];
496         if (distance[w] == -1) {
497           distance[w] = distance[v] + 1;
498           enqueue(q, w);
499         }
500       }
501     }
502     for (j=0; j<V; j++) {
503       if (distance[j] > dia) dia = distance[j];
504       average += distance[j];
505       histogram[ distance[j]]++;
506     }
507   }
508   average = average / (V*V);
509   printf("the diameter is: %d, average internode distance = %f\n", 
510          dia, average);
511   /*for (i = 0; i< 6; i++) printf("histo[%d] = %d\n", i, histogram[i]);*/
512 }
513
514 /* ------------------------------------------------- */
515 /* The queue ADT */
516
517 static Q * makeQueue()
518 {
519   Q *q = (Q *) malloc(sizeof(Q));
520   _MEMCHECK(q);
521   q->size = VMAX;
522   q->numElements = 0;
523   q->head = 1;
524   q->tail = 0;
525   q->buf = (int *) malloc(VMAX*sizeof(int));
526   _MEMCHECK(q->buf);
527   return q;
528 }
529
530 static void enqueue(Q * q, int i) {
531   q->tail++;
532   if (q->tail == q->size) q->tail = 0; /* no overflows possible */
533   q->buf[q->tail] = i;
534   q->numElements++;
535 }
536
537 static int dequeue(Q *q) {
538   int r;
539   r = q->buf[q->head++];
540   if (q->head == q->size) q->head = 0;
541   q->numElements--;
542   return r;
543 }
544
545 static int isEmpty(Q * q) {
546   return (q->numElements == 0) ;
547 }