changes made by Yogesh: when generating dense graph, the algorithm was not capable...
[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;
132 /* first add edges for a C-way spanning tree.*/
133 int c1;
134 int varr[V];
135 if (C>1) c1 = C-1;
136
137 for (i=0; i< V/c1; i++)
138   for (j=0; j<c1; j++) {
139       w = c1*i + j +1; 
140       /* printf("considering (%d, %d)\n", i, w);  */
141       if (w < V) {
142         addEdge(EdgeList,i,w);
143         /* printf(" --- added.\n"); */
144       }
145       else /*printf(" not added.\n")*/; 
146   }
147
148 n -= (V-1);
149
150 for (i=0; i<n; i++) 
151    {
152      do {
153            x = rand() % V;
154         } while (connections(x) >= C);
155      do {
156            y = rand() % V;
157         } while ((y == x) || connections(y) >= C);
158      if (edgeExists(x,y)) {
159           if (i==n-1) addspEdge(EdgeList,x,y);
160           else i--;
161      }
162      else  
163        addEdge(EdgeList, x, y);
164    }
165 }
166
167 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E);
168 void sortAdjArrays(VerticesListType *vlist);
169 static void sort(int *adj, int fromIndex, int toIndex);
170 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E);
171
172 VerticesListType * 
173 InitVertices(EdgeList, V,E)
174      EdgeListType * EdgeList;
175      int V;
176      int E;
177 { /* returns a structure of type VerticesListType, which contains an arry of 
178      vertex records, and an array of adjacency information. See typedef. */
179   /* First allocate the adjacency subarray of size E, and vertex subarray size V.
180      Then count the occurences of each vertex in the Edgelist in vertex.degree.
181      Then compute the real adjListInd = sum from 0 to i-1 of the previous degrees.
182      Then, traverse edge list, and enter each edge in two adj lists.
183      Then sort individual adj-lists, separately. */
184   VerticesListType * vlist;
185
186   vlist = (VerticesListType *) malloc(sizeof(VerticesListType));
187   _MEMCHECK(vlist);
188   vlist->numVertices = V;
189   vlist->vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
190   _MEMCHECK(vlist->vertexArray);
191   vlist->adjArray = (int *) malloc(2*E*sizeof(int)); 
192                     /* as each edge is entered twice */
193   _MEMCHECK(vlist->adjArray);
194   countDegrees(EdgeList->edges, vlist->vertexArray, V, E);
195   fillAdjArray(EdgeList->edges, vlist, V, E);
196   sortAdjArrays(vlist);
197   return(vlist);
198 }
199
200 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E)
201 { /* initialize the degrees of all vertices to 0. 
202      Traverse the edge list, incrementing the degree of the 2 nodes for each edge.
203      */
204  int i, count;
205  
206  for (i=0; i<V; i++)
207    { vertRecs[i].degree = 0;
208      vertRecs[i].next = 0;}
209  for (i=0; i<E; i++)
210    {vertRecs[ edges[i].node1 ].degree++;
211     vertRecs[ edges[i].node2 ].degree++;}
212
213 /* now fill adjListInd, by starting a counter at 0, and adding degrees of visited
214    nodes. */
215  count = 0;
216  for (i=0; i<V; i++)
217    { vertRecs[i].adjListInd = count;
218      count += vertRecs[i].degree;
219    }
220 }
221
222 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E)
223 { /* Insert each edge <x,y> as an entry y in x's adj list, and vice versa. */
224   int i, x,y;
225  int * adj;
226  Vertex * vertexRecs;
227
228  adj = vlist->adjArray;
229  vertexRecs = vlist->vertexArray;
230
231   for (i=0; i<E; i++)
232     { x = edges[i].node1; y = edges[i].node2;
233       adj[ vertexRecs[x].adjListInd + vertexRecs[x].next ] = y;
234       vertexRecs[x].next++;
235       adj[ vertexRecs[y].adjListInd + vertexRecs[y].next ] = x;
236       vertexRecs[y].next++;
237     }
238 }
239
240 void sortAdjArrays(VerticesListType *vlist)
241 { /* sort each section of the array corresponding to each vertex. */
242   int V, i;
243   int dupcount;
244
245   V = vlist->numVertices;
246   for (i=0; i<V; i++)
247     { sort(vlist->adjArray, 
248            vlist->vertexArray[i].adjListInd,
249            vlist->vertexArray[i].adjListInd + vlist->vertexArray[i].degree -1);
250     }
251   /* eliminate duplicates. May be should be merged with above? */
252   dupcount = 0;
253   for (i=0; i<V; i++)
254     { int m,n, limit;
255       int * adj;
256
257       m = vlist->vertexArray[i].adjListInd;
258       n = m+1;
259       limit = m + vlist->vertexArray[i].degree; /* this is the first index
260                                                    not belonging to this vertex.*/
261       adj = vlist->adjArray;
262       /* do this in 2 phases. First phase: m and n are exactly one away.
263          goes on until the first duplicate is found. In this phase, there
264          is no need to assign values (no shifting is going on.) */
265       while ((adj[m] != adj[n]) && (n < limit)) {m++; n++;}
266       /* Phase 2: */
267       while (n<limit) {
268         while ((adj[m] == adj[n]) && (n<limit)) 
269           { n++; dupcount++; vlist->vertexArray[i].degree--;}
270         adj[m+1] = adj[n]; /*move the non duplicate back to its new position*/
271         m++; n++;
272       }
273     }
274 /* printf("number of duplicate edges removed = %d\n", dupcount/2);*/
275 /* Here is an assignment to a global variable.... */
276 if ((dupcount % 2) != 0) {printf("error. duplicates not even.\n"); }
277 E -= dupcount/2;
278 }
279
280 static void sort(int *adj, int fromIndex, int toIndex)
281 { int i,j, tmp;
282   short changed;
283   changed = 1;
284   for (i=toIndex; ((i>fromIndex) && changed); i--)
285     { changed = 0;
286       for (j=fromIndex; j<i; j++)
287         { if (adj[j] > adj[j+1])
288             { /* swap */
289               changed = 1;
290               tmp = adj[j];
291               adj[j] = adj[j+1];
292               adj[j+1] = tmp;
293             }
294         }
295     }
296 }
297
298 static void copyOut(VerticesListType *vertices, int *npe, int *pes)
299
300  int i;
301  int * adj;
302  Vertex * vertexRecs;
303  
304  adj = vertices->adjArray;
305  vertexRecs = vertices->vertexArray;
306
307  *npe = vertexRecs[CmiMyPe()].degree;
308  for (i=0; i<vertexRecs[CmiMyPe()].degree; i++)
309        pes[i] = adj[ vertexRecs[CmiMyPe()].adjListInd + i ];
310 }
311
312 static void printOut(VerticesListType *vertices)
313 {int i,j;
314  int * adj;
315  Vertex * vertexRecs;
316  FILE *fp;
317  char filename[20];
318  
319  adj = vertices->adjArray;
320  vertexRecs = vertices->vertexArray;
321
322  for (i=0; i<vertices->numVertices; i++)
323    {
324      /* Open graphN/graphi */
325      sprintf(filename, "graph%d/graph%d", vertices->numVertices, i);
326      fp = fopen(filename, "w");
327      fprintf(fp, "%d ", vertexRecs[i].degree);
328      for (j=0; j<vertexRecs[i].degree; j++)
329        fprintf(fp, "%d ", adj[ vertexRecs[i].adjListInd + j ]);
330      fprintf(fp, "\n");
331      fclose(fp);
332    }
333 }
334
335 static void initGraph(void)
336 { int i;
337   graph.numVertices = V;
338   graph.vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
339   _MEMCHECK(graph.vertexArray);
340   graph.adjArray = (int *) malloc(2*E*sizeof(int));
341   _MEMCHECK(graph.adjArray);
342
343   for (i=0; i< V; i++) {
344     graph.vertexArray[i].degree = 0;
345     graph.vertexArray[i].next = i*C;
346     graph.vertexArray[i].adjListInd = i*C;
347   }
348 }
349
350 static void enqueue(Q *q, int i);
351
352 static void diameter(void)
353 {
354   Q * makeQueue();
355   int i,j, k, v, w, start;
356   int *distance;
357   int *histogram;
358   Q * q;
359   int dia;
360   float average;
361
362   distance = (int *)calloc(V, sizeof(int));
363   histogram = (int *)calloc(V, sizeof(int));
364
365   for (i=0; i<V; i++) {
366     histogram[i] = 0; 
367   }
368   
369   dia = 0;
370   average = 0.0;
371   q = makeQueue();
372   for (i=0; i<V; i++) {
373     /* run non-weighted shortes distance algorithm for each vertex i */
374     for (j=0; j<V; j++) distance[j] = -1;
375     distance[i] = 0;
376     enqueue(q, i);
377     while (! (isEmpty(q))) {
378       v = dequeue(q);
379       
380       start=graph.vertexArray[v].adjListInd;
381       for (k=0; k< graph.vertexArray[i].degree; k++) {
382         w = graph.adjArray[k+start];
383         if (distance[w] == -1) {
384           distance[w] = distance[v] + 1;
385           enqueue(q, w);
386         }
387       }
388     }
389     for (j=0; j<V; j++) {
390       if (distance[j] > dia) dia = distance[j];
391       average += distance[j];
392       histogram[ distance[j]]++;
393     }
394   }
395   average = average / (V*V);
396   printf("the diameter is: %d, average internode distance = %f\n", 
397          dia, average);
398   /*for (i = 0; i< 6; i++) printf("histo[%d] = %d\n", i, histogram[i]);*/
399 }
400
401 /* ------------------------------------------------- */
402 /* The queue ADT */
403
404 static Q * makeQueue()
405 {
406   Q *q = (Q *) malloc(sizeof(Q));
407   _MEMCHECK(q);
408   q->size = VMAX;
409   q->head = 1;
410   q->tail = 0;
411   q->buf = (int *) malloc(VMAX*sizeof(int));
412   _MEMCHECK(q->buf);
413   return q;
414 }
415
416 static void enqueue(Q * q, int i) {
417   q->tail++;
418   if (q->tail == q->size) q->tail = 0; /* no overflows possible */
419   q->buf[q->tail] = i;
420   q->numElements++;
421 }
422
423 static int dequeue(Q *q) {
424   int r;
425   r = q->buf[q->head++];
426   if (q->head == q->size) q->head = 0;
427   q->numElements--;
428   return r;
429 }
430
431 static int isEmpty(Q * q) {
432   return (q->numElements == 0) ;
433 }