##########################
####
#### 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)