Click here to download p6/gengraph.cpp.

/* SI 335 Spring 2012
 * Project 6
 * This is a program to generate test cases for the "drive"
 * shortest-paths finder program. It takes in n and m and
 * writes a randomly-generated graph to the named output file.
 */

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

// Returns a random integer between 0 and n-1.
int randomInt(int n);

// Prints an error message and exits ungracefully
void error (const char* msg);

int main (int argc, char** argv) {
  srand(time(NULL));

  // Check command-line arguments
  if (argc != 4) {
    cerr << "Usage: " << argv[0] << " <n> <m> <output_file>" << endl;
    error ("Wrong number of arguments");
  }

  int n, m;
  n = atoi(argv[1]);
  m = atoi(argv[2]);

  if (n <= 0 || m <= 0) error ("n and m must be positive");
  if (n > 10000) error ("n is too large");
  if (m > n*(n-1)/2) error ("m is too large");

  ofstream graph (argv[3]);
  if (!graph) error("Bad output filename");

  // Read in city names, then put into random order.
  ifstream citynames ("cities.txt");
  if (!citynames) error("Could not find file cities.txt");

  vector<string> cities(n);
  for (int i=0; i<n; ++i)
    citynames >> cities[i];

  citynames.close();

  random_shuffle(cities.begin(), cities.end());

  // Print n, m to graph file
  graph << n << ' ' << m << endl;

  // Print city names to graph file
  for (int i=0; i<n; ++i)
    graph << cities[i] << endl;

  // Make a matrix to store whether we've already put
  // an edge between two vertices.
  bool** edges = new bool*[n];
  edges[0] = new bool[n*n];
  for (int i=1; i<n; ++i)
    edges[i] = edges[i-1]+n;
  
  if (m <= n*(n-1)/4) {
    // Graph is (mostly) sparse. So start with empty graph and
    // generate random edges.
    for (int i=0; i<n; ++i) {
      for (int j=0; j<n; ++j)
        edges[i][j] = false;
      edges[i][i] = true;
    }

    int i=0;
    // Start by generating a random tree, so the graph will be connected.
    for (; i<n-1 && i<m; ++i) {
      int u = i+1;
      int v;
      do { v = randomInt(u); } while (edges[u][v]);
      graph << cities[u] << ' ' << cities[v] << ' ';
      graph << randomInt(400) << ' ' << randomInt(400) << endl;
      edges[u][v] = edges[v][u] = true;
    }

    // Now just generate random edges
    for (; i<m; ++i) {
      int u,v;
      do {
        u = randomInt(n);
        v = randomInt(n);
      } while (edges[u][v]);
      graph << cities[u] << ' ' << cities[v] << ' ';
      graph << randomInt(400) << ' ' << randomInt(400) << endl;
      edges[u][v] = edges[v][u] = true;
    }
  }
  else {
    // Graph is (mostly) dense. So start with a complete graph and randomly
    // remove edges.
    for (int i=0; i<n; ++i) {
      for (int j=0; j<n; ++j)
        edges[i][j] = true;
      edges[i][i] = false;
    }

    for (int i=m; i<n*(n-1)/2; ++i) {
      int u,v;
      do {
        u = randomInt(n);
        v = randomInt(n);
      } while (!edges[u][v]);
      edges[u][v] = edges[v][u] = false;
    }

    for (int i=0; i<n; ++i) {
      for (int j=i+1; j<n; ++j) {
        if (edges[i][j]) {
          graph << cities[i] << ' ' << cities[j] << ' ';
          graph << randomInt(400) << ' ' << randomInt(400) << endl;
        }
      }
    }
  }

  graph.close();
  delete [] edges[0];
  delete [] edges;

  return 0;
}

// Returns a random integer between 0 and n-1.
int randomInt(int n) {
  int r, max = RAND_MAX - ((RAND_MAX-n+1) % n);
  do { r = rand(); }
  while (r > max);
  return (r % n);
}

// Prints an error message and exits ungracefully
void error (const char* msg) {
  cerr << "ERROR:" << endl << msg << endl;
  exit(1);
}