Skip to content

Instantly share code, notes, and snippets.

@bakkot
Created October 15, 2015 09:10
Show Gist options
  • Save bakkot/e58f1463c0ca1865afc7 to your computer and use it in GitHub Desktop.
Save bakkot/e58f1463c0ca1865afc7 to your computer and use it in GitHub Desktop.
investigating a hypothesis about graphs
import networkx as nx
from collections import deque
import random
random.seed(42) # determinism!
def unique(l):
return len(l) == len(set(l))
def canonical(path): # path is a tuple. should also ensure sub-cycles are canonized, really, but fuck it
# picks the minimum-valued starting point.
u = path[0][0]
v = path[-1][1]
if u < v:
return path
if u > v:
return tuple( (b, a) for (a,b) in reversed(path) ) # reverse path
if u == v: # cycle. also pick direction which minimizes second point.
m = min(a for (a,b) in path)
path = list(path)
while path[0][0] != m:
path = path[-1:] + path[:-1]
if path[0][1] > path[-1][0]:
return tuple( (b, a) for (a,b) in reversed(path) )
else:
return tuple(path)
# path to set of paths derivable from it by adding an edge
def extend(path, G): # path is a tuple
path = list(path)
extensions = set()
v = path[-1][1]
neighbors = [n for n in G.neighbors(v) if (v, n) not in path and (n, v) not in path]
for n in neighbors:
extensions.add(canonical(tuple(path + [(v,n)])))
u = path[0][0]
neighbors = [n for n in G.neighbors(u) if (n, u) not in path and (u, n) not in path]
for n in neighbors:
extensions.add(canonical(tuple([(n, u)] + path)))
if u == v: # ie, path is a cycle
for i in range(len(path)):
path = path[-1:] + path[:-1]
u = path[0][0]
neighbors = [n for n in G.neighbors(u) if (n, u) not in path and (u, n) not in path]
for n in neighbors:
extensions.add(canonical(tuple([(n, u)] + path)))
return extensions
def maxPaths(G): # under sub-path definition
maxPaths = set()
candidates = set( (e,) for e in G.edges())
while len(candidates) > 0:
path = candidates.pop()
extensions = extend(path, G)
if len(extensions) == 0: # i.e., maximal
maxPaths.add(path)
else:
for path in extensions:
if path not in maxPaths:
candidates.add(path)
return maxPaths
def maxSubsetPaths(G):
paths = maxPaths(G)
sets = [(i, frozenset(frozenset(e) for e in p)) for (i,p) in enumerate(paths)]
removed = set()
def subsumed(p,i):
p = frozenset(frozenset(e) for e in p)
for j, s in sets:
if i != j and j not in removed and p <= s:
return True
return False
for (i,p) in enumerate(paths):
if subsumed(p,i):
removed.add(i)
return [p for (i,p) in enumerate(paths) if i not in removed]
def findAndRemoveMaximalPath(G, show = False):
if G.size() == 0:
return G
removed = random.choice(maxSubsetPaths(G))
if show: print(removed)
G.remove_edges_from(removed)
def test(G, i, seed, show = False):
Gp = G.copy()
Gpp = G.copy()
# nx.write_dot(Gpp, 'ldbe.gv')
count = 0
while G.size() != 0:
findAndRemoveMaximalPath(G, show)
count += 1
if show: print('--')
while Gp.size() != 0:
findAndRemoveMaximalPath(Gp, show)
count -= 1
if count != 0:
if not show: print(count, 'i = ' + str(i), 'seed = ' + str(seed))
nx.write_dot(Gpp, 'ldbe.gv')
# random.seed(440007)
# G = nx.fast_gnp_random_graph(7, 0.5)
# test(G, 0, 0, True)
# exit(0)
for s in range(10000):
if s % 100 == 0: print(s)
for i in range(6, 9):
seed = s*1000+i
random.seed(seed)
test(nx.fast_gnp_random_graph(i, 0.5), i, seed)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment