/* MakeSparse.c */

/* Creates a sparse 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 *dest;
  int *order;
  int newdest;
  int swapper, swapindex;
  int src;
  int done;
  int i, j, k;

  /* Seed the random number generator.  Will generate the same random */
  /*   numbers every time this program is run.                        */
  srandom(29);

  /* If there's no argument on the command line, instructions are printed. */
  if (argc < 2) {
    printf("MakeSparse n [c]\n");
    printf(
  "  Prints a random undirected graph on n vertices with Theta(n) edges.\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 = 0;

  /* Generate some neighbors for each vertex. */
  dest = (int *) malloc(6 * vertices * sizeof(int));
  for (i = 0; i < vertices; i++) {
    /* Generate one to six neighbors for vertex i. */
    for (j = 0; j < 1 + (int) (random() % 5l); j++) {
      newdest = (int) (random() % (long) vertices);
      dest[6 * i + j] = newdest;
      /* Eliminate duplicate edges. */
      for (k = 0; k < j; k++) {
        if (dest[6 * i + k] == newdest) {
          dest[6 * i + j] = -1;
        }
      }
      /* Eliminate symmetric duplicate edges. */
      if (newdest < i) {
        for (k = 0; k < 6; k++) {
          if (dest[6 * newdest + k] == i) {
            dest[6 * i + j] = -1;
          }
        }
      }
      /* If this edge has been generated for the first time, count it. */
      if (dest[6 * i + j] > -1) {
        edges++;
      }
    }
    /* The remaining neighbors of vertex i are unused. */
    for (; j < 6; j++) {
      dest[6 * i + j] = -1;
    }
  }

  /* Generate a random permutation of the edges.            */
  order = (int *) malloc(6 * vertices * sizeof(int));
  for (i = 0; i < 6 * vertices; i++) {
    order[i] = i;
  }
  for (i = 0; i < 6 * vertices; i++) {
    swapindex = i + (int) (random() % (long) (6 * vertices - i));
    swapper = order[swapindex];
    order[swapindex] = order[i];
    order[i] = swapper;
  }

  /* Print the edges in a random order, with random weights in [0, 99]. */
  printf("%d %d\n", vertices, edges);
  for (i = 0; i < 6 * vertices; i++) {
    if (dest[order[i]] > -1) {
      printf("%d %d  %d\n", order[i] / 6, dest[order[i]],
             (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++) {
      do {
        done = 1;
        src = (int) (random() % (long) vertices);
        j = (int) (random() % 6l);
        if (dest[6 * src + j] == -1) {
          /* Try to add a random edge to the graph. */
          newdest = (int) (random() % (long) vertices);
          /* Eliminate duplicate edges. */
          for (k = 0; k < 6; k++) {
            if ((k != j) && (dest[6 * src + k] == newdest)) {
              done = 0;
            }
          }
          /* Eliminate symmetric duplicate edges. */
          if (newdest != src) {
            for (k = 0; k < 6; k++) {
              if (dest[6 * newdest + k] == src) {
                done = 0;
              }
            }
          }
          if (done) {
            dest[6 * src + j] = newdest;
            printf("1  %d %d  %d\n", src, newdest, (int) (random() % 100l));
          }
        } else {
          /* Remove a random edge from the graph. */
          printf("0  %d %d\n", src, dest[6 * src + j]);
          dest[6 * src + j] = -1;
        }
      } while (!done);
    }
  }
}