#!/usr/bin/env sage #~ from shutil import * import gc import smtplib from email.MIMEText import MIMEText import commands import sys import copy from sage.all import * gap.load_package("homology") Petersen = graphs.PetersenGraph() # the independence complex of a graph def I(G): return G.complement().cliques() #the dimension of a simplicial complex def Dimension(C): if C == []: return ZZ(0) else: return ZZ(gap.SimplicialComplexDimension(C)) #returns the eta function of the simplicial complex C, which is defined here is the minimal i such that the ith reduced homology group of C do not vanishes def Eta(C): EE = +Infinity if C == []: EE = ZZ(-1) else: HomologieContractibleEquivalente = gap.SimplicialHomology(graphs.CompleteGraph(Dimension(C)+1).cliques()) for i in range(Dimension(C),-1,-1): #~ if gap.SimplicialBettiNumbers(C)[i+1] <> 0: #le +1 vient du fait que les listes commencent a 0 en gap if gap.SimplicialHomology(C)[i+1] <> HomologieContractibleEquivalente[i+1] : #le +1 vient du fait que les listes commencent a 0 en gap EE = ZZ(i) return EE #returns G~(u,v) def Tilde(G,(u,v)): GG = deepcopy(G) U = GG.neighbors(u) V = GG.neighbors(v) for i in U: GG.delete_vertex(i) for i in V: if i in GG: GG.delete_vertex(i) return GG #returns G-e def Moins(G,e): GG = deepcopy(G) GG.delete_edge(e) return GG #A graph with n disjoint edges. Note that I(Matching(n)) is a (n-1)-sphere def Matching(n): G = {} for i in range(n): G[2*i]=[2*i+1] return Graph(G) #Check if Aharoni-Berger's conjecture about the Meshulam's game holds for the graph G def CheckConjecture(G): E = Eta(I(G)) Reponse = False if G.size() == 0: Reponse = True else: for e in G.edges(labels=False): if E == min( Eta(I(Moins(G,e))) , Eta(I(Tilde(G,e)))+1 ): Reponse = True return Reponse return Reponse #If Aharoni-Berger's conjecture about the Meshulam's game does not holds for the graph G, prints the adjacency matrix of G. def DrawConjecture(G): if not CheckConjecture(G): print G.adjacency_matrix() def SendMail(i): text = 'on vient de passer le cap de ' + str(i) mail = MIMEText(text) mail['From'] = "XXXX" mail['Subject'] = "Youpi" mail['To'] = "XXXX" smtp = smtplib.SMTP() smtp.connect() smtp.sendmail("XXXX", ["XXXX"], mail.as_string()) smtp.close() def Clean(): gc.enable() NonRien = commands.getoutput('rm -rf /tmp/tmp.*') NonRien = commands.getoutput('rm -rf ~/.sage/gap/*') gc.collect() #graphes bien connus #~ graphs.HoffmanSingletonGraph(), #~ , graphs.GridGraph() #~ graphs.CirculantGraph() inutile, c'est un ou 2 cycles #~ graphs.ButterflyGraph(), #~ graphs.DorogovtsevGoltsevMendesGraph(), #~ for G in [graphs.PathGraph(6), graphs.BarbellGraph(3,4), graphs.EmptyGraph(), graphs.PetersenGraph(), graphs.BullGraph(), graphs.FruchtGraph(), graphs.ChvatalGraph(), graphs.Grid2dGraph(4,5), graphs.CircularLadderGraph(7), graphs.HeawoodGraph(), graphs.ClawGraph(), graphs.HexahedralGraph(), graphs.CompleteBipartiteGraph(4,5), graphs.CompleteGraph(7), graphs.HouseGraph(), graphs.CubeGraph(4), graphs.HouseXGraph(), graphs.CycleGraph(7), graphs.IcosahedralGraph(), graphs.StarGraph(7), graphs.KrackhardtKiteGraph(), graphs.TetrahedralGraph(), graphs.LCFGraph(20, [-10,-7,-5,4,7,-10,-7,-4,5,7,-10,-7,6,-5,7,-10,-7,5,-6,7], 1), graphs.ThomsenGraph(), graphs.LadderGraph(5), graphs.WheelGraph(8), graphs.LollipopGraph(5,3), graphs.DesarguesGraph(), graphs.MoebiusKantorGraph(), graphs.DiamondGraph(), graphs.OctahedralGraph(), graphs.DodecahedralGraph(), graphs.PappusGraph()]: #~ print G #~ print CheckConjecture(G) #~ print CheckConjecture(G.complement()) #~ G = graphs.PetersenGraph().complement() #~ G = graphs.ChvatalGraph().complement() #~ G = graphs.DesarguesGraph().complement() #~ G = graphs.PetersenGraph() #~ G = graphs.ChvatalGraph() #~ G = graphs.DesarguesGraph() #~ print CheckConjecture(graphs.PetersenGraph()) #exhaustive test on the graphs with the good condition on the diameter. # be careful, the database is empty if the number of edges is greater or equal than 8! #~ for i in range(8): #~ L = GraphDatabase().get_list(num_vertices=i, diameter=2) #~ for G in L: #~ # G.show() #~ DrawConjecture(G.complement()) #~ #print i #~ os.write(1,str(i)) #~ os.write(1," - ") #~ #exhaustive test on the graphs with the good condition on the diameter. #~ #without db #~ gc.enable() #~ print gc.isenabled() #~ for i in range(3,20): #~ for G in [g for g in graphs(i) if (g.diameter() == 2)]: #~ DrawConjecture(G.complement()) #~ # rmtree('/tmp/tmp.*') #~ # !rm -rf /tmp/tmp.* #~ NonRien = commands.getoutput('rm -rf /tmp/tmp.*') #~ gc.collect() #~ # os.execl('/bin/rm -rf', '/tmp/tmp.*') #~ os.write(1,str(i)) #~ os.write(1," - ") #~ SendMail(i) #test sur un matching (le complexe est une sphere) #~ print Dimension(I(Matching(4))) #~ print Eta(I(Matching(4))) #~ print CheckConjecture(Matching(4)) #~ #test avec graphe aleatoire #~ i = 0 #~ while True: #~ Pas = 30 #~ L = [] #~ for n in range(2,40): #~ for p in range(1,Pas): #~ proba = QQ(p)/Pas #~ e = Eta(I(graphs.RandomGNP(n, proba))) #~ if e == +Infinity: #~ e=100 #~ L = L + [[n,p,e]] #~ print n,p,e #~ n = int(random()*100)+10 #~ n = 20 #~ proba = random() #~ proba = 0.5 #~ os.write(1,str(n)) #~ P = graphs.RandomGNP(n, proba) #~ C = I(P) #~ print '- proba ', proba, '- p inverse', 1/proba, '- diam ', P.diameter(), '- size ', P.size(), '- dim C', Dimension(C), '- Eta C ',Eta(C) #~ DrawConjecture(P) #~ Clean() #~ save(L,'L'+str(n)) #~ SendMail(40) #~ show(list_plot3d(L))