changes made by Yogesh: when generating dense graph, the algorithm was not capable...
authorGengbin Zheng <gzheng@illinois.edu>
Fri, 14 Nov 2003 08:14:40 +0000 (08:14 +0000)
committerGengbin Zheng <gzheng@illinois.edu>
Fri, 14 Nov 2003 08:14:40 +0000 (08:14 +0000)
Fixed by allowing it to back off when error happens and applied special edge in the last step to break self connections.

src/conv-ldb/edgelist.c
src/conv-ldb/generate.c

index 392b100f3e3fb450c666dc0208dabe1b0839e31f..1fd9ba4442846ffa856be2bd0f5e2f9259330564 100644 (file)
@@ -65,3 +65,50 @@ int edgeExists(x,y)
   
   return 0;
 }
+
+/*
+  If we are adding an edge between two nodes already connected then we 
+  need special changes. We open some distinct edge say x,y and 
+  connect v with y and x with w
+*/
+
+void addspEdge(EdgeList, v,w)
+     EdgeListType * EdgeList;
+     int v;
+     int w;
+{ int n, index,i,x,y,ind;
+  n = EdgeList->next;
+  EdgeList->next++;
+
+  /* printf("adding edge: (%d, %d)\n", v, w); */
+  //((EdgeList->edges)[n]).node1 = v;
+  //(EdgeList->edges[n]).node2 = w;
+   for (i=0;i<n-1;i++)
+     if (((EdgeList->edges[i]).node1!=v) && ((EdgeList->edges[i]).node2!=w)) 
+       {
+           x=(EdgeList->edges[i]).node1;
+           y=(EdgeList->edges[i]).node2;       
+            (EdgeList->edges[i]).node2=w;
+            (EdgeList->edges[n]).node1=v;
+           (EdgeList->edges[n]).node2=y;       
+
+            
+            ind =  graph.vertexArray[x].adjListInd;
+           for(i=0; i< graph.vertexArray[x].degree; i++)
+                   { if (graph.adjArray[ind + i] == y) graph.adjArray[ind+i]=w;}
+
+            ind =  graph.vertexArray[y].adjListInd;
+           for(i=0; i< graph.vertexArray[y].degree; i++)
+                   { if (graph.adjArray[ind + i] == x) graph.adjArray[ind+i]=y;}
+       
+            index =  graph.vertexArray[v].next++;
+           graph.adjArray[ index ] = y;
+           index =  graph.vertexArray[w].next++;
+           graph.adjArray[ index ] = x;
+           graph.vertexArray[v].degree++;
+           graph.vertexArray[w].degree++;
+            break;
+        
+       }
+}
+
index 63a335bccb93e46eea23f47668022792995edae8..ba6031ecae72bd37c394141287eb477c3523a2d6 100644 (file)
@@ -8,6 +8,7 @@
 /* Generate a random graph, given the number of nodes, the number of
    connections per node.
 
+dump graph if "tofile" is true
 Output form: directory graphN/ containing files graph0 ... graphN-1
              file graphK has C, the number of connections, followed by
              a list of C vertices that K is connected to
@@ -22,6 +23,7 @@ Modified from the original: changed output format, and converted main to a param
 #include "typedefs.h"
 
 int addEdge(EdgeListType *l,int fm,int to);
+void addspEdge(EdgeListType *, int, int);
 int edgeExists(int fm, int to);
 static Q * makeQueue();
 static int isEmpty(Q*);
@@ -89,7 +91,7 @@ void gengraph(int pV, int pC, int pseed, int *pes, int *npe, int tofile)
   if (CmiMyPe()==0) diameter();
 }
 
-
+#if 0
 static void AddEdges(EdgeListType *EdgeList, int V, int n)
    /* Add more edges to make up a total of E edges */
 {int i,j,w,x,y;
@@ -122,6 +124,45 @@ n -= (V-1);
      addEdge(EdgeList, x, y);
    }
 }
+#endif
+
+static void AddEdges(EdgeListType *EdgeList, int V, int n)
+   /* Add more edges to make up a total of E edges */
+{int i,j,w,x,y;
+/* first add edges for a C-way spanning tree.*/
+int c1;
+int varr[V];
+if (C>1) c1 = C-1;
+
+for (i=0; i< V/c1; i++)
+  for (j=0; j<c1; j++) {
+      w = c1*i + j +1; 
+      /* printf("considering (%d, %d)\n", i, w);  */
+      if (w < V) {
+       addEdge(EdgeList,i,w);
+       /* printf(" --- added.\n"); */
+      }
+      else /*printf(" not added.\n")*/; 
+  }
+
+n -= (V-1);
+
+for (i=0; i<n; i++) 
+   {
+     do {
+          x = rand() % V;
+        } while (connections(x) >= C);
+     do {
+          y = rand() % V;
+        } while ((y == x) || connections(y) >= C);
+     if (edgeExists(x,y)) {
+          if (i==n-1) addspEdge(EdgeList,x,y);
+          else i--;
+     }
+     else  
+       addEdge(EdgeList, x, y);
+   }
+}
 
 void fillAdjArray(Edge *edges, VerticesListType *vlist, int V, int E);
 void sortAdjArrays(VerticesListType *vlist);