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