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