src/conv-ldb/generate.c

   1 /* Generate a random graph, given the number of nodes, the number of
   2    connections per node.
   3
   4 dump graph if "tofile" is true
   5 Output form: directory graphN/ containing files graph0 ... graphN-1
   6              file graphK has C, the number of connections, followed by
   7              a list of C vertices that K is connected to
   8
   9 Modified from the original: changed output format, and converted main to a parametered function
  10 */
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13
  14 /* comment this out to test and change CmiPrintf to printf */
  15 #include "converse.h"
  16 #include "graphdefs.h"
  17
  18 int addEdge(VerticesListType *graph, EdgeListType *l,int fm,int to);
  19 void addspEdge(VerticesListType *graph, EdgeListType *, int, int);
  20 int edgeExists(VerticesListType *graph, int fm, int to);
  21 static Q * makeQueue();
  22 static int isEmpty(Q*);
  23 static int dequeue(Q*);
  24
  25 #define VMAX 2050
  26 int V; /* no. of vertices */
  27 int E; /* no. of edges */
  28 int C; /* no. of connections per vertex */
  29
  30 VerticesListType * InitVertices();
  31
  32
  33 /* For testing...
  34 main(int argc, char **argv)
  35 {
  36   gengraph(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]));
  37 }
  38 */
  39
  40 static void printOut(VerticesListType *vertices);
  41 static void copyOut(VerticesListType *vertices, int *npe, int *pes);
  42 static void initGraph(VerticesListType *graph);
  43 static void diameter(VerticesListType *graph);
  44 static void AddEdges(VerticesListType *graph, EdgeListType *EdgeList, int V, int n);
  45
  46 void gengraph(int pV, int pC, int pseed, int *pes, int *npe, int tofile)
  47 { int i;
  48   VerticesListType graph;
  49   int seed;
  50   EdgeListType * EdgeList;
  51   /* VerticesListType * vertices; */
  52   extern EdgeListType * InitEdgeList();
  53   char dircmd[20], dirname[10];
  54
  55   V = pV;
  56   C = pC;
  57   seed = pseed;
  58
  59   if (CmiMyPe() == 0)
  60   CmiPrintf("for %d PEs, connectivity %d... \n", V, C);
  61
  62   /* make a directory */
  63   if (tofile && CmiMyPe() == 0) {
  64   sprintf(dirname, "graph%d", V);
  65   sprintf(dircmd, "mkdir %s", dirname);
  66   system(dircmd);
  67   }
  68
  69   /* for (i=0; i<seed; i++) rand(); */
  70   for (i=0; i<seed; i++) CrnRand();
  71   if ((V*C %2) != 0) printf("V*C must be even\n");
  72   E = V*C/2;
  73   initGraph(&graph);
  74   EdgeList = InitEdgeList(E);
  75   AddEdges(&graph, EdgeList, V, E);
  76   /*  vertices = (VerticesListType *) InitVertices(EdgeList, V,E); */
  77
  78   if (tofile) {
  79     if (CmiMyPe()==0) printOut(&graph);
  80   }
  81   else copyOut(&graph, npe, pes);
  82
  83   if (CmiMyPe()==0) diameter(&graph);
  84 }
  85
  86 #if 0
  87 static void AddEdges(EdgeListType *EdgeList, int V, int n)
  88    /* Add more edges to make up a total of E edges */
  89 {int i,j,w,x,y;
  90 /* first add edges for a C-way spanning tree.*/
  91 int c1;
  92 if (C>1) c1 = C-1;
  93
  94 for (i=0; i< V/c1; i++)
  95   for (j=0; j<c1; j++) {
  96       w = c1*i + j +1;
  97       /* printf("considering (%d, %d)\n", i, w);  */
  98       if (w < V) {
  99         addEdge(EdgeList,i,w);
 100         /* printf(" --- added.\n"); */
 101       }
 102       else /*printf(" not added.\n")*/;
 103   }
 104 n -= (V-1);
 105
 106  for (i=0; i<n; i++)
 107    {
 108      do {
 109        do {
 110          x = CrnRand() % V;
 111        } while (connections(x) >= C);
 112        do {
 113          y = CrnRand() % V;
 114        } while ((y== x) || connections(y) >= C);
 115      } while (edgeExists(x,y));
 116      addEdge(EdgeList, x, y);
 117    }
 118 }
 119 #endif
 120
 121 static void AddEdges(VerticesListType *graph, EdgeListType *EdgeList, int V, int n)
 122         /* Add more edges to make up a total of E edges */
 123   {     int i,j,w,x,y,k;
 124         int c1,max,maxi;
 125         int **varr;
 126         int varrlen,count=0;
 127         int flag=0;
 128
 129         /* first add edges for a C-way spanning tree.*/
 130         varr=(int **)calloc(V, sizeof(int*));
 131         for (i=0;i<V;i++)
 132             varr[i]=calloc(2, sizeof(int));
 133
 134   c1 = 1;
 135         if (C>1) c1 = C-1;
 136
 137         for (i=0; i<= V/c1; i++)
 138           for (j=0; j<c1; j++) {
 139               w = c1*i + j +1;
 140               if (w < V) {
 141                 addEdge(graph, EdgeList,i,w);
 142                 count++;
 143                               }
 144                   }
 145
 146         /*varr is array of vertices and free connection for each vertex*/
 147         j=0;
 148         for (i=0;i<V;i++)
 149                 if(connections(graph, i)<C)
 150                 {
 151                  varr[j][0]=i;
 152                  varr[j][1]=C-connections(graph,i);
 153                  j++;
 154                 }
 155         varrlen=j;
 156         CmiAssert(varrlen>0);
 157
 158         /*for all edges except last 10 , edge is formed by randomly selecting vertices from varr*/
 159
 160         n -= count;
 161
 162         /*if (n>10)
 163         for (j=0; j<n-10; j++)
 164            {
 165                 flag=0;
 166                 do {
 167                      x = rand() % varrlen;
 168                      do {
 169                              y = rand() % varrlen;
 170                         } while (y == x) ;
 171                 }while (edgeExists(varr[x][0],varr[y][0]));
 172              addEdge(EdgeList, varr[x][0], varr[y][0]);
 173
 174              varr[x][1]=varr[x][1]-1;
 175              varr[y][1]=varr[y][1]-1;
 176
 177              //If no free connections left for a vertex remove it from varr
 178
 179              if (varr[x][1]==0) {
 180                                  flag=1;
 181                                  for (i=x;i<varrlen-1;i++)
 182                                         {
 183                                          varr[i][0]=varr[i+1][0];
 184                                          varr[i][1]=varr[i+1][1];
 185                                         }
 186                                  varrlen--;
 187                                 }
 188              if ((y>x)&&(flag)) {
 189
 190                                         if (varr[y-1][1]==0)
 191                                                         {
 192                                                           for (i=y-1;i<varrlen-1;i++)
 193                                                                 {
 194                                                                  varr[i][0]=varr[i+1][0];
 195                                                                  varr[i][1]=varr[i+1][1];
 196                                                                 }
 197                                                           varrlen--;
 198                                                         }
 199                                 }
 200              else if (varr[y][1]==0) {
 201                                  for (i=y;i<varrlen-1;i++)
 202                                         {
 203                                          varr[i][0]=varr[i+1][0];
 204                                          varr[i][1]=varr[i+1][1];
 205                                         }
 206                                  varrlen--;
 207                                 }
 208            }
 209
 210         //for last 10 edges, first vertex is one with max free connections and other vertex is randomly chosen
 211
 212         if (n>10) k=10; else k = n;*/
 213
 214         k=n;
 215         for (j=0;j<k;j++)
 216                 {
 217                                 flag=0;
 218                                 max=0;
 219                                 maxi=0;
 220                                 for (i=0;i<varrlen;i++)
 221                                         if (varr[i][1]>max) { max=varr[i][1];maxi=i;}
 222                                 x = maxi;
 223                                 do {
 224                                      y = rand() % varrlen;
 225                                    } while (y == x) ;
 226
 227                                 /*if (edgeExists(varr[x][0],varr[y][0]))
 228                                         if (j==k-1) addspEdge(EdgeList,varr[x][0],varr[y][0]);
 229                                         else do {
 230                                                         y = rand() % varrlen;
 231                                                  } while (y == x);
 232                                 else addEdge(EdgeList,varr[x][0],varr[y][0]); */
 233
 234                                 if (edgeExists(graph, varr[x][0],varr[y][0])&&(j==k-1))
 235                                         addspEdge(graph, EdgeList,varr[x][0],varr[y][0]);
 236                                 else
 237                                 {
 238                                         while((y==x)||(edgeExists(graph,varr[x][0],varr[y][0])))
 239                                                 y = rand() % varrlen;
 240                                         addEdge(graph,EdgeList,varr[x][0],varr[y][0]);
 241                                 }
 242
 243                                 varr[x][1]=varr[x][1]-1;
 244                                 varr[y][1]=varr[y][1]-1;
 245
 246                                 if (varr[x][1]==0)
 247                                         {
 248                                          flag=1;
 249                                          for (i=x;i<varrlen-1;i++)
 250                                                 {
 251                                                  varr[i][0]=varr[i+1][0];
 252                                                  varr[i][1]=varr[i+1][1];
 253                                                 }
 254                                          varrlen--;
 255                                         }
 256                                 if ((y>x)&&(flag))
 257                                         {
 258                                          if (varr[y-1][1]==0)
 259                                                         {
 260                                                           for (i=y-1;i<varrlen-1;i++)
 261                                                                 {
 262                                                                  varr[i][0]=varr[i+1][0];
 263                                                                  varr[i][1]=varr[i+1][1];
 264                                                                 }
 265                                                           varrlen--;
 266                                                         }
 267                                         }
 268                                 else if (varr[y][1]==0)
 269                                         {
 270                                                  for (i=y;i<varrlen-1;i++)
 271                                                         {
 272                                                          varr[i][0]=varr[i+1][0];
 273                                                          varr[i][1]=varr[i+1][1];
 274                                                         }
 275                                                  varrlen--;
 276                                         }
 277                         }
 278         for (i=0;i<V;i++) free(varr[i]);
 279         free(varr);
 280 }
 281
 282
 283 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E);
 284 void sortAdjArrays(VerticesListType *vlist);
 285 static void sort(int *adj, int fromIndex, int toIndex);
 286 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E);
 287
 288 VerticesListType *
 289 InitVertices(EdgeList, V,E)
 290      EdgeListType * EdgeList;
 291      int V;
 292      int E;
 293 { /* returns a structure of type VerticesListType, which contains an arry of
 294      vertex records, and an array of adjacency information. See typedef. */
 295   /* First allocate the adjacency subarray of size E, and vertex subarray size V.
 296      Then count the occurences of each vertex in the Edgelist in vertex.degree.
 297      Then compute the real adjListInd = sum from 0 to i-1 of the previous degrees.
 298      Then, traverse edge list, and enter each edge in two adj lists.
 299      Then sort individual adj-lists, separately. */
 300   VerticesListType * vlist;
 301
 302   vlist = (VerticesListType *) malloc(sizeof(VerticesListType));
 303   _MEMCHECK(vlist);
 304   vlist->numVertices = V;
 305   vlist->vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
 306   _MEMCHECK(vlist->vertexArray);
 307   vlist->adjArray = (int *) malloc(2*E*sizeof(int));
 308                     /* as each edge is entered twice */
 309   _MEMCHECK(vlist->adjArray);
 310   countDegrees(EdgeList->edges, vlist->vertexArray, V, E);
 311   fillAdjArray(EdgeList->edges, vlist, V, E);
 312   sortAdjArrays(vlist);
 313   return(vlist);
 314 }
 315
 316 void countDegrees(Edge *edges, Vertex *vertRecs, int V, int E)
 317 { /* initialize the degrees of all vertices to 0.
 318      Traverse the edge list, incrementing the degree of the 2 nodes for each edge.
 319      */
 320  int i, count;
 321
 322  for (i=0; i<V; i++)
 323    { vertRecs[i].degree = 0;
 324      vertRecs[i].next = 0;}
 325  for (i=0; i<E; i++)
 326    {vertRecs[ edges[i].node1 ].degree++;
 327     vertRecs[ edges[i].node2 ].degree++;}
 328
 329 /* now fill adjListInd, by starting a counter at 0, and adding degrees of visited
 330    nodes. */
 331  count = 0;
 332  for (i=0; i<V; i++)
 333    { vertRecs[i].adjListInd = count;
 334      count += vertRecs[i].degree;
 335    }
 336 }
 337
 338 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E)
 339 { /* Insert each edge <x,y> as an entry y in x's adj list, and vice versa. */
 340   int i, x,y;
 341  int * adj;
 342  Vertex * vertexRecs;
 343
 344  adj = vlist->adjArray;
 345  vertexRecs = vlist->vertexArray;
 346
 347   for (i=0; i<E; i++)
 348     { x = edges[i].node1; y = edges[i].node2;
 349       adj[ vertexRecs[x].adjListInd + vertexRecs[x].next ] = y;
 350       vertexRecs[x].next++;
 351       adj[ vertexRecs[y].adjListInd + vertexRecs[y].next ] = x;
 352       vertexRecs[y].next++;
 353     }
 354 }
 355
 356 void sortAdjArrays(VerticesListType *vlist)
 357 { /* sort each section of the array corresponding to each vertex. */
 358   int V, i;
 359   int dupcount;
 360
 361   V = vlist->numVertices;
 362   for (i=0; i<V; i++)
 363     { sort(vlist->adjArray,
 364            vlist->vertexArray[i].adjListInd,
 365            vlist->vertexArray[i].adjListInd + vlist->vertexArray[i].degree -1);
 366     }
 367   /* eliminate duplicates. May be should be merged with above? */
 368   dupcount = 0;
 369   for (i=0; i<V; i++)
 370     { int m,n, limit;
 371       int * adj;
 372
 373       m = vlist->vertexArray[i].adjListInd;
 374       n = m+1;
 375       limit = m + vlist->vertexArray[i].degree; /* this is the first index
 376                                                    not belonging to this vertex.*/
 377       adj = vlist->adjArray;
 378       /* do this in 2 phases. First phase: m and n are exactly one away.
 379          goes on until the first duplicate is found. In this phase, there
 380          is no need to assign values (no shifting is going on.) */
 381       while ((adj[m] != adj[n]) && (n < limit)) {m++; n++;}
 382       /* Phase 2: */
 383       while (n<limit) {
 384         while ((adj[m] == adj[n]) && (n<limit))
 385           { n++; dupcount++; vlist->vertexArray[i].degree--;}
 386         adj[m+1] = adj[n]; /*move the non duplicate back to its new position*/
 387         m++; n++;
 388       }
 389     }
 390 /* printf("number of duplicate edges removed = %d\n", dupcount/2);*/
 391 /* Here is an assignment to a global variable.... */
 392 if ((dupcount % 2) != 0) {printf("error. duplicates not even.\n"); }
 393 E -= dupcount/2;
 394 }
 395
 396 static void sort(int *adj, int fromIndex, int toIndex)
 397 { int i,j, tmp;
 398   short changed;
 399   changed = 1;
 400   for (i=toIndex; ((i>fromIndex) && changed); i--)
 401     { changed = 0;
 402       for (j=fromIndex; j<i; j++)
 403         { if (adj[j] > adj[j+1])
 404             { /* swap */
 405               changed = 1;
 406               tmp = adj[j];
 407               adj[j] = adj[j+1];
 408               adj[j+1] = tmp;
 409             }
 410         }
 411     }
 412 }
 413
 414 static void copyOut(VerticesListType *vertices, int *npe, int *pes)
 415 {
 416  int i;
 417  int * adj;
 418  Vertex * vertexRecs;
 419
 420  adj = vertices->adjArray;
 421  vertexRecs = vertices->vertexArray;
 422
 423 #if CMK_NODE_QUEUE_AVAILABLE
 424  *npe = vertexRecs[CmiMyNode()].degree;
 425  for (i=0; i<vertexRecs[CmiMyNode()].degree; i++)
 426        pes[i] = adj[ vertexRecs[CmiMyNode()].adjListInd + i ];
 427 #else
 428  *npe = vertexRecs[CmiMyPe()].degree;
 429  for (i=0; i<vertexRecs[CmiMyPe()].degree; i++)
 430        pes[i] = adj[ vertexRecs[CmiMyPe()].adjListInd + i ];
 431 #endif
 432 }
 433
 434 static void printOut(VerticesListType *vertices)
 435 {int i,j;
 436  int * adj;
 437  Vertex * vertexRecs;
 438  FILE *fp;
 439  char filename[20];
 440
 441  adj = vertices->adjArray;
 442  vertexRecs = vertices->vertexArray;
 443
 444  for (i=0; i<vertices->numVertices; i++)
 445    {
 446      /* Open graphN/graphi */
 447      sprintf(filename, "graph%d/graph%d", vertices->numVertices, i);
 448      fp = fopen(filename, "w");
 449      fprintf(fp, "%d ", vertexRecs[i].degree);
 450      for (j=0; j<vertexRecs[i].degree; j++)
 451        fprintf(fp, "%d ", adj[ vertexRecs[i].adjListInd + j ]);
 452      fprintf(fp, "\n");
 453      fclose(fp);
 454    }
 455 }
 456
 457 static void initGraph(VerticesListType *graph)
 458 { int i;
 459   graph->numVertices = V;
 460   graph->vertexArray = (Vertex *) malloc(V*sizeof(Vertex));
 461   _MEMCHECK(graph->vertexArray);
 462   graph->adjArray = (int *) malloc(2*E*sizeof(int));
 463   _MEMCHECK(graph->adjArray);
 464
 465   for (i=0; i< V; i++) {
 466     graph->vertexArray[i].degree = 0;
 467     graph->vertexArray[i].next = i*C;
 468     graph->vertexArray[i].adjListInd = i*C;
 469   }
 470 }
 471
 472 static void enqueue(Q *q, int i);
 473
 474 static void diameter(VerticesListType *graph)
 475 {
 476   Q * makeQueue();
 477   int i,j, k, v, w, start;
 478   int *distance;
 479   int *histogram;
 480   Q * q;
 481   int dia;
 482   float average;
 483
 484   distance = (int *)calloc(V, sizeof(int));
 485   histogram = (int *)calloc(V, sizeof(int));
 486
 487   for (i=0; i<V; i++) {
 488     histogram[i] = 0;
 489   }
 490
 491   dia = 0;
 492   average = 0.0;
 493   q = makeQueue();
 494   for (i=0; i<V; i++) {
 495     /* run non-weighted shortes distance algorithm for each vertex i */
 496     for (j=0; j<V; j++) distance[j] = -1;
 497     distance[i] = 0;
 498     enqueue(q, i);
 499     while (! (isEmpty(q))) {
 500       v = dequeue(q);
 501
 502       start=graph->vertexArray[v].adjListInd;
 503       for (k=0; k< graph->vertexArray[i].degree; k++) {
 504         w = graph->adjArray[k+start];
 505         if (distance[w] == -1) {
 506           distance[w] = distance[v] + 1;
 507           enqueue(q, w);
 508         }
 509       }
 510     }
 511     for (j=0; j<V; j++) {
 512       if (distance[j] > dia) dia = distance[j];
 513       average += distance[j];
 514       histogram[ distance[j]]++;
 515     }
 516   }
 517   average = average / (V*V);
 518   printf("the diameter is: %d, average internode distance = %f\n",
 519          dia, average);
 520   /*for (i = 0; i< 6; i++) printf("histo[%d] = %d\n", i, histogram[i]);*/
 521   free(distance);
 522   free(histogram);
 523 }
 524
 525 /* ------------------------------------------------- */
 526 /* The queue ADT */
 527
 528 static Q * makeQueue()
 529 {
 530   Q *q = (Q *) malloc(sizeof(Q));
 531   _MEMCHECK(q);
 532   q->size = VMAX;
 533   q->numElements = 0;
 534   q->head = 1;
 535   q->tail = 0;
 536   q->buf = (int *) malloc(VMAX*sizeof(int));
 537   _MEMCHECK(q->buf);
 538   return q;
 539 }
 540
 541 static void enqueue(Q * q, int i) {
 542   q->tail++;
 543   if (q->tail == q->size) q->tail = 0; /* no overflows possible */
 544   q->buf[q->tail] = i;
 545   q->numElements++;
 546 }
 547
 548 static int dequeue(Q *q) {
 549   int r;
 550   r = q->buf[q->head++];
 551   if (q->head == q->size) q->head = 0;
 552   q->numElements--;
 553   return r;
 554 }
 555
 556 static int isEmpty(Q * q) {
 557   return (q->numElements == 0) ;
 558 }