Skip to content
Permalink
master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

QKDNetJournal/Simulator--with_changes!.py

Go to file
 
 
Cannot retrieve contributors at this time
executable file 1563 lines (1347 sloc) 49.9 KB
Raw Blame
Open in GitHub Desktop
#!/bin/python3
"""
Graph Rep:
N^2 = number of nodes (nodes {1-n^2})
Assume a square grid, so each node is connect0 to i-1, i+1, i+n
A set T |T| >=2 {1,n^2} Union {i} such that node i are trusted nodes
"""
from __future__ import print_function
from ortools.graph import pywrapgraph
import random
import collections
import sys
from copy import deepcopy
from math import log2
import math
import networkx as nx
# global balance
# global prio_a
# global prio_b
# global prio_last
prio_last = None
prio_a = prio_b = 1000
prio_timer = 0
balance = False
filt = None
prio_counts = {}
# global CAD
CAD = False
from Graphs import *
import contextlib
class DummyFile(object):
def write(self, x): pass
@contextlib.contextmanager
def nostdout():
save_stdout = sys.stdout
sys.stdout = DummyFile()
yield
sys.stdout = save_stdout
def check_and_determine_balancing(balance_info, G):
#create graph from balance_info, call R2 on it, for each edge do DFS from A to B based on updated balances
# Do we balance?
# right now we balance if max edge is 1+ sigma times min edge, but this will usually be true
#delta for NearA observations:
# .2 is best found so far, ith sigma .2. 0 is worse than .2
# .2, .1 is worse than .2 .2 but almost equal to simple balancing
# real question is how/why we do better than the simple balancing. seems like we filter baad things with delta?
delta = 0.2 #check if y/x is high enough aand worth balancing .2 best so far for Near A .0766
max_dist = G._paths[G._Alice][G._Bob]*.75 # max distance between candidate balance paths
sigma = .15 # 1+sigma is min ratio between between min aand max keypool
global prio_timer
global prio_last
# if prio_timer != 20:
# prio_timer +=1
# return prio_last
# print(balance_info)
if not "Sigma" in prio_counts:
print(f"Prio counts reset to {prio_counts} in starting balance")
prio_counts["Sigma"] = sigma
prio_counts["Delta"] = delta
pools = [balance_info[i][j] for i in balance_info for j in balance_info[i] if balance_info[i][j] > 0]
if not pools:
prio_counts[(False, "No Pools")] = prio_counts.get((False, "No Pools"), 0) + 1
return False
balance_flag = (1+sigma) * min(pools) < max(pools)
max_diff = max(pools)-min(pools)
# print(max_diff)
# if we balance, find constraining edges, and then most constraining edges
if not balance_flag:
prio_counts[(False, "No Sigma")] = prio_counts.get((False, "No Sigma"), 0) + 1
return False
bottlenecks = find_bottleneck_edges(balance_info, G._Alice, G._Bob)
# print(f"Bottleneck edges: {bottlenecks}")
if not bottlenecks:
prio_counts[(False, "No bottlenecks")] = prio_counts.get((False, "No bottlenecks"), 0) + 1
return False
#with bottlenecks, we want to filter/sort
# TODO: need a good way of picking m
boost = amt_constraining(balance_info, G, bottlenecks)
dist = lambda edge: G._paths[edge[0]][edge[1]]
# candidate = lambda x: dist(x[0]) * 1 if x[1]/max_diff >= delta and dist(x[0]) < max_dist else 0
# # print("boost", boost)
# print([(x[0],candidate(x)) for x in boost])
# best_edge = max(boost,key = candidate)
# Question: which is better! Better ratio on longer paths or shorter paths with worse ratio? switch order of filtering
# print(boost)
## print([(x[0],x[1]/max_diff) for x in boost])
# filter_delta = [cand for cand in boost if cand[1]/max_diff > delta]
# print([(x[0],x[1]/(balance_info[x[0][0]][x[0][1]] if balance_info[x[0][0]][x[0][1]] else .000001) ) for x in boost])
filter_delta = [cand for cand in boost if cand[1]/(balance_info[cand[0][0]][cand[0][1]] if balance_info[cand[0][0]][cand[0][1]] else .000001)> delta]
# print(filter_delta)
filter_length = [cand for cand in filter_delta if dist(cand[0]) < max_dist]
# print(filter_length)
#now filter_length has only candidate bottlnecks that boost by enough and are eshort enough, take most boosting shortest edge
if filter_length:
shortest_len = dist(min([x[0] for x in filter_length], key= dist))
# print(shortest_len)
filter_length2 = [cand for cand in filter_length if dist(cand[0]) == shortest_len]
# print(filter_length2)
best_boost = max(filter_length2, key= lambda cand: cand[1])[1]
# print(best_boost)
filter_boost = [cand for cand in filter_length2 if cand[1] == best_boost]
else:
filter_boost = []
if filter_boost:
best_edge = random.choice(filter_boost)
# print("Balance info: ", balance_info)
# print("Bottlneck edges: ", bottlenecks)
# print("Boost flow by:" , boost)
# print("Filtering for delta and lenght:", filter_boost)
# print(" ", best_edge)
# print ("----\n\n")
prio_last = best_edge[0]
prio_timer = 0
return best_edge[0]
# if best_edge[1] != 0 and candidate(best_edge) != 0:
# return best_edge[0]
else:
prio_counts[(False, "no candidate")] = prio_counts.get((False, "no candidate"), 0) + 1
return False
def get_maxflow(balance_info, source,sink):
start_nodes, end_nodes, capacities = [],[],[]
for i in balance_info:
for j in balance_info[i]:
if balance_info[i][j]: #chnaged from K to kb, hopefullt fixes keybit error
start_nodes.append(i)
end_nodes.append(j)
capacities.append(balance_info[i][j])
if start_nodes:
with nostdout():
flow = maxflow_ortools(start_nodes, end_nodes, capacities, source, sink)
return flow.OptimalFlow()
else:
return 0
def amt_constraining(balance_info, G, bottlenecks):
# returns an array of tuples containing constraining edges and the number of bits that can be added to the flow
#if we add x keybits to that edge
pools = [balance_info[i][j] for i in balance_info for j in balance_info[i] if balance_info[i][j] > 0]
# print(balance_info)
# print(pools)
max_diff = max(pools)-min(pools)
baseline = get_maxflow(balance_info, G._Alice, G._Bob)
new_flows = []
for edge in bottlenecks:
balance_info[edge[0]][edge[1]]+=max_diff
new_flows.append((edge, get_maxflow(balance_info, G._Alice, G._Bob) - baseline))
balance_info[edge[0]][edge[1]]-= max_diff
return new_flows
def find_bottleneck_edges(balance_info, source, sink):
#create flownetwork with balanceinfo capacities, run Ford fulkersons.
# on residual graph, for each edge run DFS(source) and DFS(sink), any edge (u,v)
# where u is reachable from source and v from sinik is a bottleneck
# print("Looking for bottleneck edges")
#first, get a flow from ortools
start_nodes, end_nodes, capacities = [],[],[]
for i in balance_info:
for j in balance_info[i]:
if balance_info[i][j]: #chnaged from K to kb, hopefullt fixes keybit error
start_nodes.append(i)
end_nodes.append(j)
capacities.append(balance_info[i][j])
# print(capacities)
if start_nodes:
with nostdout():
flow = maxflow_ortools(start_nodes, end_nodes, capacities, source, sink)
else:
return [] # no keybits yet
flow_dict = {s: {e:0 for e in end_nodes} for s in start_nodes}
for i in range(flow.NumArcs()):
flow_dict[flow.Tail(i)][flow.Head(i)] = flow.Flow(i)
# residual graph should have 2 components, 1 with sink and 1 with source
# any edge that has one endpoint is each is a bottleneck
G = nx.Graph()
G.add_nodes_from(balance_info.keys())
for i in flow_dict:
for j in flow_dict[i]:
if i >= j:
continue
if balance_info[i][j] - flow_dict[i][j] > 0:
G.add_edge(i,j)
G.add_edge(j,i)
# print(G.edges())
from_source = [i for i in nx.dfs_postorder_nodes(G, source)] # nx.dfs_edges(G,source)
# from_source_comp = set([e[0] for e in from_source_edges]+[e[1] for e in from_source_edges])
from_sink = [i for i in nx.dfs_postorder_nodes(G, sink)] #nx.dfs_edges(G,sink)
# from_sink_comp = set([e[0] for e in from_sink_edges]+[e[1] for e in from_sink_edges])
bottlenecks = []
for i in balance_info:
for j in balance_info:
if i in from_source and j in from_sink and i < j:
bottlenecks.append((i,j))
# print("Got bottleneck edges: {}".format(bottlenecks))
return bottlenecks
def generate_network(n,T, p, q, d, l, alpha , shape = "grid"):
# print(shape)
if shape == "ring":
G = RingGraph(n,T)
elif shape == "braid":
G = BraidedRingGraph(n,T)
elif shape == "wheel":
G = WheelGraph(n,T)
elif shape == "bwheel":
G = BraidedWheelGraph(n,T)
else:
G = GridGraph(n,T)
L = {i:{j: l for j in G.get_nodes()} for i in G.get_nodes()}
P = {i:{j: p for j in G.get_nodes()} for i in G.get_nodes()}
D = {i:{j: d for j in G.get_nodes()} for i in G.get_nodes()}
Q = [q for i in G.get_nodes()]
K = {i:{j: 0 for j in G.get_trusted()} for i in G.get_trusted()}
Kb = {i:{j: [] for j in G.get_trusted()} for i in G.get_trusted()}
if l is not None and alpha is not None:
if "b" in shape or "wheel" in shape:
theta = (n-2)*180/n
for i in P:
for j in P[i]:
if "b" in shape and j == i+2 % n:
L[i][j] = l*math.sqrt(2-2*math.cos(math.radians(theta)))
P[i][j] = 10**(-alpha*L[i][j]/10)
D[i][j] = d*(L[i][j]/l)
if "wheel" in shape and j == n:
L[i][j] = l/(2*math.sin(math.radians(180/n)))
P[i][j] = 10**(-alpha*L[i][j]/10)
D[i][j] = d*(L[i][j]/l)
else:
print("Didn't get l and alpha!! UNIFORM NETWORK")
for i in P:
for j in P[i]:
L[i][j] = 0
return (G,L,P,Q,D,K, Kb)
def pair_ent(G, P):
G1 = type(G)(G.get_dim(), G.get_trusted(), G._weight, G._Alice, G._Bob)
G1.set_edges([e for e in G.get_edges() if PRNG_gen.random() < P[e[0]][e[1]]])
return G1
def R1_find_best_links(G,G1,K,node, dumb, het_dist):
neighbors = G1.get_neighbors(node) #these nodes are connected by ent channel to our noe
trusted = G1.get_trusted()
dist = lambda x: G._paths[x[0]][x[1]]
kmdist = lambda x: G._realpaths[x[0]][x[1]] if het_dist else 1
Pt = []
if len(neighbors) <=1:
return [] # coudn't add any
#We have a list of neighbor nodes and unique trsuted nodes, and the distance between them
neigh_trusted1 = [(u,T) for u in neighbors for T in trusted]
#print("Node:", node)
#print("Dists1: ", neigh_trusted1)
best_dist_1 = dist(min(neigh_trusted1, key=dist)) #this gives us the best distance
Poss1 = [p for p in neigh_trusted1 if dist(p) == best_dist_1]
best_kmdist_1 = kmdist(min(Poss1, key =kmdist))
Poss1 = [p for p in Poss1 if kmdist(p) == best_kmdist_1]
#print(Poss1)
(v1,t1) = PRNG_gen.choice(Poss1)
neigh_trusted2 = [(u,T) for u in neighbors for T in trusted if T!=t1]
best_dist_2 = dist(min(neigh_trusted2, key=dist)) #this gives us the best distance
Poss2a = [p for p in neigh_trusted2 if dist(p) == best_dist_2 ]
best_kmdist_2 = kmdist(min(Poss2a, key =kmdist))
Poss2a = [p for p in Poss2a if kmdist(p) == best_kmdist_2] # TODO should this go before or after smart check, prob before
Poss2 = [p for p in Poss2a if abs(node-p[0]) == abs(node-v1)]
if dumb or not Poss2 : #if dumb flag is set dont try and maintain direction
Poss2 = Poss2a
#print(Poss2)
(v2,t2) = PRNG_gen.choice(Poss2)
if v1 == v2:
#Trying
next_nt1 = [p for p in neigh_trusted1 if p[0] != v1 and p[1] != t2]
next_nt2 = [p for p in neigh_trusted2 if p[0] != v2 and p[1] != t1]
next_best_1 = dist(min(next_nt1, key=dist))
next_best_2 = dist(min(next_nt2, key=dist))
next_poss1 = [p for p in next_nt1 if dist(p) == next_best_1]
next_poss2 = [p for p in next_nt2 if dist(p) == next_best_2]
(nv1, nt1) = PRNG_gen.choice(next_poss1)
(nv2, nt2) = PRNG_gen.choice(next_poss1)
if dist((v1,t1)) + dist((nv2, nt2)) < dist((nv1,nt1)) + dist((v2,t2)):
v2,t2 = nv2,nt2
elif dist((v1,t1)) + dist((nv2, nt2)) >dist((nv1,nt1)) + dist((v2,t2)):
v1,t1 = nv1,nt1
else:
which = PRNG_gen.choice([0,1])
if which:
v1,t1 = nv1,nt1
else:
v2,t2 = nv2,nt2
if v1 == v2:
raise RuntimeError("Error, trying to link same node to itself")
Pt.append([min(v1,v2), node, max(v1,v2)])
neighbors.remove(v1)
neighbors.remove(v2)
if len(neighbors)==2:
Pt.append([min(neighbors), node, max(neighbors)])
return Pt
def local_R1(G, G1, K, dumb, balance_counts, het_dist):
#G1.show_graph()
global balance
global prio_a
global prio_b
global prio_last
prio = None
G.add_graph()
G.all_paths()
trusted = G1.get_trusted()
dynamic = True
# G1.show_graph()
print("---")
""" simple balancing
"""
if len(trusted) == 3 and balance and balance_counts and not dynamic:
sigma = .15
prio_counts["Sigma"] =sigma
prio_counts["Delta"] = "SIMPLE"
#if K[trusted[0]][trusted[1]] > balance * K[trusted[1]][trusted[2]]:
if balance_counts[trusted[0]][trusted[1]] > (1+ sigma) * balance_counts[trusted[1]][trusted[2]]:
if prio_last != "B":
G._paths = None
G.all_paths()
for node in G._paths:
for n2 in G._paths[node]:
if n2 == trusted[0] and G._paths[node][n2]:
G._paths[node][n2] = float('inf')
prio = "B"
prio_b +=1
prio = (trusted[1], trusted[2])
prio_counts[prio] = prio_counts.get(prio, 0) + 1
#print(K)
#elif K[trusted[1]][trusted[2]] > balance * K[trusted[0]][trusted[1]]:
elif balance_counts[trusted[1]][trusted[2]] > (1+sigma) * balance_counts[trusted[0]][trusted[1]]:
if prio_last != "A":
G._paths = None
G.all_paths()
for node in G._paths:
for n2 in G._paths[node]:
if n2 == trusted[2] and G._paths[node][n2]:
G._paths[node][n2] = float('inf')
prio = "A"
prio_a += 1
prio = (trusted[0], trusted[1])
prio_counts[prio] = prio_counts.get(prio, 0) + 1
#print(K)
else:
if prio_last:
G._paths = None
G.all_paths()
prio = None
prio = False
prio_counts[prio] = prio_counts.get(prio, 0) + 1
if balance and dynamic:
prio = check_and_determine_balancing(balance_counts, G)
if prio:
prio_counts[prio] = prio_counts.get(prio, 0) + 1
if not prio:
if prio_last:
G._paths = None
G.all_paths()
elif prio_last != prio:
G._paths = None
G.all_paths()
for node in G._paths:
for n2 in G._paths[node]:
if n2 not in prio:
G._paths[node][n2] = float('inf') #TODO can this be better to account for others? not sure dont think so OTOMH
prio_last = prio
Pt = []
for node in G1.get_nodes():
if node in trusted:
for neighbor in G1.get_neighbors(node):
if neighbor in trusted:
Pt.append([node, neighbor])
G1.remove_edge(node, neighbor)
if node not in trusted:
result = R1_find_best_links(G,G1,K,node, dumb, het_dist)
#print("best links for ", node, result)
#print(result)
if result:
#print("Result," ,result)
#print("Path", Pt)
for add in result:
added = False
#print("new", add)
for path in Pt:
#print(" add, path", add[:-1], path[-2:])
if add[:-1] == path[-2:]:
path.append(add[-1])
added = True
#print("mrg-",Pt)
elif add[::-1][:-1] == path[-2:]: #checks if we have a reverse connection, like in a ring
path.append(add[::-1][-1])
added = True
if not added:
Pt.append(add)
#print(Pt)
#raise RuntimeError
ret = [p for p in Pt if p[0 ] in trusted and p[-1] in trusted]
for path in ret:
for pathi in range(len(path)-1):
G1.remove_edge(path[pathi], path[pathi+1])
return ret
# global balance
# global prio_a
# global prio_b
# prio_a = prio_b = 0
def R1(G,G1, L,K, balance_counts, het_dist):
global balance
global prio_a
global prio_b
global prio_counts
G1.add_graph()
trusted = G.get_trusted()
Pt = []
first_flag = False
if not G._paths:
G.all_paths()
prio = None
old_prio = None
dynamic = True
#G1.show_graph()
# print("---")
"""
Simple balancing
"""
if len(trusted) == 3 and balance and balance_counts and not dynamic:
sigma = .15
prio_counts["Sigma"] =sigma
prio_counts["Delta"] = "SIMPLE"
#if K[trusted[0]][trusted[1]] > balance * K[trusted[1]][trusted[2]]:
if balance_counts[trusted[0]][trusted[1]] > (1+sigma) * balance_counts[trusted[1]][trusted[2]]:
prio = (trusted[1], trusted[2])
prio_counts[prio] = prio_counts.get(prio, 0) + 1
prio_b +=1
# print("Prioritizing B")
#print(K)
#elif K[trusted[1]][trusted[2]] > balance * K[trusted[0]][trusted[1]]:
elif balance_counts[trusted[1]][trusted[2]] > (1+sigma) * balance_counts[trusted[0]][trusted[1]]:
prio = (trusted[0], trusted[1])
prio_counts[prio] = prio_counts.get(prio, 0) + 1
prio_a += 1
#print("Prioritizing A")
#print(K)
else:
prio = False
prio_counts[prio] = prio_counts.get(prio, 0) + 1
if balance and dynamic:
prio = check_and_determine_balancing(balance_counts, G)
# print(f"Balanced: prio {prio}")
if prio:
prio_counts[prio] = prio_counts.get(prio, 0) + 1
else:
pass
# print("No prio")
# prrio = False
# print(prio)
while True:
# print("in whiile True in R1")
shortest_paths = []
if not balance or not prio:
for TN1 in trusted:
for TN2 in trusted:
if TN1 < TN2:
# shortest_paths += G1.all_shortest_paths(TN1, TN2)
shortest_paths.append(G1.get_random_shortest_path(TN1,TN2))
# elif prio == "B":
# shortest_paths += G1.all_shortest_paths(trusted[1], trusted[2])
# elif prio == "A":
# shortest_paths += G1.all_shortest_paths(trusted[0], trusted[1])
else:
# shortest_paths += G1.all_shortest_paths(prio[0], prio[1])
shortest_paths.append(G1.get_random_shortest_path(prio[0],prio[1]))
adds = [p for p in shortest_paths if len(p)!=0]
#print("lens ", [[x[0],x[-1],len(x)] if x else "" for x in shortest_paths])
#print("Paths", adds)
mina = min(adds, key = lambda x: len(x)) if adds else []
#print("mina =", mina)
adds = [p for p in adds if len(p) == len(mina)]
# Further find mindist and filter off that first QUESTION/TODO: should this go before or after ABpath
if het_dist:
adds_dists = []
for p in adds:
d = 0
for i in range(len(p)-1):
try:
d+=L[p[i]][p[i+1]]
except:
print(L)
print(p, i, i+1, p[i],p[i+1])
exit(0)
adds_dists.append(d)
adds = [adds[i] for i in range(len(adds)) if adds_dists[i]== min(adds_dists)]
# Checking if their are any minimal A-B paths, only pick from them if true
ABpath = False
for path in adds:
if path[0] == G._Alice and path[-1] == G._Bob:
ABpath = True
if ABpath:
adds = [p for p in adds if p[0] == G._Alice and p[-1] == G._Bob]
if type(G) in (WheelGraph, BraidedWheelGraph):
ringpath = False
for path in adds:
if max(G._nodes) not in path:
ringpath = True
if ringpath:
adds = [p for p in adds if max(G._nodes) not in p]
#print("chosing from", adds)
# print("T", trusted)
# print("adds",addcs)
add = PRNG_ran.choice(adds) if adds else []
# print("adding", add)
# print("add",add)
#add = adds[-1] if adds else []
#print("chose", add)
# print("")
if add:
#print("{} -> {} len {}".format(add[0],add[-1], len(add)))
#print("Adding", add)
#if len(add) != 7 and ((add[0],add[-1]) == (0,24) or (add[0],add[-1]) == (24,48)):
# print("Added so far:", [(x,len(x)) for x in Pt])
# print("Paths", adds)
# print("mina =", mina)
# print("chose from", adds)
# print("Adding", add, len(add))
# G1.show_graph()
# add = adds[-1] if adds else []
for j in range(len(add)-1):
G1.remove_edge(add[j], add[j+1])
Pt.append(add)
else:
#print("Breaking")
if prio:
#print("Looking for all")
old_prio = prio
prio = None
else:
break
#print("Added ", Pt)
#print("------")
#G1.show_graph()
prio = old_prio
return Pt
def path_ent(G, Q, D, Pt):
# print(Pt)
G2 = type(G)(G.get_dim(), G.get_trusted(), G._weight, G._Alice, G._Bob) #GridGraph(G.get_dim(), G.get_trusted())
G2.set_nodes(G.get_trusted())
edges = []
pathinf = []
for p in Pt:
prob_suc = 1
prob_dep = 1-D[p[0]][p[1]]
for i in range(len(p[1:-1])):
pi = p[i]
pi2 = p[i+1]
try:
prob_suc *= Q[pi]
except:
print(prob_suc, Q, pi)
try:
prob_dep *= (1-D[pi][pi2])
except:
print(pi, pi2)
raise RuntimeError
prob_dep = prob_dep + (1-prob_dep)/2
rand = PRNG_ent.random()
if rand <= prob_suc and p[0] in G2.get_trusted() and p[-1] in G2.get_trusted():
edges.append((p[0],p[-1], int(PRNG_ent.random() > prob_dep)))
pathinf.append(1 - prob_dep)
# print(f"Added edge {p[0]} {p[-1]}")
# print(edges)
G2.set_edges([(e[0],e[1]) for e in edges ])
# G2.print_graph()
return G2, edges, pathinf
def attempt_QKD(G, Ed, Pz, Px, K, Kb, pathinf, balance_inf = None):
# print("edges", Ed)
for x in range(len(Ed)):
edge = Ed[x]
path = pathinf[x]
if PRNG_qkd.random() <= Pz*Pz+Px*Px:
i = min(edge[0], edge[1])
j = max(edge[0], edge[1])
K[i][j] +=1
#Kb[i][j]+=str(int(edge[2]))
Kb[i][j].append((str(int(edge[2])),path))
balance_inf[i][j]+=max(0,(1-2*binary_entropy(path)))
## Reverse:
K[j][i] +=1
#Kb[i][j]+=str(int(edge[2]))
Kb[j][i].append((str(int(edge[2])),path))
balance_inf[j][i]+=max(0,(1-2*binary_entropy(path)))
G3 = type(G)(G.get_dim(), G.get_trusted(), G._weight, G._Alice, G._Bob) #GridGraph(G.get_dim(), G.get_trusted())
G3.set_nodes(G.get_trusted())
G3.set_edges(G.get_edges())
return G3, K, Kb, balance_inf
def R2_regular(G,K,Kb,finite = False, thresh = None):
old_K = deepcopy(K)
old_Kb = deepcopy(Kb)
for i in K:
for j in K:
if not K[i][j]:
continue
errors = Kb[i][j].count("1")
Q = float(errors/K[i][j])
#K[i][j] = max(0,int((1-2*binary_entropy(Q))*K[i][j]))
K[i][j] = cad_EC(Q, K[i][j])
Kb[i][j] = "0"*K[i][j]
try:
print(" {} - > {} had {} bits and {} errors, error rate of {} resulting in {} secret key bits".format(i, j,old_K[i][j],errors,Q, K[i][j]))
except:
print(" {} - > {} had {} bits and {} errors, error rate of {}".format(k, kb, k_errors[k][kb][0],k_errors[k][kb][1],0))
#print("+++++++++++++++++++++++++++++++++++++++++++++")
c=0
while True:
c+=1
#print("-------------------- Loop {} ------------".format(c))
# print(K)
start_nodes, end_nodes, capacities = [],[],[]
for i in K:
for j in K[i]: #chnaged k to kb
#if Kb[i][j]:
start_nodes.append(i)
end_nodes.append(j)
capacities.append(K[i][j])
# print(start_nodes)
# print(end_nodes)
# print(capacities)
if not (start_nodes and end_nodes and capacities):# or not min(K) in start_nodes or not max(K) in end_nodes:
return 0, 0, old_K, old_Kb
flow = maxflow_ortools(start_nodes, end_nodes, capacities, G._Alice, G._Bob)
##error stuff
flows = []
for i in range(flow.NumArcs()):
for j in range(i,flow.NumArcs()):
if flow.Head(i) == flow.Tail(j) and (flow.Head(i)!=flow.Tail(i)) and (flow.Flow(j) and flow.Flow(i)):
print(' %1s -> %1s %3s / %3s' % (flow.Tail(i),flow.Head(i),flow.Flow(i),flow.Capacity(i)))
print(' %1s -> %1s %3s / %3s' % (flow.Tail(j),flow.Head(j),flow.Flow(j),flow.Capacity(j)))
flows.append([flow.Tail(i), flow.Head(i), flow.Head(j), min(flow.Flow(i),flow.Flow(j))])
#print(flows[-1])
# print("Flows is ", flows)
if len(flows) <= 1:
print(" Breaking flows")
break
for f in flows:
# print("consiering at", f)
if True or not (f[0] == G._Alice and f[1] == G._Bob):
try:
new_str = "".join([str(int(Kb[f[0]][f[1]][i]) ^ int(Kb[f[1]][f[2]][i])) for i in range(f[3])])
# print("Looking at", f)
except Exception as e:
print("Error")
print("Flow", f)
print("Kb[{}][{}]".format(f[0],f[1]), Kb[f[0]][f[1]])
print("Kb[{}][{}]".format(f[1],f[2]), Kb[f[1]][f[2]])
print(e)
raise RuntimeError
# print("1", Kb[f[0]][f[1]])
# print("2", Kb[f[1]][f[2]])
# print("xor" ,new_str)
# print("old", Kb[f[0]][f[2]])
Kb[f[0]][f[1]] = Kb[f[0]][f[1]][f[3]:]
Kb[f[1]][f[2]] = Kb[f[1]][f[2]][f[3]:]
Kb[f[0]][f[2]] += new_str
K[f[0]][f[1]] -=f[3]
K[f[1]][f[2]] -=f[3]
K[f[0]][f[2]] +=f[3]
# print("old1",Kb[f[0]][f[1]])
# print("old2",Kb[f[1]][f[2]])
# print("new",Kb[f[0]][f[2]])
break
if flows:
f= flows[0]
try:
new_str = "".join([str(int(Kb[f[0]][f[1]][i]) ^ int(Kb[f[1]][f[2]][i])) for i in range(f[3])])
# print("Looking at", f)
except Exception as e:
print("Error")
print("Flow", f)
print("Kb[{}][{}]".format(f[0],f[1]), Kb[f[0]][f[1]])
print("Kb[{}][{}]".format(f[1],f[2]), Kb[f[1]][f[2]])
print(e)
raise RuntimeError
# print("1", Kb[f[0]][f[1]])
# print("2", Kb[f[1]][f[2]])
# print("xor" ,new_str)
# print("old", Kb[f[0]][f[2]])
Kb[f[0]][f[1]] = Kb[f[0]][f[1]][f[3]:]
Kb[f[1]][f[2]] = Kb[f[1]][f[2]][f[3]:]
Kb[f[0]][f[2]] += new_str
K[f[0]][f[1]] -=f[3]
K[f[1]][f[2]] -=f[3]
K[f[0]][f[2]] +=f[3]
# print("old1",Kb[f[0]][f[1]])
# print("old2",Kb[f[1]][f[2]])
# print("new",Kb[f[0]][f[2]])
errors = Kb[G._Alice][G._Bob].count("1")
# print("Error string is " ,len(Kb[min(Kb)][max(Kb)]))
##reset K, Kb
Kb[G._Alice][G._Bob]=""
for i in range(flow.NumArcs()):
K[flow.Tail(i)][flow.Head(i)]-=flow.Flow(i)
#print(Kb)
#print(K)
# print("Flows", flows)
# print("maxflow", flow.OptimalFlow())
# print("HERE")
return flow.OptimalFlow(), errors, K, Kb
def R2_regular_all(G, K_all, Kb_all, finite= False, thresh = None):
K = {i:{j: 0 for j in G.get_trusted()} for i in G.get_trusted()}
Kb = {i:{j: "" for j in G.get_trusted()} for i in G.get_trusted()}
for x in Kb_all:
for y in Kb_all[x]:
if not K_all[x][y]:
continue
keys = dict()
for keybit in Kb_all[x][y]:
if keybit[1] in keys:
keys[keybit[1]][0] += 1
keys[keybit[1]][1] += int(keybit[0])
else:
keys[keybit[1]] = [0,0]
# print("{} -> {} decoherence rate: Keybits,error".format(x,y))
# print(keys)
for rate in keys:
try:
Q = keys[rate][1]/keys[rate][0]
except:
Q = 0
#K[x][y]+= max(0,int((1-2*binary_entropy(float(Q)))*keys[rate][0]))
keys[rate].append(cad_EC(Q, keys[rate][0]))
# K[x][y] += cad_EC(Q, keys[rate][0]) #+= becuse we are adding to the keypool for each rate !
K[x][y] += keys[rate][-1]
Kb[x][y] = "0"*K[x][y]
if x < y:
print(" {} - > {} had {} bits and resulted {} secret key bits".format(x, y,K_all[x][y], K[x][y]))
for rate in keys:
try:
Q = keys[rate][1]/keys[rate][0]
except:
Q = 0
print(" {} bits had expected error rate {} and real error rate {}, produced {} secret key bits,".format(keys[rate][0], rate, float(Q) , keys[rate][-1]))
#print("+++++++++++++++++++++++++++++++++++++++++++++")
c=0
while True:
print("Solving")
c+=1
#print("-------------------- Loop {} ------------".format(c))
# print(K)
start_nodes, end_nodes, capacities = [],[],[]
for i in K:
for j in K[i]: #chnaged k to kb
#if Kb[i][j]:
start_nodes.append(i)
end_nodes.append(j)
capacities.append(K[i][j])
# print(start_nodes)
# print(end_nodes)
# print(capacities)
if not (start_nodes and end_nodes and capacities):# or not min(K) in start_nodes or not max(K) in end_nodes:
return 0, 0, old_K, old_Kb
flow = maxflow_ortools(start_nodes, end_nodes, capacities, G._Alice, G._Bob)
##error stuff
flows = []
for i in range(flow.NumArcs()):
for j in range(i,flow.NumArcs()):
if flow.Head(i) == flow.Tail(j) and (flow.Head(i)!=flow.Tail(i)) and (flow.Flow(j) and flow.Flow(i)):
print(' %1s -> %1s %3s / %3s' % (flow.Tail(i),flow.Head(i),flow.Flow(i),flow.Capacity(i)))
print(' %1s -> %1s %3s / %3s' % (flow.Tail(j),flow.Head(j),flow.Flow(j),flow.Capacity(j)))
# flows.append([flow.Tail(i), flow.Head(i), flow.Head(j), flow.Flow(j)])
flows.append([flow.Tail(i), flow.Head(i), flow.Head(j), min(flow.Flow(j),flow.Flow(i))])
pass
#print(flows[-1])
# print("Flows is ", flows)
if len(flows) <= 1:
print(" Breaking flows")
break
for f in flows:
# print("consiering at", f)
if True or not (f[0] == G._Alice and f[1] == G._Bob):
try:
print("Looking at", f)
new_str = "".join([str(int(Kb[f[0]][f[1]][i]) ^ int(Kb[f[1]][f[2]][i])) for i in range(f[3])])
# new_str = "" # this was cuasing errors, maybe because we cant figure out where flows come from, dont need for regular
# print("Looking at", f)
except Exception as e:
print("Error")
print("Flow", f)
print("Kb[{}][{}]".format(f[0],f[1]), Kb[f[0]][f[1]])
print("Kb[{}][{}]".format(f[1],f[2]), Kb[f[1]][f[2]])
print("len[{}][{}]".format(f[0],f[1]), len(Kb[f[0]][f[1]]))
print("len[{}][{}]".format(f[1],f[2]), len(Kb[f[1]][f[2]]))
print(e)
raise RuntimeError
# print("1", Kb[f[0]][f[1]])
# print("2", Kb[f[1]][f[2]])
# print("xor" ,new_str)
# print("old", Kb[f[0]][f[2]])
Kb[f[0]][f[1]] = Kb[f[0]][f[1]][f[3]:]
Kb[f[1]][f[2]] = Kb[f[1]][f[2]][f[3]:]
Kb[f[0]][f[2]] += new_str
K[f[0]][f[1]] -=f[3]
K[f[1]][f[2]] -=f[3]
K[f[0]][f[2]] +=f[3]
# print("old1",Kb[f[0]][f[1]])
# print("old2",Kb[f[1]][f[2]])
# print("new",Kb[f[0]][f[2]])
break
if flows:
f= flows[0]
try:
print("Looking at", f)
new_str = "".join([str(int(Kb[f[0]][f[1]][i]) ^ int(Kb[f[1]][f[2]][i])) for i in range(f[3])])
# new_str = "" # same as above, dont need for regular tn and causing errors
except Exception as e:
print("Error")
print("Flow", f)
print("Kb[{}][{}]".format(f[0],f[1]), Kb[f[0]][f[1]])
print("Kb[{}][{}]".format(f[1],f[2]), Kb[f[1]][f[2]])
print(e)
raise RuntimeError
# print("1", Kb[f[0]][f[1]])
# print("2", Kb[f[1]][f[2]])
# print("xor" ,new_str)
# print("old", Kb[f[0]][f[2]])
Kb[f[0]][f[1]] = Kb[f[0]][f[1]][f[3]:]
Kb[f[1]][f[2]] = Kb[f[1]][f[2]][f[3]:]
Kb[f[0]][f[2]] += new_str
K[f[0]][f[1]] -=f[3]
K[f[1]][f[2]] -=f[3]
K[f[0]][f[2]] +=f[3]
# print("old1",Kb[f[0]][f[1]])
# print("old2",Kb[f[1]][f[2]])
# print("new",Kb[f[0]][f[2]])
errors = Kb[G._Alice][G._Bob].count("1")
# print("Error string is " ,len(Kb[min(Kb)][max(Kb)]))
##reset K, Kb
Kb[G._Alice][G._Bob]=""
for i in range(flow.NumArcs()):
K[flow.Tail(i)][flow.Head(i)]-=flow.Flow(i)
#print(Kb)
#print(K)
# print("Flows", flows)
# print("maxflow", flow.OptimalFlow())
print("HERE1", G._Bob)
print(flow.OptimalFlow())
return flow.OptimalFlow(), errors, K, Kb
def R2_simple(G,K,Kb, finite = False, thresh = None):
#print("+++++++++++++++++++++++++++++++++++++++++++++")
c=0
#print(K)
while True:
c+=1
#print("-------------------- Loop {} ------------".format(c))
# print(K)
start_nodes, end_nodes, capacities = [],[],[]
for i in K:
for j in K[i]:
if Kb[i][j]: #chnaged from K to kb, hopefullt fixes keybit error
start_nodes.append(i)
end_nodes.append(j)
capacities.append(K[i][j])
# print(K,Kb)
# print(start_nodes)
# print(end_nodes)
# print(capacities)
if start_nodes:
flow = maxflow_ortools(start_nodes, end_nodes, capacities, G._Alice, G._Bob)
else:
#raise RuntimeError
return 0, 0, K, Kb
##error stuff
flows = []
for i in range(flow.NumArcs()):
for j in range(i,flow.NumArcs()):
if flow.Head(i) == flow.Tail(j) and (flow.Head(i)!=flow.Tail(i)) and (flow.Flow(j) and flow.Flow(i)):
#print('%1s -> %1s %3s / %3s' % (flow.Tail(i),flow.Head(i),flow.Flow(i),flow.Capacity(i)))
#print('%1s -> %1s %3s / %3s' % (flow.Tail(j),flow.Head(j),flow.Flow(j),flow.Capacity(j)))
flows.append([flow.Tail(i), flow.Head(i), flow.Head(j), min(flow.Flow(j), flow.Flow(i))])
# #print(flows[-1])
# print("Flows is ", flows)
if len(flows) <= 1:
# print("Breaking flows")
break
for f in flows:
# print("consiering at", f)
if True or not (f[0] == G._Alice and f[1] == G._Bob):
try:
new_str = "".join([str(int(Kb[f[0]][f[1]][i]) ^ int(Kb[f[1]][f[2]][i])) for i in range(f[3])])
# print("Looking at", f)
except Exception as e:
print("Error")
print("Flow", f)
print("Kb[{}][{}]".format(f[0],f[1]), Kb[f[0]][f[1]])
print("Kb[{}][{}]".format(f[1],f[2]), Kb[f[1]][f[2]])
print(e)
raise RuntimeError
# print("1", Kb[f[0]][f[1]])
# print("2", Kb[f[1]][f[2]])
# print("xor" ,new_str)
# print("old", Kb[f[0]][f[2]])
Kb[f[0]][f[1]] = Kb[f[0]][f[1]][f[3]:]
Kb[f[1]][f[2]] = Kb[f[1]][f[2]][f[3]:]
Kb[f[0]][f[2]] += new_str
K[f[0]][f[1]] -=f[3]
K[f[1]][f[2]] -=f[3]
K[f[0]][f[2]] +=f[3]
# print("old1",Kb[f[0]][f[1]])
# print("old2",Kb[f[1]][f[2]])
# print("new",Kb[f[0]][f[2]])
break
if flows:
f= flows[0]
try:
new_str = "".join([str(int(Kb[f[0]][f[1]][i]) ^ int(Kb[f[1]][f[2]][i])) for i in range(f[3])])
# print("Looking at", f)
except Exception as e:
print("Error")
print("Flow", f)
print("Kb[{}][{}]".format(f[0],f[1]), Kb[f[0]][f[1]])
print("Kb[{}][{}]".format(f[1],f[2]), Kb[f[1]][f[2]])
print(e)
raise RuntimeError
# print("1", Kb[f[0]][f[1]])
# print("2", Kb[f[1]][f[2]])
# print("xor" ,new_str)
# print("old", Kb[f[0]][f[2]])
Kb[f[0]][f[1]] = Kb[f[0]][f[1]][f[3]:]
Kb[f[1]][f[2]] = Kb[f[1]][f[2]][f[3]:]
Kb[f[0]][f[2]] += new_str
K[f[0]][f[1]] -=f[3]
K[f[1]][f[2]] -=f[3]
K[f[0]][f[2]] +=f[3]
# print("old1",Kb[f[0]][f[1]])
# print("old2",Kb[f[1]][f[2]])
# print("new",Kb[f[0]][f[2]])
errors = Kb[G._Alice][G._Bob].count("1")
# print("Error string is " ,len(Kb[min(Kb)][max(Kb)]))
##reset K, Kb
Kb[G._Alice][G._Bob]=""
#print(K)
#for i in range(flow.NumArcs()):
# print(flow.Tail(i), flow.Head(i), flow.Flow(i))
# K[flow.Tail(i)][flow.Head(i)]-=flow.Flow(i)
K[G._Alice][G._Bob]-=flow.OptimalFlow()
#print(Kb)
#print(K)
#print(K, flow.OptimalFlow())
if finite:
pass
return flow.OptimalFlow(), errors, K, Kb
def maxflow_ortools(start_nodes, end_nodes, capacities, source, sink):
"""MaxFlow simple interface example."""
# Define three parallel arrays: start_nodes, end_nodes, and the capacities
# between each pair. For instance, the arc from node 0 to node 1 has a
# capacity of 20.
#start_nodes = [] #[0, 0, 0, 1, 1, 2, 2, 3, 3]
#end_nodes = [] #[1, 2, 3, 2, 4, 3, 4, 2, 4]
#capacities = [] #[20, 30, 10, 40, 30, 10, 20, 5, 20]
# Instantiate a SimpleMaxFlow solver.
max_flow = pywrapgraph.SimpleMaxFlow()
# Add each arc.
for i in range(0, len(start_nodes)):
max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], int(capacities[i]))
# Find the maximum flow between node 0 and node 4.
try:
if max_flow.Solve(source,sink ) == max_flow.OPTIMAL:
# print('Max flow:', max_flow.OptimalFlow())
# print('')
# print(' Arc Flow / Capacity')
# for i in range(max_flow.NumArcs()):
# print('%1s -> %1s %3s / %3s' % (
# max_flow.Tail(i),
# max_flow.Head(i),
# max_flow.Flow(i),
# max_flow.Capacity(i)))
# print('Source side min-cut:', max_flow.GetSourceSideMinCut())
# print('Sink side min-cut:', max_flow.GetSinkSideMinCut())
pass
else:
print('There was an issue with the max flow input.')
print(start_nodes)
print(end_nodes)
print(capacities)
raise RuntimeError
except Exception as e:
print(start_nodes)
print(end_nodes)
print(capacities)
print(e)
raise RuntimeError
print("Tried to find a flow from {} to {} on {} {} {}".format(source, sink, start_nodes, end_nodes, capacities))
print("Got {}".format(max_flow.OptimalFlow()))
return max_flow
def finite_process_regular(K,Kb, K_fin, finite_block, override = False):
eps_bar = 1e-6
print(finite_block)
for k1 in K:
for k2 in K[k1]:
while K[k1][k2] > (finite_block if not override else 0):
print("nodes", k1,k2)
bits = int(min(finite_block, K[k1][k2]))
print("bits", bits)
K[k1][k2]-= bits
err_string = Kb[k1][k2][:bits]
Kb[k1][k2]=Kb[k1][k2][bits:]
shared_str = random.sample(err_string, int(finite_block/3))
print("errstr", "".join(shared_str))
print("errors", "".join(shared_str).count("1"))
QBER = shared_str.count("1") / float(len(shared_str))
print("calculated", QBER)
worst_case = math.sqrt((2*math.log(1/eps_bar)+2*math.log(1+(finite_block/3.)))/(finite_block/3.))
print("confidence interval", worst_case)
key_rate = max(0,1 - 2 *binary_entropy(QBER+worst_case))
print(key_rate)
exit(0)
def cad_opt(noise, cad):
#print("Doing CAD level {}".format(cad))
decs = []
x = 0
step = .00001
while x < noise:
decs.append(x)
x = min(x+step, noise)
decs.append(x)
maxkey = 5
QC = noise**cad
ec= QC/(QC+(1-noise)**cad)
minval = None
for l4 in decs:
Leq = ((1-3*noise+2*l4)/(1-noise))**cad
Ldiff = (abs(noise - 2*l4)/noise)**cad
# print("noise", "cad", "Leq", "Ldiff", "l4")
# print(noise, cad, Leq, Ldiff, l4)
# print(1-binary_entropy(ec)-(1-ec)*binary_entropy((1-Leq)/2) - ec*binary_entropy((1-Ldiff)/2))
#key = (1-binary_entropy(ec)-(1-ec)*binary_entropy((1-Leq)/2) - ec*binary_entropy((1-Ldiff)/2))
try:
key = ((1 - noise)**cad + noise**cad)*(1/cad)*(1-binary_entropy(ec)-(1-ec)*binary_entropy((1-Leq)/2.) - ec*binary_entropy((1-Ldiff)/2.))
except:
# print("WARNING, CAD_OPT FAILED FOR NOISE {} AND CAD {} and l4 {}".format(noise, cad, l4))
key = 0
if key < maxkey:
maxkey=key
minval = l4
l4 = minval
Leq = ((1-3*noise+2*l4)/(1-noise))**cad
Ldiff = (abs(noise - 2*l4)/noise)**cad
# print("\tnoise = {}, \n\tcad = {}, \n\tl4 = {}, \n\tleq = {}, \n\tldiff = {}, \n\tec = {}, \n\trate ={}".format(noise, cad, l4, Leq, Ldiff, ec, maxkey))
# print(((1 - Q)**cad + Q**cad)*(1/cad)*(1-binary_entropy(ec)-(1-ec)*binary_entropy((1-Leq)/2) - ec*binary_entropy((1-Ldiff)/2)))
return maxkey
# global CAD
def cad_EC(noise, bits):
if not CAD:
return int(max(0,1-2*binary_entropy(noise))*bits)
# print(" Doing CAD on noise {} with {} bits". format(noise, bits))
maxcad = 20 if CAD else 1
maxcad = maxcad if noise not in [0,1] else 1 # if the noise is 0 or 1 we would error in calc
keyrates = [max(0,1-2*binary_entropy(noise))]
for cad in range(2, maxcad+1):
keyrates.append(cad_opt(noise, cad))
# print("At CAD_level {} got keyrate {}".format(cad, keyrates[-1]))
#print("keyrates", keyrates)
# print(" Did CAD on noise {} with {} bits got {} at CAD = {} getting {} more bits".format(noise, bits, int(max(keyrates)*bits), keyrates.index(max(keyrates))+1, int(max(keyrates)*bits) - int(keyrates[0]*bits)))
return int(max(keyrates)*bits)
def binary_entropy(Q):
if abs(Q - 0) <= .000000001 or abs(Q - 1) <= .000000001:
return 0
try:
return -Q*log2(Q)-(1-Q)*log2(1-Q)
except ValueError:
# print("Value error!")
# print(Q)
raise RuntimeError
seed1 = "gen"
seed2 = "ran"
seed3 = "ent"
seed4 = "qkd"
PRNG_gen = None
PRNG_ran = None
PRNG_ent = None
PRNG_qkd = None
# global filt
# filt = None
def main(N, n, T, p, q, d, Pz = 1/2, Px = 1/2, glob=False, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "grid", l=None, alpha= None, het_dist = True, CAD_flag = True, balance_flag = False):
#print(N, n, T, p, q, d, Pz , Px , glob, dumb)
if T is None:
print("T=", T, "Aborting")
return -1,1
global PRNG_gen
global PRNG_ran
global PRNG_ent
global PRNG_qkd
PRNG_gen = random.Random(uuid.UUID(seed1) if type(seed1) is str else seed1)
PRNG_ran = random.Random(uuid.UUID(seed2) if type(seed2) is str else seed2)
PRNG_ent = random.Random(uuid.UUID(seed3) if type(seed3) is str else seed3)
PRNG_qkd = random.Random(uuid.UUID(seed4) if type(seed4) is str else seed4)
global prio_a
global prio_b
prio_a = prio_b = 0
global CAD
global balance
CAD = CAD_flag
balance = balance_flag
global prio_counts
prio_counts = {}
print(f"Prio counts reset to {prio_counts} in main")
print(f"Balance Flag is {balance}, Cad flag is {CAD}")
#Set Up
if p is None:
if l is None or alpha is None:
print("Error!! Need p or l and alpha")
return
else:
p = 10**(-alpha*l/10)
(G,L,P,Q,D,K,Kb) = generate_network(n,T,p,q,d,l, alpha, topog)
print(f"Lengths = {set(L[0].values())}")
print(f"Ps = {set(P[0].values())}")
print(f"Ds = {set(D[0].values())}")
print(f"Qs = {set(Q)}")
G.show_graph()
G.add_graph()
G.real_dists(L)
if finite:
K_fin = deepcopy(K)
#G.show_graph()
G.print_graph()
print(f"Trusted Nodes: {G.get_trusted()}")
#G.all_paths()
#print("Network Graph")
#G.show_graph()
#Ma in Loop
pathlength1 = 0
path_counts = {}
paths1 = 0
i = 0
channels = 0
decohered = 0
path_lengths ={}
discarded = 0
data_str = "Data for {} iterations, dim={} {}, L = {}, Q = {}, E = {}, Pz = {}, Global Info = {}, TN Type = {}"\
.format(N, n, topog, round(p,3), q, d, Pz, glob if glob else "{}, Smart = {}".format(glob, not dumb), "regular" if not simple else "simple")
print(data_str)
balance_inf = {i:{j: 0 for j in G.get_trusted()} for i in G.get_trusted()}
old_prioA = old_prioB = 0
while i < N:
# print("here1")
#if i % 1000 == 0:
# print(' {0}\r'.format("Completed {} out of {}".format(i,N)))
i+=1
if i % (N/20) == 0 :
print('|',end="")
if i == N:
print("")
# print("-------Entanglement Graph-----------")
G1 = pair_ent(G,P)
#G1.show_graph()
# print("-------Routing Ent-----------")
#G1b = deepcopy(G1)
G2 = deepcopy(G1)
Pt = R1(G, G1,L,K,balance_inf, het_dist) if glob else local_R1(G,G1,K,dumb, balance_inf, het_dist) #for two trusted nodes old global R1 is actually better.
# print("here2")
# Pt2 = R1(G, G2,K, None) if glob else local_R1(G,G1,K,dumb) #for two trusted nodes old global R1 is actually better.
Pt2 = []
Pt = sorted(Pt, key = lambda x: len(x))
Pt2 = sorted(Pt2, key = lambda x: len(x))
# print(Pt)
# print(Pt)
# print(Pt)
if (Pt or Pt2) and (prio_a > old_prioA or prio_b > old_prioB) and Pt != Pt2 :
old_prioB = prio_b
old_prioA = prio_a
# print()
# print("Pt1", ["{} - > {} len {}".format(x[0],x[-1], len(x) - 1) for x in sorted(Pt, key = lambda x: len(x))])
# print("Pt2", ["{} - > {} len {}".format(x[0],x[-1], len(x) - 1) for x in sorted(Pt2, key = lambda x: len(x))])
discarded += len(Pt)
#
if filt:
if filt == 1:
Pt = [x for x in Pt if .5*(1-(1-d)**(len(x)-1)) <=.11]
if filt == 2:
Pt = [x for x in Pt if len(x)-1 <11]
discarded -= len(Pt)
#print(Pt)
pathlength1 += sum([len(x)-1 for x in Pt])
paths1 += len(Pt)
for path in Pt:
path_lengths[len(path)-1] = path_lengths.get(len(path)-1,0) + 1
path_counts[tuple(path)] = path_counts.get(tuple(path),0) + 1
(G2, Ed, pathinf) = path_ent(G, Q, D, Pt)
channels+=len(Ed)
decohered += sum([x[-1] for x in Ed])
(G3, K, Kb, balance_inf) = attempt_QKD(G2, Ed, Pz, Px, K, Kb, pathinf, balance_inf)
# print("here3")
if finite and not simple and not i % finite_block/2:
print("Checking for post-processing")
print(K)
if max([max(x.values()) for x in K.values()]) > finite_block:
K_fin = finite_process_regular(K,Kb, K_fin, finite_block)
if finite and not simple:
K_fin = finite_process_regular(K,Kb, K_fin, finite_block, True)
#print(Kb)
new_Kb_low = {i:{j: "" for j in G.get_trusted()} for i in G.get_trusted()}
new_Kb_high = {i:{j: "" for j in G.get_trusted()} for i in G.get_trusted()}
new_K_low = {i:{j: 0 for j in G.get_trusted()} for i in G.get_trusted()}
new_K_high = {i:{j: 0 for j in G.get_trusted()} for i in G.get_trusted()}
Kb_all = deepcopy(Kb)
K_all = deepcopy(K)
for x in Kb:
for y in Kb[x]:
counter = 0
acc = 0
se = dict()
for keybit in Kb[x][y]:
counter +=1
acc += keybit[1]
if keybit[1] in se:
se[keybit[1]] +=1
else:
se[keybit[1]]=0
if counter:
#print("Average for ",x,y, "is", acc/counter)
#print("{} to {} average error rate was {}, counts were {}".format(x,y,acc/counter, se))
for keybit in Kb[x][y]:
if keybit[1] < acc/counter:
new_Kb_high[x][y]+=keybit[0]
new_K_high[x][y]+=1
else:
new_Kb_low[x][y]+=keybit[0]
new_K_low[x][y]+=1
newlist = [keybit[0] for keybit in Kb[x][y]]
Kb[x][y] = "".join(newlist)
#print("Standard Processing")
# print(K)
# (maxflow, errors, K, Kb) = R2_simple(G3, K, Kb) if simple else R2_regular(G3,K, Kb)
(maxflow, errors, K, Kb) = (0,0,{},{})
if simple:
print("Error, how to do segmenting with simple")
exit(0)
else:
#print("High Error Rate Bits")
(maxflow_low, errors_low, new_K_low, new_Kb_low) = (0,0,{},{}) #R2_regular(G3,new_K_low, new_Kb_low)
#print("Low Error Rate Bits ")
(maxflow_high, errors_high, new_K_high, new_Kb_high) = (0,0,{},{}) # R2_regular(G3,new_K_high, new_Kb_high)
print("Individual Error Rates PROC")
(maxflow_all, errors_all, K_all, Kb_all) = R2_regular_all(G3, K_all, Kb_all)
# print(maxflow_all, maxflow_low, maxflow_high, maxflow)
# print("COMPARE", maxflow_all, maxflow_low+maxflow_high, maxflow)
print(f"Balacing info")
try:
print(f" Sigma = {prio_counts['Sigma']} Delta = {prio_counts['Delta']}")
del prio_counts["Sigma"]
del prio_counts["Delta"]
except:
print("Couldn't get balancing values")
print(balance_inf)
for bal in prio_counts:
print(f" Prioritized edge {bal} {prio_counts[bal]} times or {prio_counts[bal]*100/N}%")
print("Final Stats: {} rounds resulted in {} {} key bits with {} errors with {} TNs at {}".format(i, maxflow, "secret" if not simple else "raw" , errors, len(G.trusted)-2, G.trusted))
print(" Results in {} secret key bits".format( max(0,int((1-2*binary_entropy(float(errors/maxflow)))*maxflow)) if maxflow else 0 ))
print("Stats")
print(" Total connections ", paths1)
print(" Average connections ", paths1/i)
print(" Average connection length ", pathlength1/paths1 if paths1 else 0)
print(" Total established channels", channels)
print(" Total decohered channels", decohered)
print(" Average channels", channels/i)
print(" Average decohered", decohered/channels if channels else 0)
print(" Path lengths and counts:")
# print(path_lengths)
for path in path_lengths:
print(" Length {}, Count {}, Expected E = {}".format(path, path_lengths[path], .5*(1-(1-d)**path)))
print(" Discarded {} paths".format(discarded))
try:
print(" Expected total error {} paths".format(sum([path_lengths[path]*.5*(1-(1-d)**path) for path in path_lengths])/sum([path_lengths[path] for path in path_lengths])))
except:
pass
# for k in k_errors:
# for kb in k_errors:
# if k_errors[k][kb][0]:
# try:
# print("pre- {} - > {} had {} bits and {} errors, error rate of {}".format(k, kb, k_errors[k][kb][0],k_errors[k][kb][1],k_errors[k][kb][1]/k_errors[k][kb][0]))
# except:
# print("pre- {} - > {} had {} bits and {} errors, error rate of {}".format(k, kb, k_errors[k][kb][0],k_errors[k][kb][1],0))
try:
print(" Overall had {} bits and {} errors, error rate of {}".format(maxflow, errors, errors/maxflow if maxflow else 0))
except:
print(" Overall had {} bits and {} errors, error rate of {}".format(maxflow, errors, 0))
print(" Path Information:")
total_paths = sum(path_counts.values())
new_paths = deepcopy(path_counts)
for p in path_counts:
if path_counts[p]/total_paths < .005:
del new_paths[p]
path_counts = new_paths
for p in sorted(list(path_counts.keys()), key = lambda path: (len(path), path[0], path[-1])):
print(f"Path {p} count: {path_counts[p]}")
print("")
print("Key rate without segmenting was {} with {} errors".format(maxflow/N, errors))
print("Key rate with half segmenting was {}".format("{} +{} = {}".format(maxflow_low/N, maxflow_high/N, (maxflow_low+maxflow_high)/N)))
print("Key rate with all segmenting was {}".format(maxflow_all / N))
print(maxflow_all, maxflow, maxflow_low+maxflow_high)
print("\nBEST KEY RATE WAS {}".format(max(maxflow_all, maxflow, maxflow_low+maxflow_high)/N))
return maxflow_all, errors
# print("not using pooling")
# return maxflow, errors #no pooling
import sys
import uuid
seed1 = uuid.uuid4()
seed2 = uuid.uuid4()
seed3 = uuid.uuid4()
seed4 = uuid.uuid4()
print("seed1 = \"{}\" ".format(seed1))
print("seed2 = \"{}\" ".format(seed2))
print("seed3 = \"{}\" ".format(seed3))
print("seed4 = \"{}\" ".format(seed4))
# seed1 = "54219335-ce3a-4f61-858d-44b7869a5cb4"
# seed2 = "45842154-d04d-4d61-86ff-d10f2a07d5e2"
# seed3 = "e9fb24b2-0e63-464f-bc37-8a284260a3e6"
# seed4 = "93e752b7-cf58-411b-9d64-128222b408da"
if __name__ == "__main__":
# (G,L,P,Q,D,K,Kb) = generate_network(24,[],1,1,.01,1, .15, "bwheel")
# print(f"Lengths = {set(L[0].values())}")
# print(f"Ps = {set(P[0].values())}")
# print(f"Ds = {set(D[0].values())}")
# print(f"Qs = {set(Q)}")
# x1= main(1000, 12, [0,12,6], None, .85, .03, Pz = 1/2, Px = 1/2, glob=True, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "bwheel", l=30, alpha= .15)
# x2= main(1000, 12, [0,12,6], None, .85, .03, Pz = 1/2, Px = 1/2, glob=True, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "bwheel", l=30, alpha= .15, het_dist = False)
# x3= main(1000, 12, [0,3,9,6], None, 1, .03, Pz = 1/2, Px = 1/2, glob=True, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "bwheel", l=30, alpha= .15)
# x4= main(1000, 12, [0,3,9,6], None, 1, .03, Pz = 1/2, Px = 1/2, glob=True, dumb=False, simple = False , finite = False, finite_block = 1e5, topog = "bwheel", l=30, alpha= .15, het_dist = False)
# print("Central TN")
# print(x1,x2)
# print("Side TNs")
# print(x3,x4)
# balance = True
# x1 = main(N=100, n=5, T=[0,12,24], p=1, q=1, d=0, Pz = 1/2, Px = 1/2, glob=True, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "grid", l=None, alpha= None, het_dist = False)
# balance = True
# x2 = main(N=1e2, n=9, T=[10,70], p=.96, q=.85, d=.02, Pz = 1/2, Px = 1/2, glob=True, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "grid", l=None, alpha= None, het_dist = False, balance_flag = balance)
balance = True
x2 = main(N=1e4, n=9, T=[10, 20, 49,70], p=.96, q=.85, d=.02, Pz = 1/2, Px = 1/2, glob=True, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "grid", l=None, alpha= None, het_dist = False, balance_flag = balance)
# G = generate_network(9,[10,20,49,70], .96, .85, 0, None, None , shape = "grid")[0]
# print(G)
# G.add_graph()
# G.all_paths()
# balance_info = {10: {10: 0, 20: 5549.631493626309, 49: 25.056440688284056, 70: 0.13029864370309951}, 20: {10: 5549.63149362631, 20: 0, 49: 1977.9240052514697, 70: 0.24913228325294767}, 49: {10: 25.056440688283814, 20: 1977.9240052514183, 49: 0, 70: 2018.4298145493901}, 70: {10: 0.13029864370320943, 20: 0.24913228325195735, 49: 2018.4298145493242, 70: 0}}
# print(check_and_determine_balancing(balance_info, G))
# print(prio_counts)
# balance = False
# x2 = main(N=1e4, n=9, T=[10, 20, 49,70], p=.96, q=.85, d=.02, Pz = 1/2, Px = 1/2, glob=True, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "grid", l=None, alpha= None, het_dist = False, balance_flag = balance)
# print(x1)
# print(x2)
# balance = True
# x1 = main(N=100, n=7, T=[0,20,48], p=1, q=1, d=0, Pz = 1/2, Px = 1/2, glob=False, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "grid", l=None, alpha= None, het_dist = False)
# balance = False
# x2 = main(N=100, n=13, T=[0,168], p=1, q=1, d=0, Pz = 1/2, Px = 1/2, glob=False, dumb=False, simple = False, finite = False, finite_block = 1e5, topog = "grid", l=None, alpha= None, het_dist = False, CAD_flag = True)
# print(x1)
# print(x2)
pass