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