/*
    graphgen.cpp

    Program to generate graphs.
    Graph format:
      NumNodes
      Node:Node,Node,Node.
      Node:Node,Node,Node.
      Node:Node,Node,Node.
      ...

    Date: Feb 15, 2001

    Flags:
      -m M N  an M x N mesh
      -r N p  randomly generated graph

    A randomly generated graph has vertex 0
    connected to vertex 1, which is connected
    to vertex 2, ..., connected to vertex N-1.
    Then, for every other potential edge, it
    is in the set of edges with probability p.

*/

#include <stdlib.h>
#include <fstream.h>

/*
    RandomInt
    Returns an integer between a and b (inclusive) with
    equal probability.
*/
int RandomInt (int a, int b)
{
  // random number between 0 (inclusive) and 1 (exclusive)
  // multiply by (b - a + 1)
  // add a
  return ( a + static_cast<int>(
               ((double (rand()) / (double (RAND_MAX) + 1)) *
               (b - a + 1))) );
}

void OutputMeshGraph (ostream & os, int M, int N)
{
  bool first_edge;

  // output number of nodes
  os << M * N << endl;

  for (int i = 0; i < M; i++)
  {
    for (int j = 0; j < N; j++)
    {
      first_edge = true;

      os << i*N + j << ":";
      if (i >= 1)
      {
        os << (i-1)*N + j;
	first_edge = false;
      }
      if (j >= 1)
      {
	if (!first_edge)
	  os << ",";
        os << i*N + (j-1);
	first_edge = false;
      }
      if (j < N-1)
      {
	if (!first_edge)
	  os << ",";
        os << i*N + (j+1);
	first_edge = false;
      }
      if (i < M-1)
        os << "," << (i+1)*N + j;
      os << ".";
      os << endl;
    }
  }
}

void OutputRandomGraph (ostream & os, int N, double prob)
{
  bool first_edge;
  int i, j;
  int *adj;

  adj = new int [N * N];

  // initialize adjacency matrix
  for (i = 0; i < N; i++)
  {
    for (j = 0; j < N; j++)
    {
      adj[i*N + j] = 0;
    }
  }


  for (i = 0; i < N; i++)
  {
    if (i > 0)
      adj[i*N + i-1] = 1;
    if (i < N-1)
      adj[i*N + i+1] = 1;
    for (j = i+2; j < N; j++)
    {
      if (RandomInt(0, 9999) < 10000*prob)
      {
	adj[i*N + j] = 1;
	adj[j*N + i] = 1;
      }
    }
  }


  // output number of nodes
  os << N << endl;

  for (i = 0; i < N; i++)
  {
    os << i << ":";
    first_edge = true;

    for (j = 0; j < N; j++)
    {
      if (adj[i*N + j])
      {
        if (!first_edge)
          os << ",";
        os << j;
        first_edge = false;
      }
    }
    os << "." << endl;
  }

  delete [] adj;
}

void main(int argc, char * argv[])
{
    bool error = false;

    int meshM, meshN;
    int randomN;
    double randomProb;

    enum graph_type
    {
      NOGRAPH = 0,
      mesh = 1,
      random = 2
    } ;

    graph_type which_graph = NOGRAPH;

    ofstream outfile_stream;

    // Change the seed value to get different streams
    // of random numbers.
    srand (10);


    // Handle command line arguments.
    // Usage:  argv[0] -[mr] arg1 arg2 output_filename
    // Options:
    //   -m M N  an M x N mesh
    //   -r N p  a randomly generated graph with probability p

    if ((argc < 5) || (argc > 5))
    {
      cout << "Usage: " << argv[0] << " -[mr] arg1 arg2 outfile." << endl;
      error = true;
    }
    else
    {
      // figure out which option was chosen
      if (argv[1][0] == '-')
      {
        switch (argv[1][1])
        {
          case 'm':
            which_graph = mesh;
	    meshM = atoi(argv[2]);
	    meshN = atoi(argv[3]);
            break;

          case 'r':
            which_graph = random;
	    randomN = atoi(argv[2]);
	    randomProb = atof(argv[3]);
            break;

          default:
            cout << "Usage: ";
            cout << "-" << argv[1][1] << " is not a valid option." << endl;
	    error = true;
            break;
        }

	// Get the output filename
        outfile_stream.open(argv[4]);
        if (!outfile_stream)
        {
          cout << "Error: Could not open " << argv[4] << "." << endl;
	  error = true;
        }
      }
      else
      {
        cout << "Usage: " << argv[0] << " -[mr] arg1 arg2 filename." << endl;
	error = true;
      }
    }

    if (!error)
    {
      if (which_graph == mesh)
      {
	OutputMeshGraph (outfile_stream, meshM, meshN);
      }
      else if (which_graph == random)
      {
        OutputRandomGraph (outfile_stream, randomN, randomProb);
      }
      else
      {
        cout << "Error: Bad graph type." << endl;
      }
    }

    if (outfile_stream)
    {
      outfile_stream.close();
    }

    cout << argv[0] << " is done." << endl;
}