/* MakeDense.c */

/* Creates a dense random undirected graph on n vertices. */

#include <stdio.h>
#include <stdlib.h>

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:  <source vertex> <destination vertex> <weight>\n");
    printf("    once:  <# of edge changes>\n");
    printf("    for each change:  0 <source vertex> <destination vertex>\n");
    printf(
  "                  or  1 <source vertex> <destination vertex> <weight>\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));
      }
    }
  }
}