A fix to dense graph generation code
[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                                 if (edgeExists(varr[x][0],varr[y][0])&&(j==k-1))
241                                         addspEdge(EdgeList,varr[x][0],varr[y][0]);
242                                 else    
243                                 {
244                                         while((y==x)||(edgeExists(varr[x][0],varr[y][0])))
245                                                 y = rand() % varrlen;
246                                         addEdge(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  *npe = vertexRecs[CmiMyPe()].degree;
430  for (i=0; i<vertexRecs[CmiMyPe()].degree; i++)
431        pes[i] = adj[ vertexRecs[CmiMyPe()].adjListInd + i ];
432 }
433
434 static void printOut(VerticesListType *vertices)
435 {int i,j;
436  int * adj;
437  Vertex * vertexRecs;
438  FILE *fp;
439  char filename[20];
440  
441  adj = vertices->adjArray;
442  vertexRecs = vertices->vertexArray;
443
444  for (i=0; i<vertices->numVertices; i++)
445    {
446      /* Open graphN/graphi */
447      sprintf(filename, "graph%d/graph%d", vertices->numVertices, i);
448      fp = fopen(filename, "w");
449      fprintf(fp, "%d ", vertexRecs[i].degree);
450      for (j=0; j<vertexRecs[i].degree; j++)
451        fprintf(fp, "%d ", adj[ vertexRecs[i].adjListInd + j ]);
452      fprintf(fp, "\n");
453      fclose(fp);
454    }
455 }
456
457 static void initGraph(void)
458 { int i;
459   graph.numVertices = V;
460   graph.vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
461   _MEMCHECK(graph.vertexArray);
462   graph.adjArray = (int *) malloc(2*E*sizeof(int));
463   _MEMCHECK(graph.adjArray);
464
465   for (i=0; i< V; i++) {
466     graph.vertexArray[i].degree = 0;
467     graph.vertexArray[i].next = i*C;
468     graph.vertexArray[i].adjListInd = i*C;
469   }
470 }
471
472 static void enqueue(Q *q, int i);
473
474 static void diameter(void)
475 {
476   Q * makeQueue();
477   int i,j, k, v, w, start;
478   int *distance;
479   int *histogram;
480   Q * q;
481   int dia;
482   float average;
483
484   distance = (int *)calloc(V, sizeof(int));
485   histogram = (int *)calloc(V, sizeof(int));
486
487   for (i=0; i<V; i++) {
488     histogram[i] = 0; 
489   }
490   
491   dia = 0;
492   average = 0.0;
493   q = makeQueue();
494   for (i=0; i<V; i++) {
495     /* run non-weighted shortes distance algorithm for each vertex i */
496     for (j=0; j<V; j++) distance[j] = -1;
497     distance[i] = 0;
498     enqueue(q, i);
499     while (! (isEmpty(q))) {
500       v = dequeue(q);
501       
502       start=graph.vertexArray[v].adjListInd;
503       for (k=0; k< graph.vertexArray[i].degree; k++) {
504         w = graph.adjArray[k+start];
505         if (distance[w] == -1) {
506           distance[w] = distance[v] + 1;
507           enqueue(q, w);
508         }
509       }
510     }
511     for (j=0; j<V; j++) {
512       if (distance[j] > dia) dia = distance[j];
513       average += distance[j];
514       histogram[ distance[j]]++;
515     }
516   }
517   average = average / (V*V);
518   printf("the diameter is: %d, average internode distance = %f\n", 
519          dia, average);
520   /*for (i = 0; i< 6; i++) printf("histo[%d] = %d\n", i, histogram[i]);*/
521 }
522
523 /* ------------------------------------------------- */
524 /* The queue ADT */
525
526 static Q * makeQueue()
527 {
528   Q *q = (Q *) malloc(sizeof(Q));
529   _MEMCHECK(q);
530   q->size = VMAX;
531   q->numElements = 0;
532   q->head = 1;
533   q->tail = 0;
534   q->buf = (int *) malloc(VMAX*sizeof(int));
535   _MEMCHECK(q->buf);
536   return q;
537 }
538
539 static void enqueue(Q * q, int i) {
540   q->tail++;
541   if (q->tail == q->size) q->tail = 0; /* no overflows possible */
542   q->buf[q->tail] = i;
543   q->numElements++;
544 }
545
546 static int dequeue(Q *q) {
547   int r;
548   r = q->buf[q->head++];
549   if (q->head == q->size) q->head = 0;
550   q->numElements--;
551   return r;
552 }
553
554 static int isEmpty(Q * q) {
555   return (q->numElements == 0) ;
556 }