WaterFilling.py

import csv
import numpy
import networkx as nx
import matplotlib.pyplot as plt
import copy
import time

M_vector=numpy.array([1000,2000,3000,4000,5000])
tran_max=1000
water_filling_packet=5

#Importing the set of edges
bi_edges=numpy.loadtxt("ripple_graph.txt",dtype=int)
bi_edges=numpy.unique(bi_edges,axis=0)

#Making a graph from the given set of edges
wei=numpy.ones(len(bi_edges)) #initializing the weights of the edges
bi_G = nx.DiGraph() #Initializing the directed graph
for i in range(0,len(bi_edges)):
    bi_G.add_weighted_edges_from([(bi_edges[i,0], bi_edges[i,1],wei[i])]) #adding edges to the graph and assigning weights

#Importing Transactions
with open('transactions.csv') as csvDataFile:
    tran=csv.reader(csvDataFile)
    tran=list(tran) #converting the imported data into a list
    tran=numpy.array(tran) #converting the list into numpy array
tran=numpy.ndarray.astype(tran,float)
k=0
for i in range(0,len(tran)):
    if tran[i,2]>tran_max:
        tran=numpy.delete(tran,obj=i,axis=0) #removing all the transactions that are greater than tran_max
    k=k+1
    if len(tran)<k:
        break

def minwp_heu(G,s,d,tran,K): 
    X=nx.shortest_simple_paths(G,s,d,'imbalance') 
    #returns a generator which returns one path at a time from shortest to longest
    weight2=100000 #initialize by a very large number
    for j, path in enumerate(X): #enumerate shortest to longest paths 
        weight1=0 #initialize by 0 to calculate the weight of path
        for k in range(0,len(path)-1):
            weight1=weight1+G[path[k]][path[k+1]]['weight']-G[path[k+1]][path[k]]['weight'] 
            #calculating the actual weight of path p
        if min(weight1,weight2)==weight1 and weight1!=weight2: #comparing with the best weight obtained so far
            min_wei_path=path #picking the minimum weight path
            weight2=weight1 #updating the best weight obtained so for
        if j == K-1: #break after looking at K shortest paths according to the imbalance
            break
    var=1
    for l in range(0,len(min_wei_path)-1):
        s=min(G[min_wei_path[l]][min_wei_path[l+1]]['weight'],G[min_wei_path[l+1]][min_wei_path[l]]['weight'],M)
        if G[min_wei_path[l]][min_wei_path[l+1]]['weight']+tran-s>M: 
            #Checking if a has enough capacity to route tran
            var=0
    if var!=0:
        return min_wei_path #We will either get a path from s to d or 0 if min_wei_path cannot route tran
    else:
        return 0

def AddWeights(G,path,tran,d):
    for i in range(0,len(path)-1):
        if path[i]!=d:
            G[path[i]][path[i+1]]['weight']=G[path[i]][path[i+1]]['weight']+tran
            bi_G[path[i]][path[i+1]]['imbalance']=max(bi_G[path[i]][path[i+1]]['weight']
                -bi_G[path[i+1]][path[i]]['weight'],0)
            bi_G[path[i+1]][path[i]]['imbalance']=max(bi_G[path[i+1]][path[i]]['weight']
                -bi_G[path[i]][path[i+1]]['weight'],0) 
    return G

def Balancing(G,path,d):
    for i in range(0,len(path)-1):
        if path[i]!=d:
            s=min(G[path[i]][path[i+1]]['weight'],G[path[i+1]][path[i]]['weight'],M) #calculating the amount of service
            G[path[i]][path[i+1]]['weight']=G[path[i]][path[i+1]]['weight']-s
            G[path[i+1]][path[i]]['weight']=G[path[i+1]][path[i]]['weight']-s
            bi_G[path[i]][path[i+1]]['imbalance']=max(bi_G[path[i]][path[i+1]]['weight']
                -bi_G[path[i+1]][path[i]]['weight'],0)
            bi_G[path[i+1]][path[i]]['imbalance']=max(bi_G[path[i+1]][path[i]]['weight']
                -bi_G[path[i]][path[i+1]]['weight'],0) 
    return G

for argument in range(1,len(sys.argv)):
    M=M_vector[int(sys.argv[argument])]
    no_of_succ_tran=0
    amount_of_succ_tran=0
    total_buffer=0
    min_wei_path=0
    for k in range(0,len(bi_edges)):
        bi_G[bi_edges[k,0]][bi_edges[k,1]]['weight']=0 #initializing the weights
        bi_G[bi_edges[k,0]][bi_edges[k,1]]['imbalance']=0 #initializing the imbalance
    for i in range(0,len(tran)):
        path_list=[] #to consolidate all the paths chosen to route a transaction
        min_wei_path=0
        var=1
        transaction=tran[i,2]/water_filling_packet #dividing the transaction into water_filling_packet number of packets
        for j in range(0,water_filling_packet):
            min_wei_path=minwp_heu(bi_G,tran[i,0],tran[i,1],transaction,1) 
            #finding the minimum weighted path from sender to reciever
            if min_wei_path!=0: #If a path exists
                bi_G=AddWeights(bi_G,min_wei_path,transaction,tran[i,1]) #Add the transaction to min_wei_path
                path_list.extend(min_wei_path) #add the path to the path list
            else:
                var=0 #even if partial transaction fails, abort the whole transaction
                if path_list!=[]:
                    bi_G=AddWeights(bi_G,path_list,-transaction,tran[i,1]) 
                    #remove the transaction that was added to the graph
                break
        if var!=0: #if the whole transaction went through
            bi_G=Balancing(bi_G,path_list,tran[i,1]) #balance the outstanding transaction
            no_of_succ_tran=no_of_succ_tran+1 #update the number of successful transactions
            amount_of_succ_tran=amount_of_succ_tran+tran[i,2] #update the amount of successful transactions
    for i in range(0,len(bi_edges)):
        total_buffer=total_buffer+bi_G[bi_edges[i,0]][bi_edges[i,1]]['weight'] 
        #output the total imbalance in the network
    f = open("Blockchain/water_filling.txt","a+")
    f.write('------------------------------------')
    f.write("\r\n")
    f.write("no_of_succ_tran =%f," %no_of_succ_tran)
    f.write("\r\n")
    f.write("amount_of_succ_tran=%f" %amount_of_succ_tran)
    f.write("\r\n")
    f.write("total_buffer = %f," %total_buffer)
    f.write("\r\n")
    f.write("M = %f," %M)
    f.write("\r\n")
    f.write('------------------------------------')
    f.write("\r\n")
    f.close()