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