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