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