'''
Created on Oct 30, 2018
@authors: Brandon Toups
'''

import datetime
from multiprocessing import Pool
import sys

# Algorithm 1 EvoGraph
# Input G = (V, E) // original graph
#       k // scale factor
# 
# parallel for y in [|E|:k * |E| - 1] do
#     (vs,vt) <- DETERMINE(ey)
#     WRITE (vs , vt );
# ---------------------------------
# MEA - Memory-efficient edge attachment
# DETERMINE(ey) :
#     x ~ U(0, (k-1)*|E|-1)
#     direction ~ U(0,1)
# if x < |E|:
#     (vs,vt) = ex
# else:
#     DETERMINE(ex)
# 
# if direction = 0
#     (REFSF=k(vs),vt)
# else:
#     (vs,REFSF=k(vt))
# ----------------------------------
# Analysis:
# Following two hash functions where H(key) = ((key + 13) x 7)
# h1(y) determines the ID x of a parent edge ex of the edge ey
# Hash Function for U(0, (k-1)*|E|-1)
# h1 :key->[0,...,(k-1)*|E|-1]
#
# h2(y) determines a direction of the edge ey (direction 0 means towards 
# the inside of the graph, while direction 1 means towards the outside of graph.
# Hash Function for U(0,1)
# h2 : key -> [0,1]
# 
# ex: attaching e6 to GSF=2
#     H(6) = ((6+13) x 7) = 133
#     h1(6) = 133mod(2-1) * 6 = 1
#     h2(6) = 133mod2 = 1
# thus e1 = (v0,v2) is picked as a parent edge and e6 is determined as (v0,REFSF=2(v2)) = (v0,v7)
# 

# Program Code 
class EdgeInstance(object):
    currentGraph = {}
    currentNumEdges = 0
    currentNumNodes = 0
    initialNumEdges = 0
    initialNumNodes = 0
    y = 0
    x = 0
    direction = 0
    vs = 0
    vt = 0
    initialKVal = 0
    currentKVal = 2
    
# Algorithm 1 EvoGraph
# Input G = (V, E) // original graph
#       k          // scale factor
# 
# parallel for y in [|E|:k*|E|-1] do 
#     (vs,vt) <- DETERMINE(ey);
#     WRITE (vs , vt );
def evograph(fileToUpscale, kValToUpscaleTo):
    readGraph(fileToUpscale)

    EdgeInstance.initialKVal = kValToUpscaleTo
    EdgeInstance.initialNumNodes = EdgeInstance.initialNumEdges - 1
    rangeEdges = EdgeInstance.initialNumEdges
    maxNumEdges = EdgeInstance.initialKVal * rangeEdges
    for EdgeInstance.currentNumEdges in range(EdgeInstance.initialNumEdges, maxNumEdges):
        readGraph(fileToUpscale)
        vsvt = DETERMINE(EdgeInstance.currentNumEdges)
        WRITE(vsvt, EdgeInstance.currentNumEdges, fileToUpscale)
        
def upscaleGraph(fileToUpscale):
    
    print '\n\nUsing single-threading, we will be running various upscaling tests on sf=1.txt.'
    print 'These include upscaling to k=2,k=3,k=4 using one thread.'
    
    print 'Original graph (Gsf=1) is: ' # print out original fileToUpscale
    with open(fileToUpscale, 'r') as fin:
        print fin.read()
    print '----------------------------------------\n'
    
    
    # Upscale to k=2
    print 'Upscaling sf=1.txt graph from k=1 to k=2: '
    evograph(fileToUpscale, 2)
    print 'The graph generated by this process below: '
    outputGraph(fileToUpscale)
    returnSF1ToOriginal()
    print 'Compare the above upscale to the expected values in k=2 graph (../data/sf=2.txt) printed below:'
    print '(Tabs in this fileToUpscale used to more easily delineate between the new edges inserted at this level)'
    with open('../data/sf=2.txt', 'r') as fin:
        print fin.read()
    print '----------------------------------------\n'

    # Upscale to k=3
    print 'Upscaling sf=1.txt graph from k=1 to k=3: '
    evograph(fileToUpscale, 3)
    print 'The graph generated by this process below: '
    outputGraph(fileToUpscale)
    returnSF1ToOriginal()
    print 'Compare the above upscale to the expected values in k=3 graph (../data/sf=3.txt) printed below:'
    print '(Tabs in this fileToUpscale used to more easily delineate between the new edges inserted at this level)'
    with open('../data/sf=3.txt', 'r') as fin:
        print fin.read()
    print '----------------------------------------\n'


    # Upscale to k=4
    print 'Upscaling sf=1.txt graph from k=1 to k=4: '
    evograph(fileToUpscale, 4)
    print 'The graph generated by this process below: '
    outputGraph(fileToUpscale)
    returnSF1ToOriginal()
    print 'Compare the above upscale to the expected values in k=4 graph (../data/sf=4.txt) printed below:'
    print '(Tabs in this fileToUpscale used to more easily delineate between the new edges inserted at this level)'
    with open('../data/sf=4.txt', 'r') as fin:
        print fin.read()
    print '----------------------------------------\n'

    
    # Upscale to k=128
    print 'Upscaling sf=1.txt graph from k=1 to k=128: '
    start = datetime.datetime.now()
    evograph(fileToUpscale, 128)
    finish = datetime.datetime.now()
    print 'The graph generated by this process is not being printed to terminal, as it is too large '
    
    timeToExec = finish - start
    print 'The time to execute an upscale to k=128 is ' + str(timeToExec) + ' seconds'
    
    print 'The program has finished so you can view the 128x upscale in sf=1.txt'
    print 'This is not the original state of the file, and will be reset to the original'
    print 'state on the next execution'
    
        
def WRITE(refvsvt, y, fileToWriteTo):
    with open(fileToWriteTo,'a') as openFile:
        openFile.write( str(refvsvt[0]) + '\t' + str(refvsvt[1])  + '\t#e' + str(y) + '\n')

# DETERMINE(ey) :
#     x ~ U(0, (k-1)*|E|-1)
#     direction ~ U(0,1)
# if x < |E|:
#     (vs,vt) = ex
# else:
#     DETERMINE(ex)
# 
# if direction = 0
#     (REFSF=k(vs),vt)
# else:
#     (vs,REFSF=k(vt))
def DETERMINE(y):
    # next k value if multiple of initial number of edges
    if EdgeInstance.currentNumEdges == EdgeInstance.initialNumEdges*EdgeInstance.currentKVal:
        EdgeInstance.currentKVal+=1
        
    if (EdgeInstance.currentKVal != int(y/EdgeInstance.initialNumEdges) + 1):
        EdgeInstance.currentKVal = int(y/EdgeInstance.initialNumEdges) + 1
    # x ~ U(0, (k-1)*|E|-1)
    EdgeInstance.x = h1(y)
    
    # if x < |E|:
    if EdgeInstance.x < EdgeInstance.initialNumEdges:
        # (vs,vt) = ex        
        EdgeInstance.vs = EdgeInstance.currentGraph['e' + str(EdgeInstance.x)][0]
        EdgeInstance.vt = EdgeInstance.currentGraph['e' + str(EdgeInstance.x)][1]
    else:
        # (vs,vt) = DETERMINE(ex)    
        vsvt = DETERMINE(EdgeInstance.x)
        if (EdgeInstance.currentKVal != int(y / EdgeInstance.initialNumEdges) + 1):
            EdgeInstance.currentKVal = int(y / EdgeInstance.initialNumEdges) + 1
            
        EdgeInstance.vs = vsvt[0]
        EdgeInstance.vt = vsvt[1]
    # if direction == 0
    # direction ~ U(0,1)
    if h2(y) == 0:
        # (REFSF=k(vs), vt)
        refvsvt = [ int(REFSF(1)), int(EdgeInstance.vt) ]
    else:
        # (vs,REFSF=k(vt))        
        refvsvt = [ int(EdgeInstance.vs) , int(REFSF(2)) ]
        
    return refvsvt
    
def readGraph(inputFile):
    with open(inputFile) as f:
        edges = {}
        lines = f.readlines()
        edgeNum = 0
        for line in lines:
            vs = line.split()[0]
            vt = line.split()[1]
            edges['e' + str(edgeNum)] = (vs,vt)
            edgeNum+=1
    if EdgeInstance.currentNumEdges == 0:
        EdgeInstance.initialNumEdges = edgeNum
    EdgeInstance.currentGraph = edges
    EdgeInstance.currentNumEdges = edgeNum
    
# H(key) = ((key + 13) x 7)
# h1(y) determines the ID x of a parent edge ex of the edge ey
# Hash Function for U(0, (k-1)*|E|-1)

# h1 :key->[0,...,(k-1)*|E|-1] 
def h1(key):
    
    return H(key) % ((EdgeInstance.currentKVal-1) * (EdgeInstance.initialNumEdges))
        
# h2(y) determines a direction of the edge ey (direction 0 means towards 
# the inside of the graph, while direction 1 means towards the outside of graph.
# Hash Function for U(0,1)
# h2 : key -> [0,1]
def h2(key):
    return H(key) % 2

def H(key):
    return ((key + 13) * 7)

def REFSF(whichIndex):
    refIs = 0
    nodesOnLevel = EdgeInstance.initialNumNodes
    if whichIndex == 2:
        refIs = int(EdgeInstance.vt)
        return refIs + int(nodesOnLevel* (EdgeInstance.currentKVal-1))
    else:
        refIs = int(EdgeInstance.vs)
        return refIs + int(nodesOnLevel* (EdgeInstance.currentKVal-1))
    return refIs

def outputGraph(fileToUpscale):
    with open(fileToUpscale, 'r') as fin:
        print (fin.read())

def returnSF1ToOriginal():
    # opens original fileToUpscale
    file1 = open("../data/sf=1Original.txt" , "r")
    # opens new fileToUpscale
    file2 = open("../data/sf=1.txt" , "w")
    #for each line in old fileToUpscale
    for line in file1:
        #write that line to the new fileToUpscale
        file2.write(line)
    #close fileToUpscale 1
    file1.close()
    #close file2
    file2.close()
    
def outputOriginalSF1():
    # print out original fileToUpscale 
    print ('Original graph (Gsf=1) is: ')
    with open('../data/sf=1Original.txt', 'r') as fin:
        print (fin.read())
    print ('----------------------------------------\n')


if __name__ == '__main__':
    print ('Running evograph.py\n')
    print 'After every single execution, for repeatability, the file that was upscaled '
    print 'will be returned to its original state automatically. This is due to the nature'
    print 'of the memory-efficient edge attachment, wherein the edges are read from the '
    print 'graph, and subsequently, new edges being attached are added directly back into that file'
    
    # make sure that sf=1.txt is a clean, original before running
    returnSF1ToOriginal()
    #returnToyToOriginal()

    fileToUpscale = '../data/sf=1.txt'
    # upscale actions taken on sf=1.txt.
    upscaleGraph(fileToUpscale)    
    
    print 'Done'
       