#------------------------------------------------------------------------------
#  RandomInput2.py 
#  Creates a random pair of matched input-output files for CSE 30 pa6. The 
#  output file contains an optimum proper coloring of the graph represented
#  by the input file.
#------------------------------------------------------------------------------
import random

# main-------------------------------------------------------------------------
def main():

   # get user input and initialize local variables
   file1 = input("Enter name of input file to create: " )
   file2 = input("Enter name of output file to create: ")
   n = int( input("Enter number of vertices n (must be positive): " ) )
   chi = int( input(f"Enter the chromatic number chi (1<=chi<={n}): " ) )
   f1 = open(file1, 'w')
   f2 = open(file2, 'w')

   # pre-color all vertices {1, 2, .., n}
   color = dict()
   for u in range(1, chi+1):
      color[u] = u
   # end
   for u in range(chi+1, n+1):
      color[u] = random.randint(1, chi)
   # end

   # create complete graph on chi vertices
   edges = []
   for u in range(1, chi):
      for v in range(u+1, chi+1):
         edges.append((u,v))
      # end
   # end

   # add random edges without increasing chromatic number
   for u in range(1, n):
      for v in range(max(u+1, chi+1), n+1):
         if color[u]!=color[v] and (random.randint(0,1)==1):
            edges.append((u,v))
         # end
      # end
   # end

   # randomize vertex labels
   P = list(range(1, n+1))
   random.shuffle(P)
   E = []
   C = dict()
   for (u,v) in edges:
      e = [P[u-1], P[v-1]]
      e.sort()
      E.append( tuple(e) )
   # end
   E.sort()
   for u in range(1, n+1):
      C[P[u-1]] = color[u]
   # end

   # write data to file1
   f1.write(str(n)+'\n')
   for (u, v) in E:
      f1.write(f'{u} {v}\n')   
   # end

   # write data to file2
   f2.write(f'{chi} colors used: {set(range(1,chi+1))}\n\n')
   f2.write('vertex    color\n')
   f2.write('----------------\n')
   for u in range(1,n+1):
      f2.write(' {0:<10}{1:<10}\n'.format(u, C[u]))
   # end

   # close files
   f1.close()
   f2.close()

# end--------------------------------------------------------------------------


#------------------------------------------------------------------------------
if __name__=='__main__':

   main()

# end