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