Sage_Code_BDHLRSY18

1967 days ago by hogben

# This worksheet contains Sage code used to find Distance Laplacian copsectral graphs # that appear in the paper # Graphs that are cospectral for the distance Laplacian # by Boris Brimkov, Ken Duna, Leslie Hogben, Kate Lorenzen, Carolyn Reinhart, # Sung-Yell Song, and Mark Yarrow 
       
################################ # Definitions of Sage functions ################################ 
       
def dL(G): nn=G.order() m=G.distance_matrix() J=ones_matrix(QQ, nn, 1) J=m*J for i in range(nn): m[i,i]=-J[i,0] return -m 
       
################################ # Search for small D^L copsectral graphs ################################ 
       
# Naive search is used for orders <= 8. # None were found below order 7 
       
# Order 6 
       
L=[] for G in graphs.cospectral_graphs(6, matrix_function=dL, graphs=lambda g: g.is_connected()): L.append([i.graph6_string() for i in G]) 
       
file1=open("cospec6vert.txt", "w"); for i in range(len(L)): file1.writelines(L[i]) file1.writelines("\r\n") file1.close() 
       
# Order 7 
       
L=[] for G in graphs.cospectral_graphs(7, matrix_function=dL, graphs=lambda g: g.is_connected()): L.append([i.graph6_string() for i in G]) 
       
file1=open("cospec7vert.txt", "w"); for i in range(len(L)): file1.writelines(L[i]) file1.writelines("\r\n") file1.close() 
       
# Order 8 
       
L=[] for G in graphs.cospectral_graphs(8, matrix_function=dL, graphs=lambda g: g.is_connected()): L.append([i.graph6_string() for i in G]) 
       
file1=open("cospec8vert.txt", "w"); for i in range(len(L)): file1.writelines(L[i]) file1.writelines("\r\n") file1.close() 
       
# Order 9 
       
# For higher orders we used a more sophisticated method. # It sorts all the graphs first by their characteristic polynomial evaluated by a number # and then mod-ed out by another number. 
       
# Order 9 
       
Kates_Num = 545 Kens_Prime = 1223 Num_Vertices = 9 L = [] for i in range(Kens_Prime): L.append([i,[]]) for G in graphs(Num_Vertices): if G.is_connected(): a = mod(distLapla(G).charpoly()(Kates_Num), Kens_Prime) L[a][1].append(G.graph6_string()) N=[] for i in range(Kens_Prime): M=[] for j in range(len(L[i][1])): G=Graph(L[i][1][j]) M.append(G) for G in graphs.cospectral_graphs(Num_Vertices, matrix_function=dL, graphs = M): N.append([j.graph6_string() for j in G]) 
       
file1=open("cospec9vert.txt", "w"); for i in range(len(N)): file1.writelines(N[i]) file1.writelines("\r\n") file1.close() 
       
# Order 10 
       
Kates_Num = 545 Kens_Prime = 1223 Num_Vertices = 10 L = [] for i in range(Kens_Prime): L.append([i,[]]) for G in graphs(Num_Vertices): if G.is_connected(): a = mod(distLapla(G).charpoly()(Kates_Num), Kens_Prime) L[a][1].append(G.graph6_string()) N=[] for i in range(Kens_Prime): M=[] for j in range(len(L[i][1])): G=Graph(L[i][1][j]) M.append(G) for G in graphs.cospectral_graphs(Num_Vertices, matrix_function=dL, graphs = M): N.append([j.graph6_string() for j in G]) 
       
file1=open("cospec10vert.txt", "w"); for i in range(len(N)): file1.writelines(N[i]) file1.writelines("\r\n") file1.close() 
       
################################ # Search for circulant cospectral pairs (Table 4.1) ################################ 
       
def Circulant_Database(n, tracker = False): db = [] i = 0 j = 0 connection_sets = Combinations(range(1,floor(n/2)+1)) s = connection_sets.cardinality() for C in connection_sets: i += 1 if tracker == True: if round(i/s*10) > j: print (j+1)*10, '% of database compilation complete' j += 1 G = graphs.CirculantGraph(n,C) if G.is_connected(): add = 1 for H in db: if G.is_isomorphic(H): add = 0 break if add == 1: db.append(G) return db 
       
file1=open("Circulant_Cospectral_Pairs.txt", "w"); empty = [] for i in range(16,31): circs = Circulant_Database(i) stuff = graphs.cospectral_graphs(i, matrix_function = dL, graphs = circs) if len(stuff) == 0: empty.append(i) else: file1.writelines("Cospectral Circulants on %d vertices:" % i) file1.writelines("\r\n") for foo in stuff: file1.writelines(str(foo[0]) + ' and ' + str(foo[1])) file1.writelines("\r\n") file1.writelines("\r\n") print "%d vertices done!" % i emptstr = "" for foo in empty: emptstr = emptstr + str(foo) + ", " file1.writelines(emptstr[:-2] + " vertices have no pairs!") file1.close() 
        
16 vertices done!
17 vertices done!
18 vertices done!
19 vertices done!
20 vertices done!
21 vertices done!
22 vertices done!
23 vertices done!
^C
Traceback (click to the left of this block for traceback)
...
__SAGE__
16 vertices done!
17 vertices done!
18 vertices done!
19 vertices done!
20 vertices done!
21 vertices done!
22 vertices done!
23 vertices done!
^C
Traceback (most recent call last):            empty.append(i)
  File "", line 1, in <module>
    
  File "/tmp/tmpkYIjHi/___code___.py", line 7, in <module>
    stuff = graphs.cospectral_graphs(i, matrix_function = dL, graphs = circs)
  File "/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph_generators.py", line 1006, in cospectral_graphs
    cp=matrix_function(g).charpoly()
  File "sage/matrix/matrix_integer_dense.pyx", line 1256, in sage.matrix.matrix_integer_dense.Matrix_integer_dense.charpoly (build/cythonized/sage/matrix/matrix_integer_dense.c:12615)
  File "src/cysignals/signals.pyx", line 94, in cysignals.signals.sig_raise_exception
KeyboardInterrupt
__SAGE__