Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

Generating graphs

By: JimboBimbo on Oct 12th, 2012  |  syntax: Python  |  size: 3.83 KB  |  hits: 46  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. ##########################
  2. ####
  3. ####  Helper functions
  4. ####
  5. ##########################
  6.  
  7. import copy
  8.  
  9. ## Returns the input list with the input value removed
  10.  
  11. def lf(lst,num):
  12.     lst.remove(num)
  13.     return lst
  14.    
  15. ## Returns a list with all instances of target replaced with new    
  16.    
  17. def lr(l,target,new):
  18.     ll = []
  19.     for i in l:
  20.         cl = []
  21.         for j in i:
  22.             if j == target:
  23.                 cl.append(new)
  24.             else:
  25.                 cl.append(j)
  26.         ll.append(cl)
  27.     return ll
  28.    
  29. ## Checks if every value appears exactly twice in a list
  30.  
  31. def checkl(l):
  32.     a = max(flatten(l))
  33.     for i in range(1,a+1):
  34.         if len(filter(lambda z: z[0] == i,l)) == 1 and len(filter(lambda z: z[1] == i,l)) == 1:
  35.             continue
  36.         else:
  37.             return False
  38.     return True
  39.  
  40. ## Gives the degree of the vertex in the graph
  41.  
  42. def deg(g,v):
  43.     a = len(g[v]) + len(filter(lambda x: x == v, flatten(g.values())))
  44.     return a
  45.  
  46. ## Creates a Mathematica graph
  47.    
  48. def tomg(g):
  49.     s = "GraphPlot[{"
  50.     for i in g.keys():
  51.         for j in g[i]:
  52.             s += "%g->%g,"%(i,j)
  53.     s = s[:-1]
  54.     s += "}]"
  55.     return s
  56.    
  57. ## Checks for graph isomorphism
  58. ## m is number of vertices
  59.  
  60. def isog(g1,g2,m):
  61.     lg1t = []
  62.     lg1 = []
  63.     for i in g1.keys():
  64.         for j in g1[i]:
  65.             lg1t.append([i,j])
  66.     for t in lg1t:
  67.         t.sort()
  68.         lg1.append(t)
  69.     lg1.sort()
  70.     lg2t = []
  71.     lg2 = []
  72.     for i in g2.keys():
  73.         for j in g2[i]:
  74.             lg2t.append([i,j])
  75.     for t in lg2t:
  76.         t.sort()
  77.         lg2.append(t)
  78.     lg2.sort()
  79.     ##Checks if same edges, same vertices
  80.     if lg1 == lg2:
  81.         return True
  82.     ##Checks if permutations of vertices
  83.     l1 = Arrangements(range(1,m+1)+range(1,m+1),2).list()
  84.     l2 = Combinations(l1,m).list()
  85.     l3 = filter(lambda y: checkl(y), l2)
  86.     for i in l3:
  87.         lG2 = copy.deepcopy(lg2)
  88.         for j in i:
  89.             lG2 = lr(lG2,j[0],str(j[1]))
  90.         for j in i:
  91.             lG2 = lr(lG2,str(j[1]),j[1])
  92.         LG2 = []
  93.         for t in lG2:
  94.             t.sort()
  95.             LG2.append(t)
  96.         LG2.sort()
  97.         if lg1 == LG2:
  98.             return True
  99.     return False
  100.  
  101. ##########################
  102. ####
  103. ####  Main sequence
  104. ####
  105. ##########################
  106.  
  107. ## Gives a list of at most trivalent graphs with n+1 vertices, where the list l has graphs with n vertices
  108. ## Uses dictionary structure, because graph object was inconsistent
  109.  
  110. a = max(flatten(map(lambda x: x.keys(), l)))
  111. vl = range(1,a+1)
  112. nl = []
  113. for i in l:
  114.     im = max(flatten(i.values()))
  115.     itemp = copy.deepcopy(i)
  116.     l1 = filter(lambda x: deg(i,x) == 1, i.keys())
  117.     l2 = filter(lambda x: deg(i,x) == 2, i.keys())
  118.     for j1 in l1:
  119.         for j2 in l1:
  120.             itemp[j1] += [j2]
  121.             nl.append(itemp)
  122.             itemp = copy.deepcopy(i)
  123.         for j3 in l2:
  124.             itemp[j1] += [j3]
  125.             nl.append(itemp)
  126.             itemp = copy.deepcopy(i)
  127.         itemp[j1] += [im+1]
  128.         nl.append(itemp)
  129.         itemp = copy.deepcopy(i)
  130.     for j4 in l2:
  131.         for j5 in lf(l2,j4):
  132.             itemp[j4] += [j5]
  133.             nl.append(itemp)
  134.             itemp = copy.deepcopy(i)
  135.         itemp[j4] += [im+1]
  136.         nl.append(itemp)
  137.         itemp = copy.deepcopy(i)
  138. nnl = []
  139. for i in nl:
  140.     im = max(flatten(i.values()))
  141.     if max(map(lambda x: deg(i,x), i.keys())) <= 3:
  142.         if len(filter(lambda x: not isog(i,x,im),nnl)) == len(nnl):
  143.             nnl.append(i)
  144. for i in nnl:
  145.     for j in flatten(i.values()):
  146.         if j not in i.keys():
  147.             i[j] = []
  148. print nnl
  149.  
  150. ##########################
  151. ####
  152. ####  Initialization and continuation
  153. ####
  154. ##########################
  155.  
  156. ## First list
  157.  
  158. l = [{1:[2],2:[]}]
  159.  
  160. ## Next list
  161.  
  162. l = copy.deepcopy(nnl)