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