//Brandon S. Parker
//April 18, 2003    
//generator.cc     
//=========================
//**************************************************************
//*               Graph Adj. Matrix Generator:                 *
//*                                                            *
//* Source file: generator.cc   Vers. 1.0                      *
//*                                                            *
//* Input: command line arguments 	                       *
//*                                                            *
//* Output: console and ASCII file                             *
//*                                                            *
//* Compile with: g++ -o generator generator.cc                *
//*                                                            *
//* Objective: Provide complete graphs for analysis            *
//*                                                            *
//* License: GPL - http://www.gnu.org/copyleft/gpl.html        *
//*                                                            *
//* For more information, see http://www.brandonparker.net     *
//*                                                            *
//* Author:                                                    *
//*  Brandon S. Parker                                         *
//*  (c) 2003 by Brandon S. Parker                             *
//*                                                            *
//**************************************************************

#include <iostream.h>
#include <stdio.h>
#include <fstream.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>


#define VERSION "1.0"
#define COPYRIGHT "(c)2003 Brandon Parker"

#define INFINITE 65535
#define MAXDIM 60000

//***Prototypes:
int CmdParse(int argv, char *argc[], char filename[], bool *QUIET, int *TYPE, int *MAX_W, int *n);
double getNOWTime();
double getCPUTime();

//************
//*** MAIN ***
//************

int main(int argv, char *argc[])
{

//*** Definitions:

srand((unsigned int)getCPUTime()); //*** seed randomize with currect time for uniqueness

char filename[88]; //*** Output filename
strcpy(filename, "AdjMatrix.mtx");

bool QUIET = false; //*** true = print to file, false = print to STDOUT only
int TYPE = 1; 	    //*** graph type: (1) Sparse, (2) Dense, (3) Mid/Random (4) Complete
int MAX_W = 60000; //*** Max weight allowed in the graph. Set to '1' for unweighted
int n = 25; //*** number of graph nodes/ matrix dimension
CmdParse(argv, argc, filename, &QUIET, &TYPE, &MAX_W, &n);
ofstream FILE(filename); //*** ASCII output file



if (!QUIET) FILE<<n<<endl;
cout<<endl<<"Size = "<<n<<endl;

unsigned int AdjMatrix[n][n]; //*** The Adjacency Matrix to be output
for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++)
		AdjMatrix[i][j] = 0;

//*** create a minimum edge connected graph (sparse)
//*** (See proof in footnote #1)
for (int i = 1; i < n; i++) 
       AdjMatrix[int(rand()%i)][i] = rand()%MAX_W + 1;

switch(TYPE)
	{ // *** Place at least one edge per node
	  // Note: above is the insurance of a connected graph... so the following cases are already connected:
	case 1: //Sparse where Edges << n(n-1)/2
		for(int i,j,k = 0; k <= (n); k++)
                        {
                        i = int(rand()%(n-1) + 1);
                        j = int(rand()%i);
                        AdjMatrix[j][i] = rand()%MAX_W + 1;
                        }

		break;
	case 2: // Dense  where Edges >> n(n-1)/2
		for(int i,j,k = 0; k <= (4 * n * n / 5); k++)
			{
			i = int(rand()%(n-1) + 1);
			j = int(rand()%i);
			AdjMatrix[j][i] = rand()%MAX_W + 1;
			}		
		break;
	case 3: // Mid/Random where Edges ~= n(n-1)/2
		for(int i,j,k = 0; k <= (n * n / 2); k++)
                        {
                        i = int(rand()%(n-1) + 1);
                        j = int(rand()%i);
                        AdjMatrix[j][i] = rand()%MAX_W + 1;
                        }
		break;
	case 4: // Complete where Edges = n
	default:
		 for (int i = 1; i < n; i++)
		    for (int j = 0; j < i; j++)
                        AdjMatrix[j][i] = rand()%MAX_W + 1;
	}

//*** Print it out.
for (int i = 0; i < n; i++)
	{
	for (int j = 0; j < n; j++)
		{
		if (!QUIET) FILE<<AdjMatrix[i][j]<<" ";
		}
	if (!QUIET) FILE<<endl;
	}
cout<<"Finished "<<filename<<"."<<endl;
FILE.close();
return 1;
}

//***************************************
//***		Sub-Routines	     * **
//***************************************



int CmdParse(int argv, char *argc[], char filename[], bool *QUIET, int *TYPE, int *MAX_W, int *n)
{
if (argv < 2)
	{
	cout<<endl<<"Usage: "<<argc[0]<<" <dimensions> [<filename>]"<<endl<<endl;
	exit(1);
	}
for (int i =  0; i < argv; i++)
	{
	if (argc[i][0] == '-')
		switch(argc[i][1])
		{
		  case 'f':
			if((argv > (i+1)) && (argc[i+1][0] != '-'))
				strcpy(filename, argc[i+1]);
			break;
		  case 'v': 
			cout<<endl<<argc[0]<<" Vers. "<<VERSION<<endl<<COPYRIGHT<<endl<<endl;
		  case 'q':
			*QUIET = true;
			break;
		  case 's':
			*TYPE = 1;
			break;
		  case 'd':
			*TYPE = 2;	
			break;
		  case 'r': 
			*TYPE = 3;
			break;
		  case 'c':
			*TYPE = 4;	
			break;
		  case 'w':
			*MAX_W = 1;
			break; 
		  case '?':
		  case 'h':
		  default:
			cout<<endl<<"Usage: "<<argc[0]<<" <dimensions> [-f <filename>] [-vhq]"<<endl;
			cout<<"Version: "<<VERSION<<" "<<COPYRIGHT<<endl<<endl;
			cout<<"  -c	Create a Complete graph."<<endl;
			cout<<"  -d	Create a Dense graph."<<endl;
			cout<<"  -f	Specify filename to write adjacency matrix to."<<endl;
			cout<<"  -h 	Display usage information."<<endl;
			cout<<"  -r	Create a random graph, (Sparse < graph < Dense)."<<endl;
			cout<<"  -s	Create a Sparse graph."<<endl;
			cout<<"  -q 	Print Adjacency Matrix to STDOUT only."<<endl;
			cout<<"  -w	Create an Unweighted graph."<<endl;
			cout<<"  -v 	Displays version information."<<endl;
			cout<<endl<<" Note: Maximum dimension for matrix is "<<MAXDIM<<"."<<endl; 
			cout<<" Output is a randomly generated, weighted (unless the -w flag is used)"<<endl;
			cout<<" adjacency matrix for a graph in ASCII format."<<endl<<endl;

		}
	else if ((i > 0) && (argc[i-1][1] != 'f'))
		 *n = atoi(argc[i]); 
	}
return 1;
}

//************************************************

double getCPUTime()
{
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_usec;
}

//************************************************

double getNOWTime() {
  struct timeval tv;
   gettimeofday(&tv, NULL);
   return tv.tv_sec*1e+06 + tv.tv_usec;
   }

//***************************************
//***              Foot-Notes         ***
//***************************************
//
// ----------------------------------------------------
// 1.) Proof of Connected minimum edge graph algorithm:
// ----------------------------------------------------
// Proof by induction:
// LET:
//	a.) G be a graph of n nodes
//	b.) M[n][n] be the Adjacency Matrix for G.
//	
// Note:
//	a.) For any i such that 0<i<n  M[i][i] is Infinity
//	b.) For any i,j such that 0<i,j<n  M[i][j] = M[j][i]
//		As such, any M[i][j>i] can be disregarded as the
//		contained value is a duplicate.
//
// Algorithm:
//	For each i = 1 to n
//	  choose a value of j such that 0<j<i
//	  Assign a connection and weight to M[i][j]	   
// Proof:
//
// (1) Let n = 2
//	The only edge possible is M[1][0], and a weight and connection
//	is placed at that location by the algorithm. Therefore, the
//	resulting graph is the minimum edge connected graph.
//
// (2) Let n = n + 1;
//	The new node must connect to one of the previous n nodes,
//	and therefore is connected to the rest of the graph maintaining
//	the minimum edge conneceted graph 
//     
// (3) Therefore, by induction, any G of size n will be a connected,
// 	minimum edge graph following the algorithm.
//