content: from __future__ import division
  import numpy as np
  import math as m
  from easygui import multenterbox
  import pandas as pd
  import matplotlib.pyplot as plt
  import math as m
  
  def import_xl(file_path):
      df = pd.read_excel(file_path,header = None)
      df = df.values
      return df
  
  def export_xl(file_path,sheets):
      writer = pd.ExcelWriter(file_path)
      for sheet,name in sheets.items():
          df = pd.DataFrame(name)
          df.to_excel(writer,sheet)
      writer.save()
  
  #Henter ut en kolonne
  def column(matrix, i):
      return [row[i] for row in matrix]
  
  #Henter ut en rad
  def row(matrix, i):
      return [column[i] for column in matrix]
  
  #Selection sort O(n2)        
  def selection_sort(array):
      n = len(array)
      for i in range(0,n):
          smallest = i
          for j in range(i,n):
              if array[j]<array[smallest]:
                  smallest = j
          copy = array[i]
          array[i] = array[smallest]
          array[smallest] = copy
      return array
  
  #Leser om to lister inneholder minst ett felles tall
  def common_node(array_1,array_2):
      x = selection_sort(array_1)
      y = selection_sort(array_2)
      i = 0
      j = 0
      share = 0
      stop = max([len(x),len(y)])-1
      while min([i,j])< stop:
          if x[i]>y[j]:
              j+=1
          elif x[i]<y[j]:
              i+=1
          else:
              share = 1
              j = 10**6
              i = 10**6
      return share
  
  def common_node_count(array_1,array_2):
      x = selection_sort(array_1)
      y = selection_sort(array_2)
      i = 0
      j = 0
      share = 0
      while i < len(x) and j < len(y):
          if x[i]>y[j]:
              j+=1
          elif x[i]<y[j]:
              i+=1
          else:
              share += 1
              j +=1
              i +=1
      return share
  
  #KORTERSTE RUTE FUNKSJONER
  
  #Lager en graf fra lenke-liste
  def make_graph(array):
      #nodes = common_node_count(column(array,0),column(array,1))
      nodes = 35
      matrix = np.full((nodes,nodes),10**6) #Lager matrise med store tall som byttes
      for i in range(0,len(array)): #Hovedloop
          #Trekker fra en for sammenlignbarhet med python-arrays
          matrix[array[i][1]-1][array[i][0]-1] = array[i][2]
          matrix[array[i][0]-1][array[i][1]-1] = array[i][2]
      np.fill_diagonal(matrix, 0)
      return matrix
  
  #Lager lengdematrise n x n
  def floyd_warshall(array):
      matrix = make_graph(array)
      #nodes = common_node_count(column(array,0),column(array,1))
      nodes = 35
      pred = np.full((nodes,nodes),-1)
  
      for i in range(0,nodes):
          for j in range(0,nodes):
              if i != j:
                  pred[i][j] = i
      
      for k in range(0,nodes):
          for i in range(0,nodes):
              for j in range(0,nodes):
                  if matrix[i][j] > matrix[i][k] +  matrix[k][j]:
                      matrix[i][j] = matrix[i][k] +  matrix[k][j]
                      pred[i][j] = pred[k][j]
      return matrix,pred
  
  #Laster inn data fra en csv fil til et nettverksarray
  def get_network(net_csv):
      graf = open(net_csv,'r')
      lenker=0
      for line in graf:
          lenker+=1
      graf_edit = np.full((lenker, 3),0)
      graf = open(net_csv,'r')
      k = 0
      for line in graf:
          stuff = line.split(";")
          graf_edit[k][0] = float(stuff[0])
          graf_edit[k][1] = float(stuff[1])
          temp = stuff[2].split('\n')[0]
          graf_edit[k][2] = float(temp)
          k+=1
      return graf_edit
  
  #Lager en path-vektor
  def path(p,i,j,path_vec):
      if i == j:
          path_vec.append(i) 
      else:
          path(p, i, p[i][j],path_vec)
          path_vec.append(j)
          
  #Henter en spesifikk path
  def get_path(p,i,j):
      #j = j + 1
      path_vec=[]
      path(p,i,j,path_vec)
      #for i in range(1,len(path_vec)):
      #    path_vec[i] = path_vec[i] - 1
      return path_vec
  
  #Lager adjecency-matrise (ikke ferdig)
  def build_adj(pred):
      
      adj_mat = np.zeros((len(pred),len(pred)))
      array_a = []
      array_b = []
      for i in range(1,len(pred)):
          for j in range(1,len(pred)):
              array_a = get_path(pred,i,j)
              print array_a
              array_b = get_path(pred,2,10)
              print array_b
              try:
                  adj_mat[1][j] = common_node(array_a,array_b)
              except:
                  adj_mat[1][j] = 0
                  
              print adj_mat[1][j]
              
      return adj_mat
  
  
  #Nettverkslaster
  #Argumenter: (1) Forgjenger-matrise (2) antall noder (3) nettverksfil (4) od-matrise
  def network_loader(graf,net,od,pred):
  
      #Antall noder
      n = len(od)-1
  
      #Redigering
      for k in range(0,len(net)):
          net[k][3]=0 #Nulllstiller antall reiser
          net[k][2]=graf[k][2] #Legger inn oppdaterteavstander fra grafen        
  
      #Legger ut reiser paa nettet
      for i in range(0,n):
          for j in range(0,n):
              path = get_path(pred,i,j)
              len_path=get_len_path(path)
              for h in range(0,len_path):
                  for k in range(0,len(net)):
                      if net[k][0] == path[h]+1 and net[k][1] == path[1+h]+1:
                          net[k][3] += int(od[i][j])
                      elif net[k][1] == path[h]+1 and net[k][0] == path[1+h]+1:
                          net[k][3] += int(od[i][j])
      return net
  
  #a=get_path(pred,5,12)
  
  #GRAVITASJONSFUNKSJONER
  def deter_mat_make(length_mat):
      
      deter_mat = np.zeros((len(length_mat),len(length_mat)))
      for i in range(0,len(length_mat)):
          for j in range(0,len(length_mat)):
              deter_mat[i][j] = deter(length_mat[i][j])
      return deter_mat
      
  def deter(length):
      return 2.71**(beta*length)
  
  def sumproduct(list1,list2):
      
      sums = 0
      for i in range(0,len(list1)):
          sums += list1[i]*list2[i]
      return sums
          
  def gravity(origin, destination, length_mat):
      
      #Initialization
      deter_mat = deter_mat_make(length_mat) #Lager matrise med forvitring
      dimension = len(origin) #Henter ut matrisedimensjonene
      alpha = [1]*(dimension) #Intitierer alpha-vektor
      beta = [1]*(dimension)  #Intitierer beta-vektor
      largest = 10**6         #Intitierer storste avvik
      alpha_last = alpha      #Intitierer alpha -1
      beta_last = beta        #Intitierer beta -1
      k = 0                   #Intitierer tellevariabler for iterasjoner
      iterasjoner = []
      
      #Hovedlokke
      while largest > .00001:
          
          #Oppdaterer faktorene
         for p in range(0,dimension):
            alpha[p] = origin[p]/(sumproduct(beta_last,column(deter_mat,p)))
            beta[p] = destination[p]/(sumproduct(alpha,row(deter_mat,p)))
            largest = 0
            
          #Looper for aa finne storste element
         for j in range(0,dimension):
             current = alpha[j]*sumproduct(beta,column(deter_mat,j))-origin[j]
             if current>largest:
                 largest = current
                 
          #Setter forrige beta
         beta_last = beta
         iterasjoner.append(largest)
         #Legger til en iterasjon
         k+=1
         print "Konvergens, Gravitasjonsmodell", largest
         if k == maxiter:
             largest = 0
         
      return alpha,beta,k,iterasjoner
  
  def create_od(origin,destination, length_mat):
      
      alpha,beta,k,iterasjoner = gravity(origin, destination, length_mat)
      deter_mat = deter_mat_make(length_mat)
      od = np.zeros((len(origin),len(origin)))
      
      for i in range(0,len(origin)):
          for j in range(0,len(origin)):
              od[i][j] = alpha[i]*beta[j]*deter_mat[i][j]
      return od,alpha,beta,k,iterasjoner
  
  def calc_pt_matrix(od,length_mat):
      out_od = np.zeros((len(od),len(od)))
      for i in range(0,len(od)):
          for j in range(0,len(od)):
              out_od[i][j] = int(out_od[i][j])*length_mat[i][j]
      return out_od
  
  def get_min(net):
      smallest = 10**6
      smallest_id = 10**6
      for i in range(0,len(net)):
          if net[i][3]/net[i][2]<smallest and net[i][5]==0:
              smallest = net[i][3]/net[i][2]
              smallest_id = i
      return smallest_id,smallest
   
  
  def change_graph(graph,net):
      graph_out = graph
      for i in range(0,len(net)):
          if net[i][5]==1:
              graph_out[i][2]=k_just*graph_out[i][2]
      return graph_out
  
  def production(net):
      sumcost = 0
      for i in range(0,len(net)):
          if net[i][5]!=1:
              sumcost += (net[i][3]/capacity)*net[i][2]
      return sumcost
  
  def sum_pass(net):
      sumpass = 0
      for i in range(0,len(net)):
          sumpass+=net[i][3]
      return sumpass
  
  def get_len_path(path):
      len_path = 0
      if len(path) < 3:
          len_path = 0
      elif len(path) == 3:
          len_path = 2
      else:
          len_path=int(len(path)/2)+int(len(path)%2)+1
      return len_path
  
  def obj(od,length_mat,net,prodgoal):
      return (production(net)*kmk*dogn-prodgoal)**2*(k_just-1)*capacity/.9+time_cost(od,length_mat)
      
  def time_cost(od,length_mat):
      cost = 0
      for i in range(0,len(od)-1):
          for j in range(0,len(od)-1):
              cost += od[i][j]*length_mat[i][j]
      return cost
  
  def get_zero_net(net):
      zero_net = np.zeros((len(net),6))
      for i in range(0,len(net)):
          zero_net[i][2] = net[i][2]
          zero_net[i][3] = net[i][3]
          zero_net[i][5] = net[i][5]
      return zero_net
  
  def update_zero_net(net,zero_net):
      for i in range(0,len(net)):
          zero_net[i][5] = net[i][5]
      return zero_net
  