Permalink
Cannot retrieve contributors at this time
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/tempbalancescratch.py
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
96 lines (66 sloc)
2.72 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#balance_scratch adaptive_balancing R1 | |
#global | |
from Simulator import * | |
def check_and_determine_balancing(balance_info, Graph): | |
#create graph from balance_info, call R2 on it, for each edge do DFS from A to B based on updated balances | |
pass | |
# Do we balance? | |
# right now we balance if max edge is 1+ sigma times min edge, but this will usually be true | |
balance_flag = (1+sigma) * min(balance_info.values()) < max(balance_info.values()) | |
# if we balance, find constraining edges, and then most constraining edges | |
if not balance_flag: | |
return False | |
bottlenecks = find_bottleneck_edges(balance_info, graph._Alice, graph._Bob) | |
if not bottlenecks: | |
return False | |
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]) | |
if start_nodes: | |
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 balance_info: | |
for j in balance_info[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: | |
bottlenecks.append((i,j)) | |
print("Got bottleneck edges: {}".format(bottlenecks)) | |
return bottlenecks | |
balance_info = { | |
0: {0: 0 , 1: 100, 2: 100, 3: 100 } , | |
1: {0: 0 , 1:0 , 2:0 , 3:120 } , | |
2: {0: 0 , 1:0 , 2:0 , 3: 100} , | |
3: {0: 0, 1: 0, 2: 0, 3:0 } | |
} | |
print(balance_info) | |
print(find_bottleneck_edges(balance_info, 0,3)) | |