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