Added checks for null pointer allocation.
[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   _MEMCHECK(vlist);
119   vlist->numVertices = V;
120   vlist->vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
121   _MEMCHECK(vlist->vertexArray);
122   vlist->adjArray = (int *) malloc(2*E*sizeof(int)); 
123                     /* as each edge is entered twice */
124   _MEMCHECK(vlist->adjArray);
125   countDegrees(EdgeList->edges, vlist->vertexArray, V, E);
126   fillAdjArray(EdgeList->edges, vlist, V, E);
127   sortAdjArrays(vlist);
128   return(vlist);
129 }
130
131 countDegrees(edges, vertRecs, V, E)
132      Edge * edges; /* array of Edge records */
133      Vertex * vertRecs; /* array of Vertex records */
134      int V;
135      int E;
136 { /* initialize the degrees of all vertices to 0. 
137      Traverse the edge list, incrementing the degree of the 2 nodes for each edge.
138      */
139  int i, count;
140  
141  for (i=0; i<V; i++)
142    { vertRecs[i].degree = 0;
143      vertRecs[i].next = 0;}
144  for (i=0; i<E; i++)
145    {vertRecs[ edges[i].node1 ].degree++;
146     vertRecs[ edges[i].node2 ].degree++;}
147
148 /* now fill adjListInd, by starting a counter at 0, and adding degrees of visited
149    nodes. */
150  count = 0;
151  for (i=0; i<V; i++)
152    { vertRecs[i].adjListInd = count;
153      count += vertRecs[i].degree;
154    }
155 }
156
157 fillAdjArray(edges, vlist, V, E)
158      Edge * edges;
159      VerticesListType * vlist;
160      int V;
161      int E;
162 { /* Insert each edge <x,y> as an entry y in x's adj list, and vice versa. */
163   int i, x,y;
164  int * adj;
165  Vertex * vertexRecs;
166
167  adj = vlist->adjArray;
168  vertexRecs = vlist->vertexArray;
169
170   for (i=0; i<E; i++)
171     { x = edges[i].node1; y = edges[i].node2;
172       adj[ vertexRecs[x].adjListInd + vertexRecs[x].next ] = y;
173       vertexRecs[x].next++;
174       adj[ vertexRecs[y].adjListInd + vertexRecs[y].next ] = x;
175       vertexRecs[y].next++;
176     }
177 }
178
179 sortAdjArrays(vlist)
180      VerticesListType * vlist;
181 { /* sort each section of the array corresponding to each vertex. */
182   int V, i;
183   int dupcount;
184
185   V = vlist->numVertices;
186   for (i=0; i<V; i++)
187     { sort(vlist->adjArray, 
188            vlist->vertexArray[i].adjListInd,
189            vlist->vertexArray[i].adjListInd + vlist->vertexArray[i].degree -1);
190     }
191   /* eliminate duplicates. May be should be merged with above? */
192   dupcount = 0;
193   for (i=0; i<V; i++)
194     { int m,n, limit;
195       int * adj;
196
197       m = vlist->vertexArray[i].adjListInd;
198       n = m+1;
199       limit = m + vlist->vertexArray[i].degree; /* this is the first index
200                                                    not belonging to this vertex.*/
201       adj = vlist->adjArray;
202       /* do this in 2 phases. First phase: m and n are exactly one away.
203          goes on until the first duplicate is found. In this phase, there
204          is no need to assign values (no shifting is going on.) */
205       while ((adj[m] != adj[n]) && (n < limit)) {m++; n++;}
206       /* Phase 2: */
207       while (n<limit) {
208         while ((adj[m] == adj[n]) && (n<limit)) 
209           { n++; dupcount++; vlist->vertexArray[i].degree--;}
210         adj[m+1] = adj[n]; /*move the non duplicate back to its new position*/
211         m++; n++;
212       }
213     }
214 /* printf("number of duplicate edges removed = %d\n", dupcount/2);*/
215 /* Here is an assignment to a global variable.... */
216 if ((dupcount % 2) != 0) {printf("error. duplicates not even.\n"); }
217 E -= dupcount/2;
218 }
219
220 sort(adj, fromIndex, toIndex)
221      int * adj;
222      int fromIndex;
223      int toIndex;
224 { int i,j, tmp;
225   short changed;
226   changed = 1;
227   for (i=toIndex; ((i>fromIndex) && changed); i--)
228     { changed = 0;
229       for (j=fromIndex; j<i; j++)
230         { if (adj[j] > adj[j+1])
231             { /* swap */
232               changed = 1;
233               tmp = adj[j];
234               adj[j] = adj[j+1];
235               adj[j+1] = tmp;
236             }
237         }
238     }
239 }
240
241 printOut(vertices)
242 VerticesListType * vertices ;
243 {int i,j;
244  int * adj;
245  Vertex * vertexRecs;
246  FILE *fp;
247  char filename[20];
248  
249  adj = vertices->adjArray;
250  vertexRecs = vertices->vertexArray;
251
252  for (i=0; i<vertices->numVertices; i++)
253    {
254      /* Open graphN/graphi */
255      sprintf(filename, "graph%d/graph%d", vertices->numVertices, i);
256      fp = fopen(filename, "w");
257      fprintf(fp, "%d ", vertexRecs[i].degree);
258      for (j=0; j<vertexRecs[i].degree; j++)
259        fprintf(fp, "%d ", adj[ vertexRecs[i].adjListInd + j ]);
260      fprintf(fp, "\n");
261      fclose(fp);
262    }
263 }
264
265 initGraph()
266 { int i;
267   graph.numVertices = V;
268   graph.vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
269   _MEMCHECK(graph.vertexArray);
270   graph.adjArray = (int *) malloc(2*E*sizeof(int));
271   _MEMCHECK(graph.adjArray);
272
273   for (i=0; i< V; i++) {
274     graph.vertexArray[i].degree = 0;
275     graph.vertexArray[i].next = i*C;
276     graph.vertexArray[i].adjListInd = i*C;
277   }
278 }
279
280
281 diameter()
282 {
283   Q * makeQueue();
284   int i,j, k, v, w, start;
285   int *distance;
286   int *histogram;
287   Q * q;
288   int dia;
289   float average;
290
291   distance = (int *)calloc(V, sizeof(int));
292   histogram = (int *)calloc(V, sizeof(int));
293
294   for (i=0; i<V; i++) {
295     histogram[i] = 0; 
296   }
297   
298   dia = 0;
299   average = 0.0;
300   q = makeQueue();
301   for (i=0; i<V; i++) {
302     /* run non-weighted shortes distance algorithm for each vertex i */
303     for (j=0; j<V; j++) distance[j] = -1;
304     distance[i] = 0;
305     enqueue(q, i);
306     while (! (isEmpty(q))) {
307       v = dequeue(q);
308       
309       start=graph.vertexArray[v].adjListInd;
310       for (k=0; k< graph.vertexArray[i].degree; k++) {
311         w = graph.adjArray[k+start];
312         if (distance[w] == -1) {
313           distance[w] = distance[v] + 1;
314           enqueue(q, w);
315         }
316       }
317     }
318     for (j=0; j<V; j++) {
319       if (distance[j] > dia) dia = distance[j];
320       average += distance[j];
321       histogram[ distance[j]]++;
322     }
323   }
324   average = average / (V*V);
325   printf("the diameter is: %d, average internode distance = %f\n", 
326          dia, average);
327   /*   for (i = 0; i< 6; i++) printf("histo[%d] = %d\n", i, histogram[i]);*/
328 }
329
330 /* ------------------------------------------------- */
331 /* The queue ADT */
332
333 Q * makeQueue()
334 {
335   Q *q = (Q *) malloc(sizeof(Q));
336   _MEMCHECK(q);
337   q->size = VMAX;
338   q->head = 1;
339   q->tail = 0;
340   q->buf = (int *) malloc(VMAX*sizeof(int));
341   _MEMCHECK(q->buf);
342   return q;
343 }
344
345 enqueue(Q * q, int i) {
346   q->tail++;
347   if (q->tail == q->size) q->tail = 0; /* no overflows possible */
348   q->buf[q->tail] = i;
349   q->numElements++;
350 }
351
352 int dequeue(Q *q) {
353   int r;
354   r = q->buf[q->head++];
355   if (q->head == q->size) q->head = 0;
356   q->numElements--;
357   return r;
358 }
359
360 isEmpty(Q * q) {
361   return (q->numElements == 0) ;
362 }