/* MakeDense.c */ /* Creates a dense random undirected graph on n vertices. */ #include #include int main(int argc, char **args) { int vertices; int edges; int changes; int *order; int swapper, swapindex; int i, j; /* Seed the random number generator. Will generate the same random */ /* numbers every time this program is run. */ srandom(12); /* If there's no argument on the command line, instructions are printed. */ if (argc < 2) { printf("MakeDense n [c]\n"); printf( " Prints a random undirected graph on n vertices with Theta(n^2) edges\n"); printf(" Not every pair of vertices is connected, however.\n"); printf(" If c is specified, c edge changes will be printed.\n\n"); printf(" Format: <# of vertices> <# of edges>\n"); printf( " for each edge: \n"); printf(" once: <# of edge changes>\n"); printf(" for each change: 0 \n"); printf( " or 1 \n\n"); printf(" A prefix of 0 specifies an edge deleted from the graph.\n"); printf(" A prefix of 1 specifies an edge added to the graph.\n"); exit(0); } /* Read the number of vertices. */ sscanf(args[1], "%d", &vertices); edges = vertices * (vertices + 1) / 2; /* Generate a random permutation of the edges. */ order = (int *) malloc(edges * sizeof(int)); for (i = 0; i < vertices; i++) { for (j = 0; j <= i; j++) { if ((random() & 1l) == 0l) { /* Write the edge as (i, j). */ order[(i * (i + 1) / 2) + j] = i * vertices + j; } else { /* Write the edge as (j, i). */ order[(i * (i + 1) / 2) + j] = j * vertices + i; } } } for (i = 0; i < edges; i++) { swapindex = i + (int) (random() % (long) (edges - i)); swapper = order[swapindex]; order[swapindex] = order[i]; order[i] = swapper; } /* Print the edges (with a few missing) in a random order, */ /* with random weights in [0, 99]. */ if (edges >= 3) { edges = edges - (int) (random() % (long) (edges / 3)); } printf("%d %d\n", vertices, edges); for (i = 0; i < edges; i++) { printf("%d %d %d\n", order[i] / vertices, order[i] % vertices, (int) (random() % 100l)); } if (argc < 3) { printf("0\n"); } else { /* Read the number of changes. */ sscanf(args[2], "%d", &changes); printf("%d\n", changes); for (i = 0; i < changes; i++) { if ((((random() & 1l) == 0l) && (edges > 0)) || (edges == vertices * (vertices + 1) / 2)) { /* Remove a random edge from the graph. */ swapindex = random() % (long) edges; edges--; swapper = order[swapindex]; order[swapindex] = order[edges]; order[edges] = swapper; printf("0 %d %d\n", swapper / vertices, swapper % vertices); } else { /* Add a random edge to the graph. */ swapindex = edges + random() % (long) ((vertices * (vertices + 1) / 2) - edges); swapper = order[swapindex]; order[swapindex] = order[edges]; order[edges] = swapper; edges++; printf("1 %d %d %d\n", swapper / vertices, swapper % vertices, (int) (random() % 100l)); } } } }