import java.io.*;
import java.util.Random;

/**
 * <p>Title: GenGraph for Assignment 5</p>
 * <p>Description: Generates a description of a random graph in a text file</p>
 * <p>Copyright: Copyright (c) 2003</p>
 * <p>Company: </p>
 * @author Andrew Rau-Chaplin
 * @version 1.0
 */

public class GenerateGraph {

   private static int graph[][]; // matrix representation of graph
   private static int n; // number of vertices
   private static int m; // number of edges
   private static int seed; //Random seed used to create graph

   /**
    * Writes the current graph to a binary file where the first int is the
    * random seed used to create the graph, the second int is the number of
    * vertices and the third int is the number of edges. The remaining its
    * represent the graph in row major order.
    * @param filename
    * @throws IOException
    */
   private static void writeGraphToFile(String filename) throws IOException {
      DataOutputStream outfile = new DataOutputStream(new FileOutputStream(
          filename));

      outfile.writeInt(seed);
      outfile.writeInt(n);
      outfile.writeInt(m);
      for (int r = 0; r < n; r++) {
         for (int c = 0; c < n; c++)
             outfile.writeInt(graph[r][c]);
      }
      outfile.close();
   }


   /**
    * Read a graph from a binary file.
    * @param filename
    * @throws IOException
    */
   private static void readGraphFromFile(String filename) throws IOException {
      DataInputStream   infile = new DataInputStream(new FileInputStream(filename));

      seed = infile.readInt();
      n = infile.readInt();
      m = infile.readInt();

      graph = new int[n][n];
      for (int r = 0; r < n; r++) {
         for (int c = 0; c < n; c++)
            graph[r][c] = infile.readInt();
      }
      infile.close();
   }

   private static String formatInt(int i, int length) {
      String result = "" + i;
      while (result.length() < length)
            result = " " + result;
      return result;
   }

   private static String blanks(int length) {
   String result = "";
   for (int i = 0; i < length; i++)
      result += " ";
   return result;
}

   // Retrns number of digits in x
   private static int digitCount(int x) {
      int d = 0;
      while (x != 0) {
         d++;
         x = x / 10;
      }
      return d;
   }

   /**
    * Display the current graph
    */
   private static void displayGraph() {
      int d = digitCount(n);

      // Print header
      System.out.println("Random graph: Seed = " + seed +
                       " Vertices = " + n + " Edges = " + m);
      System.out.print(blanks(d + 1));
      for (int c = 0; c< n;c++)
         System.out.print(formatInt(c,d+1));
      System.out.println();
      System.out.println();

      //Display graph
      for (int r = 0; r < n; r++){
         System.out.print(formatInt(r,d) + "  ");
         for (int c = 0; c < n; c++)
            if (c>r)
               System.out.print(formatInt(graph[r][c],d) + " ");
            else
               System.out.print(blanks(d + 1));
         System.out.println();
      }
   }

   /**
    * Generates a random graph and stores it in a binary file
    * @param nodes Number of vertices
    * @param edges Number of edges
    * @param filename File for output
    * @param seed Random Seed
    */
   private static void generateRandomGraph(int nodes, int edges, String filename,
                                          int randomSeed) {
      Random generator = new Random(seed);
      int p, q, temp;

      n = nodes;
      m = edges;
      seed = randomSeed;
      graph = new int[nodes][nodes];

      // Create m edges
      for (int e = 0; e < m; e++) {
         // Find a pair of vertices that don't have an edge between them
         do {
            p = generator.nextInt(n);
            q = generator.nextInt(n);
            //swap p and q if p > q
            if (p>q){
               temp = p;
               p = q;
               q = temp;
            }
         } while ((p == q) || (graph[p][q] != 0));

         // create and edge between p and q
         graph[p][q] = 1;
      }
   }

private static int maxEdges(int v){
      return (((v * v) - v) /2);
   }

   private static void generateRandomGraph(String filename, int seed)  throws IOException {
      int n; // Number of vertices
      int m; // Number of edges
      int maxEdges; //Max number of edges in undirected graph with n vertices
      BufferedReader inputStream = new BufferedReader(
          new InputStreamReader(System.in));

      // Prompt user for n and m. Can have at most n * n edges.
      do {
         System.out.print("Required number of vertices?: ");
         n = Integer.valueOf(inputStream.readLine().trim()).intValue();
         maxEdges = ((n * n) - n) /2;
         System.out.print("Required number of edges? (0.." + maxEdges+"): ");
         m = Integer.valueOf(inputStream.readLine().trim()).intValue();
         if (m > maxEdges) {
            System.out.println("Max number of edges is " + maxEdges);
         }
      }
      while (m > maxEdges);

      //Generate a random graph
      generateRandomGraph(n, m, filename, seed);

   }

   public static void main(String[] args) throws IOException {

      int selection;
      String filename;
      int seed;
      BufferedReader inputStream = new BufferedReader(new InputStreamReader(System.in));

      do {
         // Prompt user for selection
         do {
            System.out.println();
            System.out.println("1: Create new random graph file.");
            System.out.println("2: Open and display a random graph file.");
            System.out.println("3:Exit.");
            System.out.print("Selection?: ");
            selection = Integer.valueOf(inputStream.readLine().trim()).intValue();
            if ( (selection < 1) || (selection > 3)) {
               System.out.println("Not a valid selection.");
            }
         }

         while ( (selection < 1) || (selection > 3));

         if (selection == 1) {
            System.out.print("Name of output file?: ");
            filename = inputStream.readLine();

            System.out.print("Integer Seed: ");
            seed = Integer.valueOf(inputStream.readLine().trim()).intValue();

            //Generate a random graph
            generateRandomGraph(filename,seed);

            //Write random graph to file
            writeGraphToFile(filename);

            graph = null;
         }
         else if (selection == 2) {
            System.out.print("Name of input file?: ");
            filename = inputStream.readLine();
            readGraphFromFile(filename);
            displayGraph();
         }
         else {
            System.out.println("Done.");

         }
      }
      while (selection != 3);
   }
}