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