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