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