Graphs.py

from __future__ import print_function
import random
import sys
from copy import deepcopy
from math import log2
import math
import networkx as nx
# import Simulator
try: 
	#server doesn't have
	import matplotlib.pyplot as plt
except:
	pass
import uuid


def all_simple_paths_breakdown(G, source, sink, inc):
#     results = {i: [] for i in range(inc+1)}
	results = {}
	dist = len(nx.shortest_path(G,source, sink))
	for path in nx.all_simple_paths(G, source, sink, cutoff=dist+inc-1):
#         print(path, len(path)-dist)
		if not len(path)-1 in results:
			results[len(path)-1] = []
		results[len(path)-1].append(path)
	return results
# res = all_simple_paths_breakdown(G.G, 10,1, 1)
# for l in res:
#     print(l, res[l])

def disjoint_paths(source, sink, paths, trusted, used_edges):
	trusted = set(trusted)
	P = nx.Graph()
	for path in paths:
		if not set(path[1:-1]).intersection(trusted):
			edges = [(path[i], path[i+1]) for i in range(len(path)-1)]
			if not set(edges).intersection(used_edges):
#                 print("      ", path)
				for edge in edges:
					P.add_edge(edge[0], edge[1], capacity = 1)
    
	max_flow, flow_dict = nx.maximum_flow(P, source, sink) if (source in P.nodes and sink in P.nodes) else (0, [])
	used_edges = []
	for edge0 in flow_dict:
		for edge1 in flow_dict[edge0]:
			if flow_dict[edge0][edge1]:
#                 print(f"{edge0} -> {edge1}: {flow_dict[edge0][edge1]}")
				used_edges.append((edge0, edge1))
	return (max_flow, used_edges)

def count_disjoint_paths_shortest_plus(G, source, sink, trusted, inc):
	# print(G, source, sink, trusted, inc)
#     print("in")
	paths = all_simple_paths_breakdown(G, source,sink, inc)
	results = {}
	used_edges = set()
	for l in sorted(paths.keys()):
		count, new_edges = disjoint_paths(source, sink, paths[l], trusted, used_edges)
#         print("  ", l, count, new_edges)
		used_edges = used_edges.union(new_edges)
		results[l] = count

	return results




class Graph:
	def __init__(self, nodes, edges, weight = lambda u,v: 1, RAND = None, graph = False):
		self._nodes = tuple([int(node) for node in nodes])
		self._edges = set([ (min(e), max(e)) for e in edges])
		self._weight = False #never use it and disallows pickling
		self.G = graph 
		self._paths = None
		self._Alice = None
		self._Bob = None
		self._realpaths = None
		self._RNG = RAND if RAND else True
		self.TN_graph = False
		if not RAND:
			print(self._RNG)
			print(RAND)
			raise RuntimeError("Crashed!") #random.random(uuid.uuid4())
	
	# def num_edge_disjoint_shortest_paths(self, source, sink):
	# 	P = nx.Graph()
	# 	for path in nx.all_shortest_paths(self.G,source, sink):
	# 		if not set(path[1:-1]).intersection(set(self.trusted)):
	# 			for i in range(len(path)-1):
	# 				P.add_edge(path[i], path[i+1])

	# 	return nx.edge_connectivity(P, source, sink) if (source in P.nodes and sink in P.nodes) else 0
	def TN_balance_graph(self, dec, loss, bsm, depth = 5):
		if self.TN_graph:
			if dec == self.dec and self.loss == loss and self.bsm == bsm:
				return self.TN_graph
		self.add_graph()
		self.dec = dec
		self.loss = loss
		self.bsm = bsm

		T = nx.Graph()
		print("Creating TN Balancing Graph with depth", depth)
	#     print("constructing TN graph")
	#     print("dist, num, qber, keyrate, cap")
		for node1 in self.trusted:
			for node2 in self.trusted:
				caps = []
				if node1 < node2:
					dist_count_dict = count_disjoint_paths_shortest_plus(self.G, node1, node2, self.trusted, depth)
					for dist in dist_count_dict:
						num_disj= dist_count_dict[dist]
						qber = (1-(1-dec)**dist)/2 # this assumes we know the dec, which might be unrelaistic
						keyrate = cad_EC(qber, 100000, True)/100000 #could observe keyrate from balance info but might get statistical error early potentially cascading
						caps.append(num_disj * keyrate * (loss**dist) * (bsm**(dist-1)))

					T.add_edge(node1,node2, cap = sum(caps))
		self.TN_graph = T	
		return T
	# def TN_balance_graph(self, dec):

	# 	if self.TN_graph:
	# 		return self.TN_graph
	# 	self.add_graph()
	# 	T = nx.Graph()

	# 	for node1 in self.trusted:
	# 		for node2 in self.trusted:
	# 			if node1 < node2:
	# 				num_disj_shorts = self.num_edge_disjoint_shortest_paths(node1, node2)
	# 				dist = len(nx.shortest_path(self.G, node1,node2))-1
	# 				qber = (1-(1-dec)**dist)/2 # this assumes we know the dec, which might be unrelaistic
	# 				keyrate = cad_EC(qber, 10000000, True)/10000000 #could observe keyrate from balance info but might get statistical error early potentially cascading
	# 				cap = num_disj_shorts * keyrate

	# 				T.add_edge(node1,node2, cap = cap)
	# 	self.TN_graph = T	
	# 	return T

	def add_graph(self):
		if self.G:
			return
		self.G = nx.Graph()
		for edge in self.get_edges():
			self.G.add_edge(min(edge), max(edge))

	def print_graph(self):
		# print("Vertices: {}".format(self.get_nodes()))
		# print("Edges: {}".format([ (x, self.weight(x[0],x[1])) for x in self.get_edges()]))
		print("Alice {}, Bob {}".format(self._Alice, self._Bob))

	def view_graph(self, dummy_arg = None):
		self.show_graph()
	def get_edges(self):
		return self._edges

	def weight(self, u,v):
		return self._weight(u,v)

	def get_nodes(self):
		return self._nodes

	def get_edge(self, u, v):
		edge = (min(u,v), max(u,v))
		if edge in self.get_edges():
			return edge
		return False

	def set_edges(self, new_edges):
		self._edges = set(new_edges)
		# self.G.edges = []
		if self.G:
			# for edge in self.get_edges():
			# 	self.G.add_edge(edge[0], edge[1])
			self.G = nx.Graph()
			for edge in self.get_edges():
				self.G.add_edge(min(edge), max(edge))

	def set_nodes(self, new_nodes):
		self._nodes = tuple(new_nodes)

	def get_neighbors(self, u):
		return set([v for v in self.get_nodes() if self.get_edge(u,v)])

	def remove_edge(self, u, v):
		e = self.get_edge(u,v)
		# print(f"edge to remove {e=}, {(u,v) in self._edges}")
		# print(self._edges)
		if e:
			self.get_edges().remove((e[0],e[1]))
			if self.G:
				# print("removing from self.G")
				self.G.remove_edge(e[0], e[1])
		

	def add_edge(self, u, v):
		e = self.get_edge(u,v)
		if not e:
			self.get_edges().add((u,v))
			if self.G:
				self.G.add_edge(e[0], e[1])

	def all_shortest_paths(self, source, dest):
		if not self.shortest_path(source, dest):
			return []
		# print(f"shortest paths b/w {source} and {dest}", [p for p in nx.all_shortest_paths(self.G, source, dest)])
		return [p for p in nx.all_shortest_paths(self.G, source, dest, weight="perturbed_weight")]

	def get_random_shortest_path(self, source, dest):
		for u,v in self.G.edges:
			self.G[u][v]["perturbed_weight"] = 1+self._RNG.random()/1000
		return self.shortest_path(source,dest)

	def shortest_path(self, source, dest):
		G = self.G
		# print(G)
		try:
			return nx.shortest_path(G,source, dest, weight="perturbed_weight")
		except nx.exception.NodeNotFound:
			return ()
		except nx.exception.NetworkXNoPath:
			return ()

		# while Q:
		# 	u = None
		# 	udist = float('Inf')
		# 	for key in Q:
		# 		if dist[key] < udist:
		# 			u = key
		# 			udist = dist[key]
		# 	if u is None:
		# 		return () #no path
		# 	Q.remove(u)

		# 	for v in Q:
		# 		edge = self.get_edge(u,v)
		# 		if edge:
		# 			alt = dist[u] + self.weight(edge[0],edge[1])
		# 			if alt < dist[v]:
		# 				dist[v] = alt + .000 if u!= source and abs(u-v) != abs(u - prev[u]) else 0
		# 				prev[v] = u


		# 	if u == dest:
		# 		S = []
		# 		if prev[u] is not None or u == source:
		# 			while u is not None:
		# 				S = [u]+S
		# 				u = prev[u]
		# 			#print(S)
		# 			return S 
		# 		else:
		# 			return () 
		# return ()

	def all_paths(self):
		if self._paths:
			return self._paths
		paths = {}
		for u in self.get_nodes():
			for v in self.get_nodes():
				path = self.shortest_path(u,v)
				if u in paths:
					paths[u][v] = len(path) -1 #(len(path)-1, path)
				else:
					paths[u] = {v:len(path) -1} #(len(path)-1, path)}
		self._paths = paths
		return paths

	def real_dists(self, L):
		if self._realpaths:
			return self._realpaths
		paths = {}
		for u in self.get_nodes():
			for v in self.get_nodes():
				path = self.shortest_path(u,v)
				d = 0
				for i in range(len(path)-1):
					d+=L[i][i+1]
				if u in paths:
					paths[u][v] =d #(len(path)-1, path)
				else:
					paths[u] = {v:d} #(len(path)-1, path)}
		self._realpaths = paths
		return paths

class RingGraph(Graph):
	def __init__(self, n, T, weight=lambda u,v: 1, Alice = None, Bob = None,  RAND=None):
		self._n = n
		# print(f"GRAPH HAS NODES {n}")
		T = list(T)
		vert = tuple([i for i in range(0,n)])
		edgel = []
		for i in vert:
			if (i+1) % n  in vert:
				edgel.append((i, (i+1) % n))
			# if (i+2) % n in vert:
				# edgel.append((i, (i+2) % n))

		super().__init__(vert, edgel, RAND=RAND)
		if not Alice or not Bob:
			self._Alice = 0
			self._Bob = math.floor(n/2)
		else:
			self._Alice = Alice
			self._Bob = Bob
		if self._Alice in T:
			T.remove(self._Alice)
			T.remove(self._Bob)
		T = [self._Alice] + T + [self._Bob] # make sure that T is always trusted Nodes between Alice and Bob
		self.trusted = tuple(sorted([int(t) for t in set(T)]))
		# print(f"GRAPH HAS NODES {vert}")

	def show_graph(self):
		self.print_graph()

	def get_dim(self):
		return self._n
	def get_trusted(self):
		return self.trusted

class BraidedRingGraph(Graph):
	def __init__(self, n, T, weight=lambda u,v: 1, Alice = None, Bob = None, RAND=None):
		self._n = n
		# print(f"GRAPH HAS NODES {n}")
		T = list(T)
		vert = tuple([i for i in range(0,n)])
		edgel = []
		for i in vert:
			if (i+1) % n  in vert:
				edgel.append((i, (i+1) % n))
			if (i+2) % n in vert:
				edgel.append((i, (i+2) % n))

		super().__init__(vert, edgel, RAND=RAND)
		if not Alice or not Bob:
			self._Alice = 0
			self._Bob = math.floor(n/2)
		else:
			self._Alice = Alice
			self._Bob = Bob
			
		if self._Alice in T:
			T.remove(self._Alice)
			T.remove(self._Bob)
		T = [self._Alice] + T + [self._Bob] # make sure that T is always trusted Nodes between Alice and Bob
		self.trusted = tuple(sorted([int(t) for t in set(T)]))

	def show_graph(self):
		self.print_graph()

	def get_dim(self):
		return self._n
	def get_trusted(self):
		return self.trusted

class WheelGraph(Graph):
	def __init__(self, n, T, weight=lambda u,v: 1, Alice = None, Bob = None, RAND=None):
		self._n = n
		T = list(T)
		vert = [i for i in range(0,n)]
		edgel = []
		for i in vert:
			if (i+1) % n  in vert:
				edgel.append((i, (i+1) % n))
				edgel.append((i, n))
		vert.append(n)
		vert = tuple(vert)
		
		super().__init__(vert, edgel, RAND=RAND)
		if not Alice or not Bob:
			self._Alice = 0
			self._Bob = int(n/2)
		else:
			self._Alice  = Alice
			self._Bob  = Bob
		if self._Alice in T:
			T.remove(self._Alice)
			T.remove(self._Bob)
		T = [self._Alice] + T + [self._Bob]
		self.trusted = tuple(sorted([int(t) for t in set(T)]))

	def show_graph(self):
		self.print_graph()

	def get_dim(self):
		return self._n
	def get_trusted(self):
		return self.trusted

class BraidedWheelGraph(Graph):
	def __init__(self, n, T, weight=lambda u,v: 1, Alice = None, Bob = None, RAND=None):
		self._n = n
		T = list(T)
		vert = [i for i in range(0,n)]
		edgel = []
		for i in vert:
			if (i+1) % n  in vert:
				edgel.append((i, (i+1) % n))
				edgel.append((i, (i+2) % n))
				edgel.append((i, n))
		vert.append(n)
		vert = tuple(vert)
		
		super().__init__(vert, edgel, RAND=RAND)
		if not Alice or not Bob:
			self._Alice = 0
			self._Bob = int(n/2)
		if self._Alice in T:
			T.remove(self._Alice)
			T.remove(self._Bob)
		T = [self._Alice] + T + [self._Bob]
		self.trusted = tuple(sorted([int(t) for t in set(T)]))

	def show_graph(self):
		self.print_graph()

	def get_dim(self):
		return self._n
	def get_trusted(self):
		return self.trusted

class GridGraph(Graph):
	def __init__(self, n, T, weight=lambda u,v: 1, Alice = None, Bob = None, RAND=None):
		self._n = n
		T = list(T)
		vert = tuple([i for i in range(0,n*n)])
		edgel = []
		for i in vert:
			if i+1 in vert and (i+1) % n  !=0:
				edgel.append((i, i+1))
			if i+n in vert:
				edgel.append((i, i+n))
		
		super().__init__(vert, edgel, RAND=RAND)
		if not Alice or not Bob:
			Alice = min(T)
			Bob = max(T)  
		self._Alice  = Alice
		self._Bob  = Bob
		if self._Alice in T:
			T.remove(self._Alice)
			T.remove(self._Bob)
		T = [self._Alice] + T + [self._Bob]
		self.trusted = tuple(sorted([int(t) for t in set(T)]))

	def show_graph(self):
		print("")
		n = self._n
		for row in range(n):
			for nodes_or_edge in range(3):
				for col in range(n):
					cur_node = col + row*n 
					if nodes_or_edge == 0:
						#print(cur_node, end = "")
						print(" T " if cur_node in self.get_trusted() else "%3d" % cur_node, end = "")
						if self.get_edge(cur_node, cur_node + 1):
							print(" -- ", end="")
						else:
							print("    ", end="") 
					else:
						if self.get_edge(cur_node, cur_node+n):
							print (" | ",end="")
						else:
							pass
							print(" "*max(len(str(cur_node)),len(str(cur_node+n))), end="")
						print("    ",end="")
				
				print("")

	def get_dim(self):
		return self._n
	def get_trusted(self):
		return self.trusted


class RandomGraph(Graph):
	def __init__(self, n, T, radius, weight=lambda u,v: 1, Alice = None, Bob = None, RAND=None, style = "random"):
		numN = n


		self._n = numN

		for i in range(50):
			self.G=nx.random_geometric_graph(numN, radius, dim=2, seed=RAND)
			if nx.is_connected(self.G):
				break
		
		self.radius = radius
		# print(self.G, f"max edges {numN*( numN-1)//2}")

		nodes = list(self.G.nodes)
		edges = list(self.G.edges)
		super().__init__(nodes, edges, RAND=RAND, graph = self.G)
		self.add_graph()

		if Alice is None or Bob is None:
			print("NOT Getting new AB")
			# Alice, Bob = self.select_AB()
			Alice, Bob = 0, n-1
		self._Alice  = Alice
		self._Bob  = Bob
		# print(A,B)
		if type(T) is int:
			T = self.selectT(T, style)
		else:
			T = list(T)
		# print(T, self._Alice, self._Bob)
		if self._Alice in T:
			T.remove(self._Alice)
			T.remove(self._Bob)
		# print(self.trusted)
		T = [self._Alice] + T + [self._Bob]
		# print("t,",T)
		self.trusted = tuple([int(t) for t in T])
		# print(self.trusted)
	
	

	def selectT(self, numT, style):
		pos = nx.get_node_attributes(self.G, 'pos')
		Alice_pos = pos[self._Alice]
		Bob_pos = pos[self._Bob]
		
		def get_alice_quadrant(self):
			alice_quad = []
			for node in self.G.nodes:
				if abs(Alice_pos[0]-pos[node][0]) < abs(Bob_pos[0]-pos[node][0]):
					if abs(Alice_pos[1]-pos[node][1]) < abs(Bob_pos[1]-pos[node][1]): 
						alice_quad.append(node)

			return list(set(alice_quad).difference({self._Alice, self._Bob}))

		
		if style == "random":
			return self._RNG.sample(list(set(self.G.nodes).difference({self._Alice, self._Bob})), numT)
		elif style == "random-quadrant-Alice":
			return self._RNG.sample(list(set(get_alice_quadrant(self)).difference({self._Alice, self._Bob})), numT)
		elif style == "central":
			trusted = []
			for i in range(numT):
				ncenter, _ = min(pos.items(), key=lambda node: ((node[1][0]-0.5)**2+(node[1][1]-0.5)**2) if not node[0] in trusted+[self._Alice, self._Bob] else 1000)
				trusted.append(ncenter)
			return trusted
		elif style == "notDiag-Alice":
		# 	trusted = []
		# 	ncenter, _ = min(pos.items(), key=lambda node: ((node[1][0]-0.5)**2+(node[1][1]-0.5)**2) if not node[0] in trusted+[self._Alice, self._Bob] else 1000)
		# 	trusted.append(ncenter)
		# 	newcentroid = (pos[self._Alice][0] + pos[ncenter][0]/2,pos[self._Alice][1] + pos[ncenter][1]/2)
		# 	ncenter, _ = min(pos.items(), key=lambda node: ((node[1][0]-newcentroid[0])**2+(node[1][1]-newcentroid[1])**2) if not node[0] in trusted+[self._Alice, self._Bob] else 1000)
		# 	trusted.append(ncenter)
		# 	return trusted
			trusted = [self.find_central(list(set(get_alice_quadrant(self)).difference({self._Alice, self._Bob})))]
			center, _ = min(pos.items(), key=lambda node: ((node[1][0]-0.5)**2+(node[1][1]-0.5)**2) if not node[0] in trusted+[self._Alice, self._Bob] else 1000)

			return [trusted[0][0], center]


		else:
			raise RuntimeError(f"Invalid style for trusted nodes in grandom graph: {style}")


	def select_AB(self):
		d = nx.eccentricity(self.G)
		diameter = nx.diameter(self.G)
		# print(f"Diameter: {diameter}")

		ecc_nodes = [x for x in d if  d[x] == diameter-1]
		elt1 = self._RNG.sample(ecc_nodes, 1)[0]
		elt2 = self._RNG.sample(list(nx.descendants_at_distance(self.G, elt1, diameter-1)),1)[0]
		return elt1, elt2

	def show_graph(self):

		print(self.G, f"max edges {self._n*( self._n-1)//2}")

		return
	def view_graph(self,save_file = False):
		print(f"{self._Alice=}, {self._Bob=}, {self.trusted=} ")


		G = self.G
		
		pos = nx.get_node_attributes(G, 'pos')
	
		plt.figure(figsize=(8, 8))
		T = self.G.subgraph(self.trusted)

		node_color = []#dict({node:"" for node in G.nodes})
		labels_dict = {node:node for node in G.nodes}
		for node in labels_dict:
			if node in self.get_trusted():
				if node == self._Alice:
					# labels_dict[node]= "A"
					node_color.append("white")
				elif node == self._Bob:
					# labels_dict[node]= "B"
					node_color.append("white")
				else:
					# labels_dict[node]= f"$T_{self.get_trusted().index(node)}$"
					node_color.append("#02bfc0")
			else:
				node_color.append("#02ff00")

		# print(labels_dict)
		nx.draw_networkx_edges(G, pos, alpha=0.4)
		# nx.draw_networkx_nodes(H, pos, node_size=300, node_color=node_color,
		                       # cmap=plt.get_cmap('Reds_r'), edgecolors = "black")
		nx.draw_networkx_nodes(G, pos, node_color = node_color, node_size=300,  edgecolors = "black")
		nx.draw_networkx_nodes(T, pos, node_color = [node_color[node] for node in T.nodes if node in self.trusted], node_size=300,  edgecolors = "black")


		nx.draw_networkx_labels(G, pos, labels = labels_dict, 
		                     font_size=12, font_color='black', font_family='sans-serif', 
		                     font_weight='normal', alpha=None, bbox=None, horizontalalignment='center', 
		                     verticalalignment='center', ax=None, clip_on=True)

		plt.xlim(-0.05, 1.05)
		plt.ylim(-0.05, 1.05)
		plt.axis('off')
		if save_file:
			plt.savefig(save_file+".pdf", format="pdf")
		# plt.savefig('random_geometric_graph.png')
		else:
			plt.show()

	def find_centroid(self, points):
		Xavg = sum([point[0] for point in points])/len(points)
		Yavg = sum([point[1] for point in points])/len(points)

		return Xavg, Yavg

	def find_central(self, nodes):
		pos = nx.get_node_attributes(self.G, 'pos')

		centroid = self.find_centroid([pos[node] for node in nodes])
		return min(pos.items(), key=lambda node: (node[1][0]-centroid[0])**2+(node[1][1]-centroid[1])**2)

	def get_dim(self):
		return self._n
	def get_trusted(self):
		return self.trusted

	def draw_flow_network(self):
		print(f"{self._Alice=}, {self._Bob=}, {self.trusted=} ")


		G = self.G
		
		pos = nx.get_node_attributes(G, 'pos')
	
		plt.figure(figsize=(8, 8))
		T = nx.Graph(self.G.subgraph(self.trusted))
		for node in T.nodes:
			for node2 in T.nodes:
				if node != node2:
					T.add_edge(node,node2, data = {"dis":len(nx.shortest_path(G, node,node2))-1, "num": len([x for x in nx.all_shortest_paths(G, node, node2)])})
		edge_labels = {}
		for edge in T.edges:
			edge_labels[edge] = f"d:{T[edge[0]][edge[1]]['data']['dis']}, n:{T[edge[0]][edge[1]]['data']['num']}"

			node1,node2 = edge
			print(f"{node1}->{node2}: dist = {len(nx.shortest_path(G, node1,node2))-1}, num_shortest = {len([x for x in nx.all_shortest_paths(G, node1,node2)])} ")
		node_color = []#dict({node:"" for node in G.nodes})
		labels_dict = {node:node for node in G.nodes if node in self.trusted}
		for node in G.nodes:
			if node in self.get_trusted():
				if node == self._Alice:
					# labels_dict[node]= "A"
					node_color.append("white")
				elif node == self._Bob:
					# labels_dict[node]= "B"
					node_color.append("white")
				else:
					# labels_dict[node]= f"$T_{self.get_trusted().index(node)}$"
					node_color.append("#02bfc0")
			else:
				node_color.append("#02ff00")

		# print(labels_dict)
		nx.draw_networkx_edges(T, pos, alpha=0.4)
		# nx.draw_networkx_nodes(H, pos, node_size=300, node_color=node_color,
		                       # cmap=plt.get_cmap('Reds_r'), edgecolors = "black")
		nx.draw_networkx_nodes(T, pos, node_color = [node_color[node] for node in T.nodes if node in self.trusted], node_size=300,  edgecolors = "black")


		nx.draw_networkx_labels(T, pos, labels = labels_dict, 
		                     font_size=12, font_color='black', font_family='sans-serif', 
		                     font_weight='normal', alpha=None, bbox=None, horizontalalignment='center', 
		                     verticalalignment='center', ax=None, clip_on=True)

		nx.draw_networkx_edge_labels(T,pos, edge_labels, rotate=False)

		plt.xlim(-0.05, 1.05)
		plt.ylim(-0.05, 1.05)
		plt.axis('off')
		# plt.savefig('random_geometric_graph.png')
		plt.show()


if __name__ == "__main__":
	Gr= RandomGraph(n=50, T=2, radius=.25, RAND=random.Random(uuid.uuid4()), style = "central")
	# Gr.view_graph()

	print(len(Gr.G.nodes))
	Gr.draw_flow_network()
	print(Gr._weight)
	print(Gr.weight)
	# pathsgen = nx.all_shortest_paths(Gr.G, Gr._Alice, Gr._Bob)
	# tn_paths = []
	# paths = []
	# # for p in pathsgen:
	# # 	# if False not in set([Gr.trusted[i] in p for i in range(1, len(Gr.trusted)-1)]):
	# # 	if True in set([Gr.trusted[i] in p for i in range(1, len(Gr.trusted)-1)]):
	# # 		tn_paths.append(p)
	# # 	paths.append(p) 
	# # print(len(paths), len(tn_paths))

	# # Gr.G = nx.Graph()
	# # for node in Gr.get_nodes():
	# # 	Gr.G.add_node(node)
	# # for p in tn_paths:
	# # 	for idx in range(len(p)-1):
	# # 		Gr.G.add_edge(p[idx], p[idx+1])
	# Gr.view_graph()


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, CAD_flag):
	if not CAD_flag:
		return int(max(0,1-2*binary_entropy(noise))*bits)
	# print("			Doing CAD on noise {} with {} bits". format(noise, bits))
	maxcad = 20 if CAD_flag 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 ValueError