'''
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 parallel(fileToUpscale, kValToUpscaleTo, processes):
    readGraph(fileToUpscale)

    EdgeInstance.initialKVal = kValToUpscaleTo
    EdgeInstance.initialNumNodes = EdgeInstance.initialNumEdges - 1
    rangeEdges = EdgeInstance.initialNumEdges
    maxNumEdges = EdgeInstance.initialKVal * rangeEdges
        
    # parallelized for-loop using multiprocessing functionality
    if processes != -1:
        p = Pool(processes=processes)
    # allow OS to assign number of processes
    else:
        p = Pool()
    
    iterRange = list(range(EdgeInstance.initialNumEdges, maxNumEdges))

    # if we are upscaling sf=1.txt 
    if fileToUpscale == '../data/sf=1.txt':
        start = datetime.datetime.now()
        p.map(EvoGraphSF1, iterRange)
        finish = datetime.datetime.now()
        iterationTime = (finish - start)
        print str(processes) + ' thread(s)\t' + 'Execution time: ' + str(iterationTime) 
        p.close()
    
    elif fileToUpscale == '../data/toy.txt':
        start = datetime.datetime.now()
        p.map(EvoGraphToy, iterRange)
        finish = datetime.datetime.now()
        iterationTime = (finish - start)
        print str(processes) + ' thread(s)\t' + 'Execution time: ' + str(iterationTime) 
        p.close()
        
    return iterationTime

def EvoGraphSF1(currentNumEdges):
    readGraph('../data/sf=1.txt')
    vsvt = DETERMINE(currentNumEdges)
    WRITE(vsvt, currentNumEdges, '../data/sf=1.txt')

def EvoGraphToy(currentNumEdges):
    readGraph('../data/toy.txt')
    vsvt = DETERMINE(currentNumEdges)
    WRITE(vsvt, currentNumEdges, '../data/toy.txt')
        
def upscaleGraph():
    
    print '\n\nUsing multiprocessing, we will be running various upscaling tests on sf=1.txt.'
    print ('These include upscaling to k=2,k=3,k=4 using multiple threads.' 
           + ' You will notice that many of these are out \nof order when printing out. However,'
           + ' all of the values are correct. Since EvoGraph is using I/O for \nfinding new edges, any'
           + ' of the threads can read and write the edges at any time. \nThis means that, due to the possibility'
           + ' of deep recursion, some of the threads reading later edges will be \nwritten into sf=1.txt' 
           + ' before the earlier writes are finished'
           + ' \n\n')
    
    print 'Original graph (Gsf=1) is: ' # print out original fileToUpscale
    with open('../data/sf=1.txt', 'r') as fin:
        print fin.read()
    print '----------------------------------------\n'
    
    # Upscale to k=2
    print 'Upscaling sf=1.txt graph from k=1 to k=2: '
    parallel('../data/sf=1.txt', 2, 3)
    print 'The graph generated by this process below: '
    outputGraph('../data/sf=1.txt')
    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: '
    parallel('../data/sf=1.txt', 3, 3)
    print 'The graph generated by this process below: '
    outputGraph('../data/sf=1.txt')
    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: '
    parallel('../data/sf=1.txt', 4, 12)
    print 'The graph generated by this process below: '
    outputGraph('../data/sf=1.txt')
    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'
    
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)
    nodesOnLevel = EdgeInstance.initialNumNodes
    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 returnToyToOriginal():
    #print 'For repeatability, the fileToUpscale toy is now being returned to its original state'
    # opens original fileToUpscale
    file1 = open("../data/toyOriginal.txt" , "r")
    # opens new fileToUpscale
    file2 = open("../data/toy.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')

def outputOriginalToy():
    # print out original fileToUpscale 
    print ('Original graph (Gsf=1) is: ')
    with open('../data/toyOriginal.txt', 'r') as fin:
        print (fin.read())
    print ('----------------------------------------\n')  
    
def runtime(fileToUpscale, kValue, numberOfThreads, numIterations):
    print 'Running parallel upscale on ' + fileToUpscale + ' to test time complexity of a ' + str(kValue) + 'x upscale.'

    k2TimeTotal = 0
    numExecutions = numIterations 
    iterationTime = 0
    for iteration in range(0,numExecutions):
        iterationTime += (parallel(fileToUpscale, kValue, numberOfThreads)).total_seconds()     
    
    print 'Total execution time:   ' + str(iterationTime) + ' seconds for ' + str(iteration + 1) + ' iteration(s)'
    print 'Average execution time: ' + str(iterationTime / (iteration+1) )
    print ''
    
def timingSF1():
    
    print '----------------------------------------'
    print 'Now running timing tests on k=2 upscale'
    print '----------------------------------------\n\n'
    
    fileToUpscale = '../data/sf=1.txt'
    # Below lines for testing execution time 
    numberOfThreads = 1
    kValue = 2
    numIterations = 5
    # k=2 ; threads=1 ; iterations=5
    runtime(fileToUpscale, kValue, numberOfThreads, numIterations)
    
    # k=2 ; threads=2 ; iterations=5
    runtime(fileToUpscale, kValue, 2,  numIterations)
    
    # k=2 ; threads=4 ; iterations=5
    runtime(fileToUpscale, kValue, 4,  numIterations)
    
    # k=2 ; threads=8 ; iterations=5
    runtime(fileToUpscale, kValue, 8,  numIterations)
    
    # k=2 ; threads=16; iterations=5
    #runtime(fileToUpscale, kValue, 16, numIterations)
    
    # k=2 ; threads=32; iterations=5
    #runtime(fileToUpscale, kValue, 32, numIterations)
    
    # k=2 ; threads=64; iterations=5
    #runtime(fileToUpscale, kValue, 64, numIterations)
    
    # k=2 ; threads=100; iterations=5
    runtime(fileToUpscale, kValue, 100, numIterations)
    
    # k=2 ; threads=110; iterations=5
    #runtime(fileToUpscale, kValue, 110, numIterations)
    
    # k=2 ; threads=128; iterations=5
    #runtime(fileToUpscale, kValue, 128, numIterations)
    
    # k=2 ; threads=150; iterations=5
    #runtime(fileToUpscale, kValue, 150, numIterations)
    
    # k=2 ; threads=200; iterations=5
    #runtime(fileToUpscale, kValue, 200, numIterations)
    
    # k=2 ; threads=250; iterations=5
    #runtime(fileToUpscale, kValue, 250, numIterations)
    
    # k=2 ; threads=300; iterations=5
    #runtime(fileToUpscale, kValue, 300, numIterations)
    
    # k=2 ; threads=400; iterations=5
    #runtime(fileToUpscale, kValue, 400, numIterations)

    
    print '----------------------------------------'
    print 'Now running timing tests on k=3 upscale'
    print '----------------------------------------\n\n'
    fileToUpscale = '../data/sf=1.txt'
    # Below lines for testing execution time 
    numberOfThreads = 1
    kValue = 3
    numIterations = 5
    # k=3 ; threads=1 ; iterations=5
    runtime(fileToUpscale, kValue, numberOfThreads, numIterations)
    
    # k=3 ; threads=2 ; iterations=5
    runtime(fileToUpscale, kValue, 2,  numIterations)
    
    # k=3 ; threads=4 ; iterations=5
    runtime(fileToUpscale, kValue, 4,  numIterations)
    
    # k=3 ; threads=8 ; iterations=5
    runtime(fileToUpscale, kValue, 8,  numIterations)
    
    # k=3 ; threads=16; iterations=5
    #runtime(fileToUpscale, kValue, 16, numIterations)
    
    # k=3 ; threads=32; iterations=5
    #runtime(fileToUpscale, kValue, 32, numIterations)
    
    # k=3 ; threads=64; iterations=5
    #runtime(fileToUpscale, kValue, 64, numIterations)
    
    # k=3 ; threads=100; iterations=5
    runtime(fileToUpscale, kValue, 100, numIterations)
    
    # k=3 ; threads=110; iterations=5
    #runtime(fileToUpscale, kValue, 110, numIterations)
    
    # k=3 ; threads=128; iterations=5
    #runtime(fileToUpscale, kValue, 128, numIterations)
    
    # k=3 ; threads=150; iterations=5
    #runtime(fileToUpscale, kValue, 150, numIterations)
    
    # k=3 ; threads=200; iterations=5
    #runtime(fileToUpscale, kValue, 200, numIterations)
    
    # k=3 ; threads=250; iterations=5
    #runtime(fileToUpscale, kValue, 250, numIterations)
    
    # k=3 ; threads=300; iterations=5
    #runtime(fileToUpscale, kValue, 300, numIterations)
    
    # k=3 ; threads=400; iterations=5
    #runtime(fileToUpscale, kValue, 400, numIterations)
    
    
    print '----------------------------------------'
    print 'Now running timing tests on k=128 upscale'
    print '----------------------------------------\n\n'
    fileToUpscale = '../data/sf=1.txt'
    # Below lines for testing execution time 
    numberOfThreads = 1
    kValue = 128
    numIterations = 5
    # k=128 ; threads=1 ; iterations=5
    runtime(fileToUpscale, kValue, numberOfThreads, numIterations)
    
    # k=128 ; threads=2 ; iterations=5
    runtime(fileToUpscale, kValue, 2,  numIterations)
    
    # k=128 ; threads=4 ; iterations=5
    runtime(fileToUpscale, kValue, 4,  numIterations)
    
    # k=128 ; threads=8 ; iterations=5
    runtime(fileToUpscale, kValue, 8,  numIterations)
    
    # k=128 ; threads=16; iterations=5
    #runtime(fileToUpscale, kValue, 16, numIterations)
    
    # k=128 ; threads=32; iterations=5
    #runtime(fileToUpscale, kValue, 32, numIterations)
    
    # k=128 ; threads=64; iterations=5
    #runtime(fileToUpscale, kValue, 64, numIterations)
    
    # k=128 ; threads=100; iterations=5
    runtime(fileToUpscale, kValue, 100, numIterations)
    
    # k=128 ; threads=110; iterations=5
    #runtime(fileToUpscale, kValue, 110, numIterations)
    
    # k=128 ; threads=128; iterations=5
    #runtime(fileToUpscale, kValue, 128, numIterations)
    
    # k=128 ; threads=150; iterations=5
    #runtime(fileToUpscale, kValue, 150, numIterations)
    
    # k=128 ; threads=200; iterations=5
    #runtime(fileToUpscale, kValue, 200, numIterations)
    
    # k=128 ; threads=250; iterations=5
    #runtime(fileToUpscale, kValue, 250, numIterations)
    
    # k=128 ; threads=300; iterations=5
    #runtime(fileToUpscale, kValue, 300, numIterations)
    
    # k=128 ; threads=400; iterations=5
    #runtime(fileToUpscale, kValue, 400, numIterations)
    
    
def timingToy():
    print '----------------------------------------'
    print 'Now running timing tests on k=2 upscale'
    print '----------------------------------------\n\n'
    
    fileToUpscale = '../data/toy.txt'
    # Below lines for testing execution time 
    #numberOfThreads = 1
    kValue = 2
    numIterations = 1
    # k=2 ; threads=1 ; iterations=5
    #runtime(fileToUpscale, kValue, numberOfThreads, numIterations)
    
    # k=2 ; threads=2 ; iterations=5
    #runtime(fileToUpscale, kValue, 2,  numIterations)
    
    # k=2 ; threads=8 ; iterations=5
    #runtime(fileToUpscale, kValue, 8,  numIterations)
    
    # k=2 ; threads=100; iterations=5
    runtime(fileToUpscale, kValue, 100, numIterations)
    
    # k=2 ; threads=110; iterations=5
    #runtime(fileToUpscale, kValue, 110, numIterations)
    
    # k=2 ; threads=200; iterations=5
    #runtime(fileToUpscale, kValue, 200, numIterations)
    
    # k=2 ; threads=250; iterations=5
    #runtime(fileToUpscale, kValue, 250, numIterations)
    
    # k=2 ; threads=300; iterations=5
    #runtime(fileToUpscale, kValue, 300, numIterations)
    
    # k=2 ; threads=400; iterations=5
    #runtime(fileToUpscale, kValue, 400, numIterations)

    # this is going to take long
    # k=2 ; threads=400; iterations=1
#    runtime(fileToUpscale, kValue, 1000, 1)
    
    
    print '----------------------------------------'
    print 'Now running timing tests on k=3 upscale'
    print '----------------------------------------\n\n'
    fileToUpscale = '../data/toy.txt'
    # Below lines for testing execution time 
    numberOfThreads = 1
    kValue = 3
    numIterations = 1
    # k=3 ; threads=1 ; iterations=5
    #runtime(fileToUpscale, kValue, numberOfThreads, numIterations)
    
    # k=3 ; threads=2 ; iterations=5
    #runtime(fileToUpscale, kValue, 2,  numIterations)
    
    # k=3 ; threads=8 ; iterations=5
    #runtime(fileToUpscale, kValue, 8,  numIterations)
    
    # k=3 ; threads=100; iterations=5
    runtime(fileToUpscale, kValue, 100, numIterations)
    
    # k=3 ; threads=100; iterations=5
    #runtime(fileToUpscale, kValue, 110, numIterations)
    
    # k=3 ; threads=200; iterations=5
    #runtime(fileToUpscale, kValue, 200, numIterations)
    
    # k=3 ; threads=250; iterations=5
    #runtime(fileToUpscale, kValue, 250, numIterations)
    
    # k=3 ; threads=300; iterations=5
    #runtime(fileToUpscale, kValue, 300, numIterations)
    
    # k=3 ; threads=400; iterations=3
    #runtime(fileToUpscale, kValue, 400, 3)

    # this is going to take long
    # k=3 ; threads=400; iterations=1
    #runtime(fileToUpscale, kValue, 1000, 1)


    
def upscaleToy128x():
    print '----------------------------------------'
    print 'Now running timing tests on k=128 upscale'
    print '----------------------------------------\n\n'
    fileToUpscale = '../data/toy.txt'
    # Below lines for testing execution time 
    numberOfThreads = 1
    kValue = 128
    numIterations = 5
    # k=128 ; threads=1 ; iterations=3
    runtime(fileToUpscale, kValue, numberOfThreads, numIterations)
    
    # k=128 ; threads=2 ; iterations=3
    runtime(fileToUpscale, kValue, 2, 5)
    
    # k=128 ; threads=10 ; iterations=3
    optimalNumThreads = 0
    runtime(fileToUpscale, kValue, optimalNumThreads, 5)
    
    
if __name__ == '__main__':
    print ('Running evograph.py\n')
    print 'After every single execution, for repeatability, the fileToUpscale 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 fileToUpscale'
    
    # make sure that sf=1.txt is a clean, original before running
    returnSF1ToOriginal()
    returnToyToOriginal()

    # Various upscale actions taken on sf=1.txt.
    upscaleGraph()    
    
    
    print '\n\nNow running timing experiments on various datasets'
    
    # running timing experiments on ../data/sf=1.txt
    timingSF1()
    
    # running timing experiments on ../data/toy.txt
    timingToy()
    
    # this is going to take the longest, reserving for only one execution
    #upscaleToy128x()
    
    print 'Finished.'
       