changed by Yogesh, fixed some logic bug in generating dense graph.
[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... ", 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[V][2];
134         int varrlen,count=0;
135         int flag=0;
136
137         /* first add edges for a C-way spanning tree.*/
138         
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(EdgeList,i,w);
146                 count++;
147               }
148           }
149         
150         /*varr is array of vertices and free connection for each vertex*/
151         
152         for(i=0;i<V;i++)
153                 for (j=0;j<2;j++)
154                         varr[i][j]=0;   
155         j=0;
156         for (i=0;i<V;i++)
157                 if(connections(i)<C)
158                 {
159                  varr[j][0]=i;
160                  varr[j][1]=C-connections(i);
161                  j++;
162                 }
163         varrlen=j;
164         
165         /*for all edges except last 10 , edge is formed by randomly selecting vertices from varr*/
166
167         n -= count;
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         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                                 if (j==k-1) addspEdge(EdgeList,varr[x][0],varr[y][0]);
231                                 else do {
232                                                 y = rand() % varrlen;
233                                           } while (y == x);
234                                 if ((j!=k-1)||(!edgeExists(varr[x][0],varr[y][0])))
235                                 addEdge(EdgeList,varr[x][0],varr[y][0]); 
236                                 varr[x][1]=varr[x][1]-1;
237                                 varr[y][1]=varr[y][1]-1;
238                                                 
239                                 if (varr[x][1]==0) 
240                                         {
241                                          flag=1;
242                                          for (i=x;i<varrlen-1;i++)
243                                                 {       
244                                                  varr[i][0]=varr[i+1][0];
245                                                  varr[i][1]=varr[i+1][1];
246                                                 }
247                                          varrlen--;
248                                         }       
249                                 if ((y>x)&&(flag))         
250                                         {
251                                          if (varr[y-1][1]==0)   
252                                                         {
253                                                           for (i=y-1;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                                         }                               
261                                 else if (varr[y][1]==0)
262                                         {
263                                                  for (i=y;i<varrlen-1;i++)
264                                                         {       
265                                                          varr[i][0]=varr[i+1][0];
266                                                          varr[i][1]=varr[i+1][1];
267                                                         }
268                                                  varrlen--;
269                                         }
270                         }             
271 }
272
273 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E);
274 void sortAdjArrays(VerticesListType *vlist);
275 static void sort(int *adj, int fromIndex, int toIndex);
276 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E);
277
278 VerticesListType * 
279 InitVertices(EdgeList, V,E)
280      EdgeListType * EdgeList;
281      int V;
282      int E;
283 { /* returns a structure of type VerticesListType, which contains an arry of 
284      vertex records, and an array of adjacency information. See typedef. */
285   /* First allocate the adjacency subarray of size E, and vertex subarray size V.
286      Then count the occurences of each vertex in the Edgelist in vertex.degree.
287      Then compute the real adjListInd = sum from 0 to i-1 of the previous degrees.
288      Then, traverse edge list, and enter each edge in two adj lists.
289      Then sort individual adj-lists, separately. */
290   VerticesListType * vlist;
291
292   vlist = (VerticesListType *) malloc(sizeof(VerticesListType));
293   _MEMCHECK(vlist);
294   vlist->numVertices = V;
295   vlist->vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
296   _MEMCHECK(vlist->vertexArray);
297   vlist->adjArray = (int *) malloc(2*E*sizeof(int)); 
298                     /* as each edge is entered twice */
299   _MEMCHECK(vlist->adjArray);
300   countDegrees(EdgeList->edges, vlist->vertexArray, V, E);
301   fillAdjArray(EdgeList->edges, vlist, V, E);
302   sortAdjArrays(vlist);
303   return(vlist);
304 }
305
306 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E)
307 { /* initialize the degrees of all vertices to 0. 
308      Traverse the edge list, incrementing the degree of the 2 nodes for each edge.
309      */
310  int i, count;
311  
312  for (i=0; i<V; i++)
313    { vertRecs[i].degree = 0;
314      vertRecs[i].next = 0;}
315  for (i=0; i<E; i++)
316    {vertRecs[ edges[i].node1 ].degree++;
317     vertRecs[ edges[i].node2 ].degree++;}
318
319 /* now fill adjListInd, by starting a counter at 0, and adding degrees of visited
320    nodes. */
321  count = 0;
322  for (i=0; i<V; i++)
323    { vertRecs[i].adjListInd = count;
324      count += vertRecs[i].degree;
325    }
326 }
327
328 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E)
329 { /* Insert each edge <x,y> as an entry y in x's adj list, and vice versa. */
330   int i, x,y;
331  int * adj;
332  Vertex * vertexRecs;
333
334  adj = vlist->adjArray;
335  vertexRecs = vlist->vertexArray;
336
337   for (i=0; i<E; i++)
338     { x = edges[i].node1; y = edges[i].node2;
339       adj[ vertexRecs[x].adjListInd + vertexRecs[x].next ] = y;
340       vertexRecs[x].next++;
341       adj[ vertexRecs[y].adjListInd + vertexRecs[y].next ] = x;
342       vertexRecs[y].next++;
343     }
344 }
345
346 void sortAdjArrays(VerticesListType *vlist)
347 { /* sort each section of the array corresponding to each vertex. */
348   int V, i;
349   int dupcount;
350
351   V = vlist->numVertices;
352   for (i=0; i<V; i++)
353     { sort(vlist->adjArray, 
354            vlist->vertexArray[i].adjListInd,
355            vlist->vertexArray[i].adjListInd + vlist->vertexArray[i].degree -1);
356     }
357   /* eliminate duplicates. May be should be merged with above? */
358   dupcount = 0;
359   for (i=0; i<V; i++)
360     { int m,n, limit;
361       int * adj;
362
363       m = vlist->vertexArray[i].adjListInd;
364       n = m+1;
365       limit = m + vlist->vertexArray[i].degree; /* this is the first index
366                                                    not belonging to this vertex.*/
367       adj = vlist->adjArray;
368       /* do this in 2 phases. First phase: m and n are exactly one away.
369          goes on until the first duplicate is found. In this phase, there
370          is no need to assign values (no shifting is going on.) */
371       while ((adj[m] != adj[n]) && (n < limit)) {m++; n++;}
372       /* Phase 2: */
373       while (n<limit) {
374         while ((adj[m] == adj[n]) && (n<limit)) 
375           { n++; dupcount++; vlist->vertexArray[i].degree--;}
376         adj[m+1] = adj[n]; /*move the non duplicate back to its new position*/
377         m++; n++;
378       }
379     }
380 /* printf("number of duplicate edges removed = %d\n", dupcount/2);*/
381 /* Here is an assignment to a global variable.... */
382 if ((dupcount % 2) != 0) {printf("error. duplicates not even.\n"); }
383 E -= dupcount/2;
384 }
385
386 static void sort(int *adj, int fromIndex, int toIndex)
387 { int i,j, tmp;
388   short changed;
389   changed = 1;
390   for (i=toIndex; ((i>fromIndex) && changed); i--)
391     { changed = 0;
392       for (j=fromIndex; j<i; j++)
393         { if (adj[j] > adj[j+1])
394             { /* swap */
395               changed = 1;
396               tmp = adj[j];
397               adj[j] = adj[j+1];
398               adj[j+1] = tmp;
399             }
400         }
401     }
402 }
403
404 static void copyOut(VerticesListType *vertices, int *npe, int *pes)
405
406  int i;
407  int * adj;
408  Vertex * vertexRecs;
409  
410  adj = vertices->adjArray;
411  vertexRecs = vertices->vertexArray;
412
413  *npe = vertexRecs[CmiMyPe()].degree;
414  for (i=0; i<vertexRecs[CmiMyPe()].degree; i++)
415        pes[i] = adj[ vertexRecs[CmiMyPe()].adjListInd + i ];
416 }
417
418 static void printOut(VerticesListType *vertices)
419 {int i,j;
420  int * adj;
421  Vertex * vertexRecs;
422  FILE *fp;
423  char filename[20];
424  
425  adj = vertices->adjArray;
426  vertexRecs = vertices->vertexArray;
427
428  for (i=0; i<vertices->numVertices; i++)
429    {
430      /* Open graphN/graphi */
431      sprintf(filename, "graph%d/graph%d", vertices->numVertices, i);
432      fp = fopen(filename, "w");
433      fprintf(fp, "%d ", vertexRecs[i].degree);
434      for (j=0; j<vertexRecs[i].degree; j++)
435        fprintf(fp, "%d ", adj[ vertexRecs[i].adjListInd + j ]);
436      fprintf(fp, "\n");
437      fclose(fp);
438    }
439 }
440
441 static void initGraph(void)
442 { int i;
443   graph.numVertices = V;
444   graph.vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
445   _MEMCHECK(graph.vertexArray);
446   graph.adjArray = (int *) malloc(2*E*sizeof(int));
447   _MEMCHECK(graph.adjArray);
448
449   for (i=0; i< V; i++) {
450     graph.vertexArray[i].degree = 0;
451     graph.vertexArray[i].next = i*C;
452     graph.vertexArray[i].adjListInd = i*C;
453   }
454 }
455
456 static void enqueue(Q *q, int i);
457
458 static void diameter(void)
459 {
460   Q * makeQueue();
461   int i,j, k, v, w, start;
462   int *distance;
463   int *histogram;
464   Q * q;
465   int dia;
466   float average;
467
468   distance = (int *)calloc(V, sizeof(int));
469   histogram = (int *)calloc(V, sizeof(int));
470
471   for (i=0; i<V; i++) {
472     histogram[i] = 0; 
473   }
474   
475   dia = 0;
476   average = 0.0;
477   q = makeQueue();
478   for (i=0; i<V; i++) {
479     /* run non-weighted shortes distance algorithm for each vertex i */
480     for (j=0; j<V; j++) distance[j] = -1;
481     distance[i] = 0;
482     enqueue(q, i);
483     while (! (isEmpty(q))) {
484       v = dequeue(q);
485       
486       start=graph.vertexArray[v].adjListInd;
487       for (k=0; k< graph.vertexArray[i].degree; k++) {
488         w = graph.adjArray[k+start];
489         if (distance[w] == -1) {
490           distance[w] = distance[v] + 1;
491           enqueue(q, w);
492         }
493       }
494     }
495     for (j=0; j<V; j++) {
496       if (distance[j] > dia) dia = distance[j];
497       average += distance[j];
498       histogram[ distance[j]]++;
499     }
500   }
501   average = average / (V*V);
502   printf("the diameter is: %d, average internode distance = %f\n", 
503          dia, average);
504   /*for (i = 0; i< 6; i++) printf("histo[%d] = %d\n", i, histogram[i]);*/
505 }
506
507 /* ------------------------------------------------- */
508 /* The queue ADT */
509
510 static Q * makeQueue()
511 {
512   Q *q = (Q *) malloc(sizeof(Q));
513   _MEMCHECK(q);
514   q->size = VMAX;
515   q->head = 1;
516   q->tail = 0;
517   q->buf = (int *) malloc(VMAX*sizeof(int));
518   _MEMCHECK(q->buf);
519   return q;
520 }
521
522 static void enqueue(Q * q, int i) {
523   q->tail++;
524   if (q->tail == q->size) q->tail = 0; /* no overflows possible */
525   q->buf[q->tail] = i;
526   q->numElements++;
527 }
528
529 static int dequeue(Q *q) {
530   int r;
531   r = q->buf[q->head++];
532   if (q->head == q->size) q->head = 0;
533   q->numElements--;
534   return r;
535 }
536
537 static int isEmpty(Q * q) {
538   return (q->numElements == 0) ;
539 }