investigating a hypothesis about graphs

ldbe.py

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)