Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ##########################
- ####
- #### Helper functions
- ####
- ##########################
- import copy
- ## Returns the input list with the input value removed
- def lf(lst,num):
- lst.remove(num)
- return lst
- ## Returns a list with all instances of target replaced with new
- def lr(l,target,new):
- ll = []
- for i in l:
- cl = []
- for j in i:
- if j == target:
- cl.append(new)
- else:
- cl.append(j)
- ll.append(cl)
- return ll
- ## Checks if every value appears exactly twice in a list
- def checkl(l):
- a = max(flatten(l))
- for i in range(1,a+1):
- if len(filter(lambda z: z[0] == i,l)) == 1 and len(filter(lambda z: z[1] == i,l)) == 1:
- continue
- else:
- return False
- return True
- ## Gives the degree of the vertex in the graph
- def deg(g,v):
- a = len(g[v]) + len(filter(lambda x: x == v, flatten(g.values())))
- return a
- ## Creates a Mathematica graph
- def tomg(g):
- s = "GraphPlot[{"
- for i in g.keys():
- for j in g[i]:
- s += "%g->%g,"%(i,j)
- s = s[:-1]
- s += "}]"
- return s
- ## Checks for graph isomorphism
- ## m is number of vertices
- def isog(g1,g2,m):
- lg1t = []
- lg1 = []
- for i in g1.keys():
- for j in g1[i]:
- lg1t.append([i,j])
- for t in lg1t:
- t.sort()
- lg1.append(t)
- lg1.sort()
- lg2t = []
- lg2 = []
- for i in g2.keys():
- for j in g2[i]:
- lg2t.append([i,j])
- for t in lg2t:
- t.sort()
- lg2.append(t)
- lg2.sort()
- ##Checks if same edges, same vertices
- if lg1 == lg2:
- return True
- ##Checks if permutations of vertices
- l1 = Arrangements(range(1,m+1)+range(1,m+1),2).list()
- l2 = Combinations(l1,m).list()
- l3 = filter(lambda y: checkl(y), l2)
- for i in l3:
- lG2 = copy.deepcopy(lg2)
- for j in i:
- lG2 = lr(lG2,j[0],str(j[1]))
- for j in i:
- lG2 = lr(lG2,str(j[1]),j[1])
- LG2 = []
- for t in lG2:
- t.sort()
- LG2.append(t)
- LG2.sort()
- if lg1 == LG2:
- return True
- return False
- ##########################
- ####
- #### Main sequence
- ####
- ##########################
- ## Gives a list of at most trivalent graphs with n+1 vertices, where the list l has graphs with n vertices
- ## Uses dictionary structure, because graph object was inconsistent
- a = max(flatten(map(lambda x: x.keys(), l)))
- vl = range(1,a+1)
- nl = []
- for i in l:
- im = max(flatten(i.values()))
- itemp = copy.deepcopy(i)
- l1 = filter(lambda x: deg(i,x) == 1, i.keys())
- l2 = filter(lambda x: deg(i,x) == 2, i.keys())
- for j1 in l1:
- for j2 in l1:
- itemp[j1] += [j2]
- nl.append(itemp)
- itemp = copy.deepcopy(i)
- for j3 in l2:
- itemp[j1] += [j3]
- nl.append(itemp)
- itemp = copy.deepcopy(i)
- itemp[j1] += [im+1]
- nl.append(itemp)
- itemp = copy.deepcopy(i)
- for j4 in l2:
- for j5 in lf(l2,j4):
- itemp[j4] += [j5]
- nl.append(itemp)
- itemp = copy.deepcopy(i)
- itemp[j4] += [im+1]
- nl.append(itemp)
- itemp = copy.deepcopy(i)
- nnl = []
- for i in nl:
- im = max(flatten(i.values()))
- if max(map(lambda x: deg(i,x), i.keys())) <= 3:
- if len(filter(lambda x: not isog(i,x,im),nnl)) == len(nnl):
- nnl.append(i)
- for i in nnl:
- for j in flatten(i.values()):
- if j not in i.keys():
- i[j] = []
- print nnl
- ##########################
- ####
- #### Initialization and continuation
- ####
- ##########################
- ## First list
- l = [{1:[2],2:[]}]
- ## Next list
- l = copy.deepcopy(nnl)
Add Comment
Please, Sign In to add comment