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