Permalink
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/Graphs.py
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
…5 seconds/500 iterations to 15 seconds per 500 iteratins. did this by modifing local_R1 to be more clever and not do all_paths every single iteration, and instead stored all pathsat beginning and copy values back from it when needed
352 lines (307 sloc)
8.55 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
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 | |
class Graph: | |
def __init__(self, nodes, edges, weight = lambda u,v: 1, RAND = None): | |
self._nodes = tuple([int(node) for node in nodes]) | |
self._edges = set([ (min(e), max(e)) for e in edges]) | |
self._weight = weight | |
self.G = False | |
self._paths = None | |
self._Alice = None | |
self._Bob = None | |
self._realpaths = None | |
self._RNG = RAND if RAND else True | |
if not RAND: | |
print(self._RNG) | |
print(RAND) | |
raise RuntimeError("Crashed!") #random.random(uuid.uuid4()) | |
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 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) | |
if self.G: | |
for edge in self.get_edges(): | |
self.G.add_edge(edge[0], edge[1]) | |
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) | |
if e: | |
self.get_edges().remove((e[0],e[1])) | |
if 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 | |
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 |