don''t let the dense graph generation function only dump the output to disk files...
[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 Output form: directory graphN/ containing files graph0 ... graphN-1
12              file graphK has C, the number of connections, followed by
13              a list of C vertices that K is connected to
14
15 Modified from the original: changed output format, and converted main to a parametered function
16 */
17 #include <stdio.h>
18 #include <stdlib.h>
19
20 /* comment this out to test and change CmiPrintf to printf */
21 #include "converse.h"
22 #include "typedefs.h"
23
24 int addEdge(EdgeListType *l,int fm,int to);
25 int edgeExists(int fm, int to);
26 static Q * makeQueue();
27 static int isEmpty(Q*);
28 static int dequeue(Q*);
29
30 #define VMAX 2050
31 int V; /* no. of vertices */
32 int E; /* no. of edges */
33 int C; /* no. of connections per vertex */
34 int seed;
35
36 VerticesListType graph;
37
38 VerticesListType * InitVertices();
39
40
41 /* For testing... 
42 main(int argc, char **argv)
43 {
44   gengraph(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]));
45 }
46 */
47
48 static void printOut(VerticesListType *vertices);
49 static void copyOut(VerticesListType *vertices, int *npe, int *pes);
50 static void initGraph(void);
51 static void diameter(void);
52 static void AddEdges(EdgeListType *EdgeList, int V, int n);
53
54 void gengraph(int pV, int pC, int pseed, int *pes, int *npe, int tofile)
55 { int i;
56   EdgeListType * EdgeList;
57   /* VerticesListType * vertices; */
58   extern EdgeListType * InitEdgeList();
59   char dircmd[20], dirname[10];
60
61   V = pV;
62   C = pC;
63   seed = pseed;
64   
65   if (CmiMyPe() == 0)
66   CmiPrintf("for %d PEs, connectivity %d... ", V, C);
67
68   /* make a directory */
69   if (tofile && CmiMyPe() == 0) {
70   sprintf(dirname, "graph%d", V);
71   sprintf(dircmd, "mkdir %s", dirname);
72   system(dircmd);
73   }
74   
75   /* for (i=0; i<seed; i++) rand(); */
76   for (i=0; i<seed; i++) CrnRand();
77   if ((V*C %2) != 0) printf("V*C must be even\n");
78   E = V*C/2;
79   initGraph();
80   EdgeList = InitEdgeList(E);
81   AddEdges(EdgeList, V, E); 
82   /*  vertices = (VerticesListType *) InitVertices(EdgeList, V,E); */
83
84   if (tofile) {
85     if (CmiMyPe()==0) printOut(&graph);
86   }
87   else copyOut(&graph, npe, pes);
88
89   if (CmiMyPe()==0) diameter();
90 }
91
92
93 static void AddEdges(EdgeListType *EdgeList, int V, int n)
94    /* Add more edges to make up a total of E edges */
95 {int i,j,w,x,y;
96 /* first add edges for a C-way spanning tree.*/
97 int c1;
98 if (C>1) c1 = C-1;
99
100 for (i=0; i< V/c1; i++)
101   for (j=0; j<c1; j++) {
102       w = c1*i + j +1; 
103       /* printf("considering (%d, %d)\n", i, w);  */
104       if (w < V) {
105         addEdge(EdgeList,i,w);
106         /* printf(" --- added.\n"); */
107       }
108       else /*printf(" not added.\n")*/; 
109   }
110 n -= (V-1);
111
112  for (i=0; i<n; i++) 
113    {
114      do {
115        do {
116          x = CrnRand() % V;
117        } while (connections(x) >= C);
118        do {
119          y = CrnRand() % V;
120        } while ((y== x) || connections(y) >= C);
121      } while (edgeExists(x,y));
122      addEdge(EdgeList, x, y);
123    }
124 }
125
126 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E);
127 void sortAdjArrays(VerticesListType *vlist);
128 static void sort(int *adj, int fromIndex, int toIndex);
129 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E);
130
131 VerticesListType * 
132 InitVertices(EdgeList, V,E)
133      EdgeListType * EdgeList;
134      int V;
135      int E;
136 { /* returns a structure of type VerticesListType, which contains an arry of 
137      vertex records, and an array of adjacency information. See typedef. */
138   /* First allocate the adjacency subarray of size E, and vertex subarray size V.
139      Then count the occurences of each vertex in the Edgelist in vertex.degree.
140      Then compute the real adjListInd = sum from 0 to i-1 of the previous degrees.
141      Then, traverse edge list, and enter each edge in two adj lists.
142      Then sort individual adj-lists, separately. */
143   VerticesListType * vlist;
144
145   vlist = (VerticesListType *) malloc(sizeof(VerticesListType));
146   _MEMCHECK(vlist);
147   vlist->numVertices = V;
148   vlist->vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
149   _MEMCHECK(vlist->vertexArray);
150   vlist->adjArray = (int *) malloc(2*E*sizeof(int)); 
151                     /* as each edge is entered twice */
152   _MEMCHECK(vlist->adjArray);
153   countDegrees(EdgeList->edges, vlist->vertexArray, V, E);
154   fillAdjArray(EdgeList->edges, vlist, V, E);
155   sortAdjArrays(vlist);
156   return(vlist);
157 }
158
159 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E)
160 { /* initialize the degrees of all vertices to 0. 
161      Traverse the edge list, incrementing the degree of the 2 nodes for each edge.
162      */
163  int i, count;
164  
165  for (i=0; i<V; i++)
166    { vertRecs[i].degree = 0;
167      vertRecs[i].next = 0;}
168  for (i=0; i<E; i++)
169    {vertRecs[ edges[i].node1 ].degree++;
170     vertRecs[ edges[i].node2 ].degree++;}
171
172 /* now fill adjListInd, by starting a counter at 0, and adding degrees of visited
173    nodes. */
174  count = 0;
175  for (i=0; i<V; i++)
176    { vertRecs[i].adjListInd = count;
177      count += vertRecs[i].degree;
178    }
179 }
180
181 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E)
182 { /* Insert each edge <x,y> as an entry y in x's adj list, and vice versa. */
183   int i, x,y;
184  int * adj;
185  Vertex * vertexRecs;
186
187  adj = vlist->adjArray;
188  vertexRecs = vlist->vertexArray;
189
190   for (i=0; i<E; i++)
191     { x = edges[i].node1; y = edges[i].node2;
192       adj[ vertexRecs[x].adjListInd + vertexRecs[x].next ] = y;
193       vertexRecs[x].next++;
194       adj[ vertexRecs[y].adjListInd + vertexRecs[y].next ] = x;
195       vertexRecs[y].next++;
196     }
197 }
198
199 void sortAdjArrays(VerticesListType *vlist)
200 { /* sort each section of the array corresponding to each vertex. */
201   int V, i;
202   int dupcount;
203
204   V = vlist->numVertices;
205   for (i=0; i<V; i++)
206     { sort(vlist->adjArray, 
207            vlist->vertexArray[i].adjListInd,
208            vlist->vertexArray[i].adjListInd + vlist->vertexArray[i].degree -1);
209     }
210   /* eliminate duplicates. May be should be merged with above? */
211   dupcount = 0;
212   for (i=0; i<V; i++)
213     { int m,n, limit;
214       int * adj;
215
216       m = vlist->vertexArray[i].adjListInd;
217       n = m+1;
218       limit = m + vlist->vertexArray[i].degree; /* this is the first index
219                                                    not belonging to this vertex.*/
220       adj = vlist->adjArray;
221       /* do this in 2 phases. First phase: m and n are exactly one away.
222          goes on until the first duplicate is found. In this phase, there
223          is no need to assign values (no shifting is going on.) */
224       while ((adj[m] != adj[n]) && (n < limit)) {m++; n++;}
225       /* Phase 2: */
226       while (n<limit) {
227         while ((adj[m] == adj[n]) && (n<limit)) 
228           { n++; dupcount++; vlist->vertexArray[i].degree--;}
229         adj[m+1] = adj[n]; /*move the non duplicate back to its new position*/
230         m++; n++;
231       }
232     }
233 /* printf("number of duplicate edges removed = %d\n", dupcount/2);*/
234 /* Here is an assignment to a global variable.... */
235 if ((dupcount % 2) != 0) {printf("error. duplicates not even.\n"); }
236 E -= dupcount/2;
237 }
238
239 static void sort(int *adj, int fromIndex, int toIndex)
240 { int i,j, tmp;
241   short changed;
242   changed = 1;
243   for (i=toIndex; ((i>fromIndex) && changed); i--)
244     { changed = 0;
245       for (j=fromIndex; j<i; j++)
246         { if (adj[j] > adj[j+1])
247             { /* swap */
248               changed = 1;
249               tmp = adj[j];
250               adj[j] = adj[j+1];
251               adj[j+1] = tmp;
252             }
253         }
254     }
255 }
256
257 static void copyOut(VerticesListType *vertices, int *npe, int *pes)
258
259  int i;
260  int * adj;
261  Vertex * vertexRecs;
262  
263  adj = vertices->adjArray;
264  vertexRecs = vertices->vertexArray;
265
266  *npe = vertexRecs[CmiMyPe()].degree;
267  for (i=0; i<vertexRecs[CmiMyPe()].degree; i++)
268        pes[i] = adj[ vertexRecs[CmiMyPe()].adjListInd + i ];
269 }
270
271 static void printOut(VerticesListType *vertices)
272 {int i,j;
273  int * adj;
274  Vertex * vertexRecs;
275  FILE *fp;
276  char filename[20];
277  
278  adj = vertices->adjArray;
279  vertexRecs = vertices->vertexArray;
280
281  for (i=0; i<vertices->numVertices; i++)
282    {
283      /* Open graphN/graphi */
284      sprintf(filename, "graph%d/graph%d", vertices->numVertices, i);
285      fp = fopen(filename, "w");
286      fprintf(fp, "%d ", vertexRecs[i].degree);
287      for (j=0; j<vertexRecs[i].degree; j++)
288        fprintf(fp, "%d ", adj[ vertexRecs[i].adjListInd + j ]);
289      fprintf(fp, "\n");
290      fclose(fp);
291    }
292 }
293
294 static void initGraph(void)
295 { int i;
296   graph.numVertices = V;
297   graph.vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
298   _MEMCHECK(graph.vertexArray);
299   graph.adjArray = (int *) malloc(2*E*sizeof(int));
300   _MEMCHECK(graph.adjArray);
301
302   for (i=0; i< V; i++) {
303     graph.vertexArray[i].degree = 0;
304     graph.vertexArray[i].next = i*C;
305     graph.vertexArray[i].adjListInd = i*C;
306   }
307 }
308
309 static void enqueue(Q *q, int i);
310
311 static void diameter(void)
312 {
313   Q * makeQueue();
314   int i,j, k, v, w, start;
315   int *distance;
316   int *histogram;
317   Q * q;
318   int dia;
319   float average;
320
321   distance = (int *)calloc(V, sizeof(int));
322   histogram = (int *)calloc(V, sizeof(int));
323
324   for (i=0; i<V; i++) {
325     histogram[i] = 0; 
326   }
327   
328   dia = 0;
329   average = 0.0;
330   q = makeQueue();
331   for (i=0; i<V; i++) {
332     /* run non-weighted shortes distance algorithm for each vertex i */
333     for (j=0; j<V; j++) distance[j] = -1;
334     distance[i] = 0;
335     enqueue(q, i);
336     while (! (isEmpty(q))) {
337       v = dequeue(q);
338       
339       start=graph.vertexArray[v].adjListInd;
340       for (k=0; k< graph.vertexArray[i].degree; k++) {
341         w = graph.adjArray[k+start];
342         if (distance[w] == -1) {
343           distance[w] = distance[v] + 1;
344           enqueue(q, w);
345         }
346       }
347     }
348     for (j=0; j<V; j++) {
349       if (distance[j] > dia) dia = distance[j];
350       average += distance[j];
351       histogram[ distance[j]]++;
352     }
353   }
354   average = average / (V*V);
355   printf("the diameter is: %d, average internode distance = %f\n", 
356          dia, average);
357   /*for (i = 0; i< 6; i++) printf("histo[%d] = %d\n", i, histogram[i]);*/
358 }
359
360 /* ------------------------------------------------- */
361 /* The queue ADT */
362
363 static Q * makeQueue()
364 {
365   Q *q = (Q *) malloc(sizeof(Q));
366   _MEMCHECK(q);
367   q->size = VMAX;
368   q->head = 1;
369   q->tail = 0;
370   q->buf = (int *) malloc(VMAX*sizeof(int));
371   _MEMCHECK(q->buf);
372   return q;
373 }
374
375 static void enqueue(Q * q, int i) {
376   q->tail++;
377   if (q->tail == q->size) q->tail = 0; /* no overflows possible */
378   q->buf[q->tail] = i;
379   q->numElements++;
380 }
381
382 static int dequeue(Q *q) {
383   int r;
384   r = q->buf[q->head++];
385   if (q->head == q->size) q->head = 0;
386   q->numElements--;
387   return r;
388 }
389
390 static int isEmpty(Q * q) {
391   return (q->numElements == 0) ;
392 }