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