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