SharedMagnitude Homology Ranks.sagewsOpen in CoCalc
# Graph Magnitude Homology Ranks Calculations
#
# Original maple code by Simon Willerton
# Translation into Python+SAGE by James Cranch
# Further modifications by Simon Willerton
#
# Execute the file with sage's inbuilt python via:
#   sage -python < rational_graph_homology_arxiv.py
#
# The program just generates the chain groups and calculates the differentials
# then uses the ChainComplex package to calculate the homology.
#
# For a graph g the chain groups MC_{*,*}(g) break up in to subcomplexes
# MC_{*,l}^{s,t}(g) where l is the length of the chain and s and t are the initial
# and terminal vertices of the chain.
# So here generators[s,t,k,l] is a list of the degree k generators of such a chain group.
# Then differential[s,t,k,l] is a matrix giving the differential from generators[s,t,k,l]
# to generators[s,t,k-1,l].
# The homology of each subcomplex is calculated then the ranks are added together to give
# the required output.


import sage.all

from sage.graphs.graph import Graph
from sage.graphs.distances_all_pairs import distances_all_pairs
from sage.homology.chain_complex import ChainComplex
#from sage.misc.ascii_art import ascii_art

from sage.graphs.graph_generators import GraphGenerators
graphs = GraphGenerators()

from sage.matrix.constructor import MatrixFactory
matrix = MatrixFactory()

from sage.rings.integer_ring import IntegerRing
from sage.rings.rational_field import RationalField
from sage.rings.finite_rings.finite_field_constructor import FiniteField #"finite_field" added - V.S
#BaseRing = IntegerRing()
#BaseRing = RationalField()
BaseRing = FiniteField(2)





def magnitude_homology(g,lmax=6):

    kmax = lmax +1

    d = distances_all_pairs(g)

    # populate the generators recursively
    generators = dict(((s,t,k,l),[]) for s in g.vertices() for t in g.vertices() for k in xrange(kmax+2) for l in xrange(lmax+1))
    def add_generators(a,l,x):
        k = len(a)-1
        if k<=kmax and l<=lmax:
            generators[(a[0],a[len(a)-1],k,l)].append(a)
            for y in g.vertices():
                if x != y:
                    add_generators(a+[y],l+d[x][y],y)
    for x in g.vertices():
        add_generators([x],0,x)



    # number the generators, so as to produce differentials rapidly
    for s in g.vertices():
        for t in g.vertices():
            for l in xrange(lmax+1):
                for k in xrange(kmax+1):
                    generators[(s,t,k,l)] = dict((tuple(a),i) for (i,a) in enumerate(generators[(s,t,k,l)]))


    def differential(s,t,k,l):
        m = {}
        h = generators[(s,t,k-1,l)]
        for (a,i) in generators[(s,t,k,l)].iteritems():
            for z in xrange(len(a)-2):
                if d[a[z]][a[z+1]] + d[a[z+1]][a[z+2]] == d[a[z]][a[z+2]]:
                    j = h[a[:z+1]+a[z+2:]]
                    if z%2:
                        m[(j,i)] = m.get((j,i),0) + 1
                    else:
                        m[(j,i)] = m.get((j,i),0) - 1
        return matrix(BaseRing, len(h), len(generators[(s,t,k,l)]), m)


    def chains(s,t,l):
        differentials = dict((k,differential(s,t,k,l)) for k in xrange(1,kmax+1) if generators[(s,t,k,l)] or generators[(s,t,k-1,l)])
        return ChainComplex(differentials, base_ring=BaseRing, degree=-1)




    def homology(s,t,l):
        return chains(s,t,l).homology(generators=False)

    return dict(((s,t,l),homology(s,t,l)) for s in g.vertices() for t in g.vertices() for l in xrange(lmax+1))

def figure_eight(m,n):
    g1 = graphs.CycleGraph(m)
    g2 = graphs.CycleGraph(n+m-2)
    return g1.union(g2)

def cyclic_wedge(m,n):
    g1 = graphs.CycleGraph(m)
    g2 = graphs.CycleGraph(n)
    g2.relabel(lambda i:i+m-1)
    return g1.union(g2)


# Pick a graph from the following list, or add your own

#g = Graph([(1,2),(2,3),(3,4),(4,1),(3,1)])
#g = graphs.CycleGraph(9); graph_name = "Cyc(9)"
#g = figure_eight(5,4); graph_name = 'Cyc(5) union Cyc(4) over an edge'
#g = cyclic_wedge(4,5)
#g = graphs.CompleteBipartiteGraph(4,3); graph_name='C(4,3)'
#g = graphs.RandomGNP(12,0.7)
#g = graphs.DodecahedralGraph(); graph_name = 'Dodecahedral Graph'
#g = graphs.HexahedralGraph(); graph_name = 'Hexecahedral Graph'
#g = graphs.OctahedralGraph(); graph_name = 'Octahedral Graph'
#g = graphs.IcosahedralGraph(); graph_name = 'Icosahedral Graph'
#g = graphs.MoebiusKantorGraph(); graph_name = 'Moebius Kantor Graph'
#g = graphs.PappusGraph(); graph_name = 'Pappus Graph'
#g = graphs.HeawoodGraph(); graph_name = 'Heawood Graph'
#g = graphs.PetersenGraph(); graph_name='Petersen Graph'
#g = Graph({0:[1,2,3,4,5], 1:[0,2,3,4,5], 2:[0,1,3,4,5], 3:[0,1,2], 4:[0,1,2], 5:[0,1,2]})
#g = Graph({0:[1,5],1:[0,2,4,5],2:[1,3,4],3:[2,4],4:[1,2,3,5],5:[1,4,0]}); graph_name = '{0:[1,5],1:[0,2,4,5],2:[1,3,4],3:[2,4],4:[1,2,3,5],5:[1,4,0]'
#g = Graph({0:[1,3],1:[0,2],2:[1,3],3:[0,2]}); graph_name = 'Square'
#g = Graph({0:[1,3],1:[0,2],2:[1,3],3:[0,2],4:[0,1,2,3]}); graph_name = 'W_4'
#g = Graph({0:[1,2,3],1:[2],2:[3],3:[0,2]}); graph_name = 'Square with Chord'
#g = Graph({0:[1,2,3,4],1:[2],2:[3],3:[4],4:[0]}); graph_name = 'Kite'
#g = Graph({0:[1],1:[2],2:[0]}); graph_name = 'Triangle'
#g = Graph({0:[1,2],1:[3],2:[3,4],3:[5],4:[5],5:[4]}); graph_name = 'Domino'
#g = Graph({0:[1,2],1:[3],2:[3,4],3:[5],4:[5],5:[4],6:[1,7],7:[3,8],8:[5]}); graph_name = 'Tiled Square'
#g = Graph({0:[1,2],1:[3],2:[3,4],3:[5],4:[5],5:[4],6:[5,7],7:[3]}); graph_name = 'Tetris'
#g = Graph({0:[1,2],1:[3],2:[3,4],3:[5],4:[5,6],5:[4,7],6:[7],7:[6]}); graph_name = 'Triple Domino'
#g = Graph({0:[1,2],1:[3],2:[3,4],3:[5],4:[5,6],5:[4,7],6:[7,8],7:[6],8:[9,10],9:[7,11],10:[11],11:[10]}); graph_name = 'Quadruple Domino'
#g = Graph({0:[1,2,3],1:[0,2,3],2:[1,3],3:[0,2]}); graph_name = 'K_4'
#g = Graph({0:[1,2,3],1:[0,2,3],2:[1,3],3:[0,2],4:[0,1,2]})
#g = Graph({0:[1,2,3],1:[0,2,3],2:[1,3],3:[0,2],4:[0,3],5:[2,3]})
#g = graphs.CompleteMultipartiteGraph([3,3,3,3,3]); graph_name = "C(3,3,3,3,3)"
#g = graphs.CycleGraph(6); graph_name='Cycle Graph'
#g = graphs.PetersenGraph(); graph_name='Petersen Graph'
#k = graphs.CycleGraph(5)
#k = graphs.CompleteMultipartiteGraph([1])
#g = h.join(k); graph_name = "Cyc(5) + Cyc(5)"
#g = graphs.TutteCoxeterGraph(); graph_name = "Tutte Coxeter Graph"

#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[6,9],9:[7,8]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[6,9],9:[7,8],10:[8,11],11:[9,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[6,9],9:[7,8],10:[8,11],11:[9,10],12:[10,13],13:[11,12]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[6,9],9:[7,8],10:[8,11],11:[9,10],12:[10,13],13:[11,12],14:[12,15],15:[13,14]})

#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,7],7:[2,6]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[0,9],9:[2,8]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,7],7:[2,6,8],8:[4,7]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[7,9],7:[0,6,8],8:[2,7],9:[0,6]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[2,9],9:[4,8]})

#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[7,9],7:[0,6,8],8:[2,7],9:[0,6],10:[4,8],11:[1,9]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[6,9],9:[7,8],10:[0,11],11:[2,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[6,9],9:[7,8],10:[2,11],11:[4,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[9,11],9:[0,8,10],10:[2,9],11:[0,8]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[0,9],9:[2,8,10],10:[4,9]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[0,9,10],9:[2,8,11],10:[8,11],11:[9,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[2,9,10],9:[4,8,11],10:[8,11],11:[9,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[0,9],9:[2,8],10:[4,11],11:[6,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[3,9],9:[5,8],10:[0,11],11:[2,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[5,9],9:[7,8],10:[0,11],11:[2,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,7],7:[6,8,10],8:[0,7,9,11],9:[2,8],10:[7,11],11:[8,10]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[4,7],7:[5,6],8:[3,9],9:[5,8],10:[2,11],11:[4,10]})

#g = Graph({0:[1,2],1:[0,2],2:[0,1]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2],4:[2,3]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2],4:[1,3],5:[3,4]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2],4:[2,3],5:[2,4]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2],4:[2,3],5:[1,3]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2],4:[1,3],5:[3,4],6:[4,5]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2],4:[1,3],5:[3,4],6:[1,4]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2],4:[1,3],5:[3,4],6:[0,1]})
#g = Graph({0:[1,2],1:[2,3,0],2:[0,1,3,4,5,6],3:[1,2,4],4:[2,3,5],5:[2,4,6],6:[2,5]})

#g = Graph({0:[1,2,3],1:[0,2,3],2:[0,1,3],3:[0,2,1]})
#g = Graph({0:[1,2,3,4],1:[2,4],2:[1,3],3:[0,2,4],4:[0,1,3]})
#g = Graph({0:[1,2,3,4,5],1:[2,5],2:[1,3],3:[2,4],4:[3,5],5:[1,4]})
#g = Graph({0:[1,2,3,4,5,6],1:[2,6],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[1,5]})
#g = Graph({0:[1,2,3,4,5,6],1:[2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5],7:[0,6],8:[0,7],9:[0,1,8]})

#g = Graph({0:[1,2],1:[3,4],2:[3,4],3:[1,2],4:[1,2]})
#g = Graph({0:[1,2,3],1:[0],2:[0],3:[0],4:[1,2],5:[2,3],6:[1,3]})
#g = Graph({0:[1,2,3,4],1:[0],2:[0],3:[0],4:[0],5:[1,2],6:[2,3],7:[3,4],8:[1,4]})
#g = Graph({0:[1,2,3,4,5],1:[7,11],2:[7,8],3:[8,9],4:[9,10],5:[10,11],7:[1,2],8:[2,3],9:[3,4],10:[4,5],11:[1,5]})
#g = Graph({0:[1,2,3,4,5,6],1:[8,9],2:[9,10],3:[10,11],4:[11,12],5:[12,13],6:[8,13],8:[1,6],9:[1,2],10:[2,3],11:[3,4],12:[4,5],13:[5,6]})

#g = Graph({0:[1,2],1:[3,6],2:[4,5],3:[1,4],4:[2,3],5:[2,6],6:[1,5]})
#g = Graph({0:[1,2,3],1:[4,9],2:[5,6],3:[7,8],4:[1,5],5:[2,4],6:[2,7],7:[3,6],8:[3,9],9:[1,8]})
#g = Graph({0:[1,2,3,4],1:[5,12],2:[6,7],3:[8,9],4:[10,11],5:[1,6],6:[2,5],7:[2,8],8:[3,7],9:[3,10],10:[4,9],11:[4,12],12:[1,11]})
#g = Graph({0:[1,2,3,4,5],1:[6,15],2:[7,8],3:[9,10],4:[11,12],5:[13,14],6:[1,7],7:[2,6],8:[2,9],9:[3,8],10:[3,11],11:[10,4],12:[4,13],13:[5,12],14:[5,15],15:[1,14]})

#g = Graph({0:[1,2],1:[3,8],2:[5,6],3:[1,4],4:[3,5],5:[2,4],6:[2,7],7:[6,8],8:[1,7]})
#g = Graph({0:[1,2,3],1:[4,12],2:[6,7],3:[9,10],4:[1,5],5:[4,6],6:[2,5],7:[2,8],8:[7,9],9:[3,8],10:[3,11],11:[10,12],12:[1,11]})
#g = Graph({0:[1,5,9,13],1:[2,16],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[6,8],8:[7,9],9:[8,10],10:[9,11],11:[10,12],12:[11,13],13:[12,14],14:[13,15],15:[14,16],16:[1,15]})

#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[1,2],4:[2,3],5:[1,3]})
#g = Graph({0:[1,3,4,5],1:[0,2,5,6],2:[1,3,6,7],3:[0,2,4,7],4:[0,3],5:[0,1],6:[1,2],7:[2,3]})
#g = Graph({0:[1,4,5,6],1:[0,2,6,7],2:[1,3,7,8],3:[2,4,8,9],4:[0,3,5,9],5:[0,4],6:[0,1],7:[1,2],8:[2,3],9:[3,4]})
#g = Graph({0:[1,5,6,7],1:[0,2,7,8],2:[1,3,8,9],3:[2,4,9],4:[3,5,10,11],5:[0,4,6,11],6:[0,5],7:[0,1],8:[1,2],9:[2,3],10:[3,4],11:[4,5]})
#g = Graph({0:[1,6,7,8],1:[0,2,8,9],2:[1,3,9,10],3:[2,4,10,11],4:[3,5,11,12],5:[4,6,12,13],6:[0,5,7,13],7:[0,6],8:[0,1],9:[1,2],10:[2,3],11:[3,4],12:[4,5],13:[5,6]})

#g = Graph({0:[1,3,5,6],1:[2,7,8],2:[1,3,9,10],3:[0,2,4,11],4:[3,5],5:[0,4],6:[0,7],7:[1,6],8:[1,9],9:[2,8],10:[2,11]})
#g = Graph({0:[1,4,5,14],1:[0,2,6,7],2:[1,3,8,9],3:[2,4,10,11],4:[0,3,12,13],5:[0,6],6:[1,5],7:[1,8],8:[2,7],9:[2,10],10:[3,9],11:[3,12],12:[4,11],13:[4,14],14:[0,13]})
#g = Graph({0:[1,5,6,17],1:[0,2,7,8],2:[1,3,9,10],3:[2,4,11,12],4:[5,13,14],5:[0,4,15,16],6:[0,7],7:[1,6],8:[1,9],9:[2],10:[2,11],11:[3,10],12:[3,13],13:[4,12],14:[4,15],15:[5,14],16:[5,17],17:[0,16]})

#g = Graph({0:[1,2,3,4],1:[0,2,6,7],2:[0,1,9,10],3:[0,11],4:[0,5],5:[4,6],6:[1,5],7:[1,8],8:[7,9],9:[2,8],10:[2,11],11:[3,10]})
#g = Graph({0:[1,3,4,15],1:[0,2,6,7],2:[1,3,9,10],3:[0,2,12,13],4:[0,5],5:[4,6],6:[1,5],7:[1,8],8:[7,9],9:[2,8],10:[2,11],11:[10,12],12:[3,11],13:[3,14],14:[13,15],15:[0,14]})
#g = Graph({0:[1,4,5,19],1:[0,2,7,8],2:[1,3,10,11],3:[2,4,13,14],4:[0,3,16,17],5:[0,6],6:[5,7],7:[1,6],8:[1,9],9:[8,10],10:[2,9],11:[2,12],12:[11,13],13:[3,12],14:[3,15],15:[14,16],16:[4,15],17:[4,18],18:[17,19],19:[0,18]})
#g = Graph({0:[1,5,6,23],1:[0,2,8,9],2:[1,3,11,12],3:[2,4,14,15],4:[3,5,17,18],5:[0,4,20,21],6:[0,7],7:[6,8],8:[1,7],9:[1,10],10:[9,11],11:[2,10],12:[2,13],13:[12,14],14:[3,13],15:[3,16],16:[15,17],17:[4,16],18:[4,19],19:[18,20],20:[5,19],21:[5,22],22:[21,23],23:[0,22]})

#g = Graph({0:[1,2,3],1:[0,2,3],2:[0,1,3],3:[0,1,2]})
#g = Graph({0:[1,3,4],1:[0,2,4],2:[1,3,4],3:[0,2,4],4:[0,1,2,3]})
#g = Graph({0:[1,4,5],1:[0,2,5],2:[1,3,5],3:[2,4,5],4:[0,3,5],5:[0,1,2,3,4]})
#g = Graph({0:[1,5,6],1:[0,2,6],2:[1,3,6],3:[2,4,6],4:[3,5,6],5:[0,4,6],6:[0,1,2,3,4,5]})

#g = Graph({0:[1,2,3],1:[0,2,4],2:[0,1,5],3:[0,4,5],4:[1,3,5],5:[2,3,4]})
#g = Graph({0:[1,3,4],1:[0,2,5],2:[1,3,6],3:[0,2,7],4:[0,5,7],5:[1,4,6],6:[2,5,7],7:[3,4,6]})
#g = Graph({0:[1,4,5],1:[0,2,6],2:[1,3,7],3:[2,4,8],4:[0,3,9],5:[0,6,9],6:[1,5,7],7:[2,6,8],8:[3,7,9],9:[4,5,8]})
#g = Graph({0:[1,5,11],1:[0,2,6],2:[1,3,7],3:[2,4,8],4:[3,5,9],5:[0,4,10],6:[1,7,11],7:[2,6,8],8:[3,7,9],9:[4,8,10],10:[5,9,11],11:[0,6,10]})

#g = Graph({0:[1,2,3],1:[0,2,5],2:[0,1,7],3:[0,4,8],4:[3,5],5:[4,6],6:[5,7],7:[6,8],8:[3,7]})
#g = Graph({0:[1,3,4],1:[0,2,6],2:[1,3,8],3:[0,2,10],4:[0,5,11],5:[4,6],6:[1,5,7],7:[6,8],8:[2,7,9],9:[8,10],10:[3,9,11],11:[4,10]})
#g = Graph({0:[1,4,13],1:[0,2,5],2:[1,3,7],3:[2,4,9],4:[0,3,11],5:[1,6,14],6:[5,7],7:[2,6,8],8:[7,9],9:[3,8,10],10:[9,11],11:[4,10,12],12:[11,13],13:[0,12,14],14:[5,13]})
#g = Graph({0:[1,5,16],1:[0,2,6],2:[1,3,8],3:[2,4,10],4:[3,5,12],5:[0,4,14],6:[1,7,17],7:[6,8],8:[2,7,9],9:[8,10],10:[3,9,11],11:[10,12],12:[4,11,13],13:[12,14],14:[5,13,15],15:[14,16],16:[0,15,17],17:[6,16]})

#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[1,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[1,3],6:[2,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[1,3],6:[2,3],7:[0,2]})

#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1],6:[1,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1],6:[2,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1],6:[0,1]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[2,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1],6:[1,3],7:[2,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1],6:[1,3],7:[0,2]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1],6:[1,3],7:[0,1]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1],6:[2,3],7:[0,1]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[0,1],6:[0,1],7:[0,1]})

#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,1]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[1,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[2,3]})

#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,1],7:[4,5]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,1],7:[3,5]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,1],7:[1,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,1],7:[0,1]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[2,3],7:[2,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,2],7:[1,3]})
#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[2,5],5:[3,4],6:[0,2],7:[3,5]})

#g = Graph({0:[1,2],1:[0,3],2:[0,3],3:[1,2],4:[0,1],5:[2,3]})
#g = Graph({0:[1],1:[0],2:[3],3:[2],4:[0,1],5:[2,3],6:[2,7],7:[3],8:[0,6,9],9:[1,7]})
#g = Graph({0:[1],1:[0],2:[3],3:[2],4:[0,1],5:[2,3],6:[7],7:[],8:[0,6,9],9:[1,7],10:[2,6,11],11:[3,7]})

#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[0,1]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[1,2]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[2,3]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[3,4]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[0,1],10:[1,2]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[0,1],10:[2,3]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[0,1],10:[3,4]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[6,7],9:[0,1],10:[3,4]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[0,1],10:[1,2],11:[2,3]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[0,1],10:[1,2],11:[3,4]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[0,7],9:[0,1],10:[1,2],11:[4,5]})
#g = Graph({0:[1,7],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[0,6],8:[6,7],9:[0,1],10:[2,3],11:[4,5]})
#g = Graph({0:[1],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[6,8],8:[0,7],9:[0,1],10:[4,5]})

#g = Graph({0:[1,2,3,4],1:[0,2,3,4],2:[0,1,3,4],3:[0,1,2],4:[0,1,2]})
#g = Graph({0:[1,3,4,5],1:[0,2,4,5],2:[1,3,4,5],3:[0,4,5],4:[0,1,2,3],5:[0,1,2,3]})

#g = Graph({0:[1,4],1:[0,2,6],2:[1,3,6],3:[2,4,5],4:[0,3,5],5:[3,4],6:[1,2]})
#g = Graph({0:[1,5,6],1:[0,2],2:[1,3,7],3:[2,4,7],4:[3,5],5:[0,4,6],6:[0,5],7:[2,3]})

#g = Graph({0:[1,3],1:[0,2,4],2:[1,3,4],3:[0,2],4:[1,2]})
#g = Graph({0:[1],1:[0]})
#g = Graph({0:[1,2],1:[0,2,3],2:[0,1,3],3:[1,2]})

#g = Graph({0:[1,2,8],1:[3,9],2:[3,4],3:[2,5],4:[5,6],5:[7],6:[7,8],7:[9],8:[0,6],9:[8]}) #squares-annulus-5
#g = Graph({0:[1,2],1:[3],2:[3,4],3:[2,5],4:[5,6],5:[7],6:[7,8],7:[9],8:[1,6,9],9:[8,0]}) #squares-mobiusband-5
#g = Graph({0:[1,2,3,8,9],1:[3,9],2:[3,4,5],3:[2,5],4:[5,6,7],5:[7],6:[7,8,9],7:[9],8:[0,6],9:[8]}) #triangles-annulus-5
#g = Graph({0:[1,3,8],1:[2,3,8,9],2:[3,5,4],3:[5],4:[5,6,7],5:[7],6:[7,8,9],7:[9],8:[9],9:[]}) #triangles-mobiusband-5


#Graphs made from only triangles

#g = Graph({0:[1,2],1:[0,2],2:[0,1]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[0,1]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[0,1],4:[0,3]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[0,1],4:[0,3],5:[3,4]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[0,1],4:[0,3],5:[1,3]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[0,1],4:[0,3],5:[1,2]})
#g = Graph({0:[1,2],1:[0,2],2:[0,1],3:[0,1],4:[0,3],5:[0,2]})

#YK-graph from minimal triangulation of RP^2

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [22,32]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [23,32]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [7,22]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [8,23]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,27],8:[24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [13,24]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [1,7]

#g = Graph({0:[1,2,3,4,5,6],1:[8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [2,7]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [3,10]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) minus [1,7],[7,27]

#g = Graph({0:[1,2,3,4,5,6],1:[8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) plus [7,23]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21],7:[22,23,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) plus [7,23] plus [7,24]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21,24],7:[22,23,24,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) plus [7,23],[7,24],[7,25]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21,24],7:[22,23,24,25,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) plus [7,23],[7,24],[7,25],[7,26]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21,24],7:[22,23,24,25,26,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})


#YK(RP2) plus [7,23],[7,24],[7,25],[7,26],[16,17]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21,24],7:[22,23,24,25,26,27],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[17,26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) plus all edges from 1-simplicies to 2-simplices

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21,24],7:[22,23,24,25,26,27,28,29,30,31],8:[22,23,24,25,26,27,28,29,30,31],9:[22,23,24,25,26,27,28,29,30,31],10:[22,23,24,25,26,27,28,29,30,31],11:[22,23,24,25,26,27,28,29,30,31],12:[22,23,24,25,26,27,28,29,30,31],13:[22,23,24,25,26,27,28,29,30,31],14:[22,23,24,25,26,27,28,29,30,31],15:[22,23,24,25,26,27,28,29,30,31],16:[22,23,24,25,26,27,28,29,30,31],17:[22,23,24,25,26,27,28,29,30,31],18:[22,23,24,25,26,27,28,29,30,31],19:[22,23,24,25,26,27,28,29,30,31],20:[22,23,24,25,26,27,28,29,30,31],21:[22,23,24,25,26,27,28,29,30,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})


#YK(RP2) plus [7,x] for each 2-simplex x

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21,24],7:[22,23,24,25,26,27,28,29,30,31],8:[23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[17,26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) plus each [7,x] plus [8,22]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21,24],7:[22,23,24,25,26,27,28,29,30,31],8:[22,23,24],9:[22,23],10:[25,29],11:[22,26],12:[23,30],13:[24,28],14:[25,26],15:[24,25],16:[17,26,31],17:[27,28],18:[27,29],19:[29,30],20:[30,31],21:[28,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})

#YK(RP2) plus all edges from 1-simplicies to 2-simplices minus [21,30]

#g = Graph({0:[1,2,3,4,5,6],1:[7,8,9,13,17],2:[7,10,11,14,18],3:[8,10,12,15,19],4:[9,11,12,16,20],5:[13,14,15,16,21],6:[17,18,19,20,21,24],7:[22,23,24,25,26,27,28,29,30,31],8:[22,23,24,25,26,27,28,29,30,31],9:[22,23,24,25,26,27,28,29,30,31],10:[22,23,24,25,26,27,28,29,30,31],11:[22,23,24,25,26,27,28,29,30,31],12:[22,23,24,25,26,27,28,29,30,31],13:[22,23,24,25,26,27,28,29,30,31],14:[22,23,24,25,26,27,28,29,30,31],15:[22,23,24,25,26,27,28,29,30,31],16:[22,23,24,25,26,27,28,29,30,31],17:[22,23,24,25,26,27,28,29,30,31],18:[22,23,24,25,26,27,28,29,30,31],19:[22,23,24,25,26,27,28,29,30,31],20:[22,23,24,25,26,27,28,29,30,31],21:[22,23,24,25,26,27,28,29,31],22:[32],23:[32],24:[32],25:[32],26:[32],27:[32],28:[32],29:[32],30:[32],31:[32],32:[]})


#Shrikhande graph

#g=Graph({0:[1,3,4,5,12,15],1:[2,5,6,12,13],2:[3,6,7,13,14],3:[4,7,14,15],4:[5,7,8,9],5:[6,9,10],6:[7,10,11],7:[8,11],8:[9,11,12,13],9:[10,13,14],10:[11,14,15],11:[12,15],12:[13,15],13:[14],14:[15],15:[]})


#Rook(4,4) graph

#g=Graph({0:[1,2,3,4,8,12],1:[2,3,5,9,13],2:[3,6,10,14],3:[7,11,15],4:[5,6,7,8,12],5:[6,7,9,13],6:[7,10,14],7:[11,15],8:[9,10,11,12],9:[10,11,13],10:[11,14],11:[15],12:[13,14,15],13:[14,15],14:[15],15:[]})

#Random outer planar graph with one triangle

#g=Graph({0:[1,4],1:[2],2:[3],3:[4,5,10],4:[12],5:[6],6:[7],7:[8],8:[9],9:[10],10:[11],11:[12,16],12:[13],13:[14],14:[15],15:[16,23],16:[17],17:[18],18:[19],19:[20],20:[21],21:[22],22:[23,24],23:[24],24:[]})

#Random outer planar graph with two triangles

#g=Graph({0:[1,4],1:[2],2:[3],3:[4,5,10],4:[12],5:[6],6:[7],7:[8],8:[9],9:[10],10:[11],11:[12,16],12:[13],13:[14],14:[15],15:[16,23],16:[17],17:[18],18:[19],19:[20],20:[21],21:[22],22:[23,24],23:[24],24:[],25:[11,16]})

#Random outer planar graph with three triangles

#g=Graph({0:[1,4],1:[2],2:[3],3:[4,5,10],4:[12],5:[6],6:[7],7:[8],8:[9],9:[10],10:[11],11:[12,16],12:[13],13:[14],14:[15],15:[16,23],16:[17],17:[18],18:[19],19:[20],20:[21],21:[22],22:[23,24],23:[24],24:[],25:[11,16],26:[1,2]})

#Random outer planar graph with four triangles

#g=Graph({0:[1,4],1:[2],2:[3],3:[4,5,10],4:[12],5:[6],6:[7],7:[8],8:[9],9:[10],10:[11],11:[12,16],12:[13],13:[14],14:[15],15:[16,23],16:[17],17:[18],18:[19],19:[20],20:[21],21:[22],22:[23,24],23:[24],24:[],25:[11,16],26:[1,2],27:[23,24]})

#triangulation = simplicial_complexes.RealProjectivePlane()
#poset = triangulation.face_poset().with_bounds()
#graph = poset.hasse_diagram()

#show(poset.plot())

g=Graph({0:[1,5],1:[2],2:[3],3:[4],4:[5,9],5:[6],6:[7],7:[8],8:[9],9:[]})

g.show()

#g.triangles_count()

lmax =8

#print graph_name
print 'lmax = {0}'.format(lmax)

homology = magnitude_homology(g,lmax)


total_rank = dict(((k,l),0) for k in range(0,lmax+1) for l in range(0, lmax+1))

for s in g.vertices():
    for t in g.vertices():
        for l in xrange(lmax+1):
            for degree, group in sorted(homology[s,t,l].iteritems()): 
                total_rank[degree,l] += group.rank()


for l in range(0,lmax+1):
    print
    print '{0:2d}:'.format(l),
    for k in range(0,lmax+1):
        if total_rank[k,l] != 0:
            print '{0:5d} '.format(total_rank[k,l]),
        else:
            print '      ',
lmax = 8 0: 10 1: 22 2: 22 3: 12 22 4: 24 22 5: 24 22 6: 12 24 22 7: 24 24 22 8: 24 24 22 0: 10 1: 30 2: 30 3: 120 30 4: 480 30 5: 840 30 6: 1440 1200 30