# SageMathCell online https://sagecell.sagemath.org/?q=ksovyd
# 


from sage.all_cmdline import *   # import sage library

# This script has no online dependencies; new X132 graphs are embedded sparse6.
import networkx as nx
from pathlib import Path
import re

X1 = Graph(':~?AC_C?_CcCC^CcXCSYCKZC[[CS\\C[WCKTBsUA{eDkLACC?kF@CD@KH@SGAShDcLD[J@cD@sM@{GACPASJAcEAcEA[dC{cDCKCSNC[ECKRB[FAkCBkPBsSBsHBCPBSKB[WDSNBKQBKMBSOBcIBcLA{RA{FAsICCJCCCB{UBkTB|CJLHHtNIC{JCmF{yGCqHCnI{|HkrIdIH[oGLFISsIstHcuE{}IKzGswI[xGlAihmg[pMDYJ\\[JldMLeL|]Lt^KDhLliL\\`KTfLdgMDbKc@MPr_HsMkAMpv_XyNkBNX{_PwNN')
X2 = Graph(':~?AC_C?_CD?cC`gKaOPa_RawUbOMak\\@KI`[WbsbB_ab{_CSOCKNCcGBKE_gFccgDS`a_h`OJb?[aoY`_M`wOaORagV`gZbGb`GP_o\\_g_dKFDkY`[\\b{PbKdco~aSMaxAbCNF[FB[LHCRG[Ta_}asIFkGD[G@KfHkaGsOH{[GK]GkKGCCj@XixXdwoegxeOsd_reGydovdgudWwfW|gXCg@AgHIh@Hf_}fxEghFhXQi@Ph`LhpNihUiXSj`\\k@bkHajp^k`fkhel@jlHil`nlhmjXpjPo_HqMk@MXs_XwNKAMpv_XzNkANP{')
X3 = Graph(':~?AC_C?_C]B[\\bccAwbag`aoab?`bOabGb`{PaCRDcSD[QDSWbKYboqc?obwp`WM`gM`_M`GN`?O`OP`?N`GP`OO_gR_wS_oQcghcofc_g`Ga`?b`O`_gT_wU_oV`_U`WV`gT`WW`gY`_X__Z__[__\\_gZ_w\\_o[aO]a__aW^g@VfxWgHXfXIfHGfPHhXSh`ThhUghQgxRgpPehNe`OeXMe?{eO}eG|d`AdPCdXBdgudwwdovkphl@jkxikXnkhpk`ojh_jxajp`jPkj`mjXl_HqNCBM`y_PrNK@Mhz_PvNkBMp{')
X4 = Graph(':~?AC_C?_CbCS]bwccK_CsZBcYBkCdKgD[aDSD?sOAKC@cCASF@CI@[LA[IBKKBCQA[NA[SA{LAcUA{HA{NAsMAkJAcNBCG@cF@KDBCEBKMCsTCkLCcGC{JC[FC[OB{HB{XBsQCKPBsPCKOCCECCUBkTBkMBcIB[DBS[CSYB[lDszID@IssGsnJKwHSoFK}GciH[tFkyI{qGlFJDGI\\AHl?Ik~IKrHsuH{vITHIdBHckFcjELYJ\\[JlgMLhLT]J|_KLjL|eK|aK\\kLtlMDcKk@MPr_HsMkAMpv_XyNkBNX{_PwNN')
X5 = Graph(':~?AC_C?_CE?kC_cE_kI`CF`KO@{N`sK`[LbGWa{UasWa{OaKTa[Qac_cSZbc^cc`c[]bkXbSw@wpb?t`?uaouawr__t_or_gpaOvagqcOsbwq`gb`oc`__aG]a?ZaW`b_\\bGYd?ve?vdgsdoq_wfdGrd_udOtdWpcws`Gm`Oo`Wed?jd_ncohdOlcgnacdJtKJ{|IK~ITMH|IJDCG{wFL?GSzFd@JtHH\\DHDBHlTJk}IdEItXJdYJ[yI\\OI|_KLaK\\kMTlLteK|nM\\oMLgLLiL\\cKk@M`t_XuM{AN@z_PxNSBNk@NaA')
X6 = Graph(':~?AC_C?_CD?cCcO`c__C[^C[\\boeawWbG[bOZaSF@KRAcL@sIBSdcKK@{JA{UB[PBkTBCOBK[BsECCD@CFAKG@scECRAsJBKQBSKCKWBsGAkH@[IEKSC[LC{NASOAKEAsjaWg`oec?a`Gaa@JagZ`g^a_[`w\\`_^_gFdGi`OV_dVJLWJKjFSpFCoE[sEkkDkvFKqEsmD{}GKzGS|GC{F|DHLCHDFHTBGtLHtJHdOITNILTItRId[Jl_K\\`KT]J|cK|dKtgL\\hLTmL|kLlZMLYMC@MPt_HrMcBN@x_PuM{BNX|_PyNf')
X7 = Graph(':~?AC_C?_CD?cF?kFaWQbGIas[BS]BCK@kLA[W`cXBkSbkgAciCKkAoe__Eawe`?WbGY_oZ_oI_wH`wPawacWhcgjag]agccwh`GMaoc`WO`Wdc?``{LaCaDCZD[PASQCsgDSI@sfaGT`@H`WKdKkGKHD[iGCDAcZC{NBcRBkMACVBs[B|AHkCixXj@Xdgmfp?fX@fGyeWseG~f_|eguePIhhOhpNhXKgpHgxGgPDgXCewwdwoiHSiPRitTMDcK|dKt[Jl]J|_K\\`KTiL\\gLLnMLmMDZLlYLc@MPr_PsMkBMpv_XxNkAN@{_HyN^')
X8 = Graph(':~?AC_C?_CaCKcC[XbOdbW[bw_bg]aCIDSJbOk__e__W__Lcgf_gE`?H_wO_wP`GIa_W`oN`gV`_QaWSaWV`WT`gT`WM`oR_oN_oW_gV_wb`wXc_h_gYag`a_acOg`G_`O\\ao^aG]`_]ao\\aG_aO^a?Z`?[ao[`_ZaOc`?bbG`g`XgXOfxUdxJdpEg@Wh@IePRdOpf`PfhKgPVeXFe?sf@LepDd_texTdhQdWzfGyfpShHNgHMjPZj`\\lxpl`ljp^k@`lHmlPjkPbkpokxgk`d_HqM[@M`t_PuM{BNP|_XzNcAN@x')
X9 = Graph(':~?AC_C?_C]@OJ`oNa?QaGRao\\agVa_YbGZb?[`cLcwgdwI`on`{OaGpb_kbgk`giawmbWmb?laolbGjagjaOi_oq`OS`WN`WO`_Y`oRaGYaORbwgc?ccgecOb`?`_wK_wZ_wU`GV`GW`?\\`?X_oh`G]_of__L_g[_gT__S__DhPXhXRgpHgxGe`SexDfPWfX?e@KepNg`Oeh@f@Tf`AfHBeHUiHQfxMfhLePVdordg}d_ndOjjPZj`\\m@plpnjp^k@`kPlkXckhelHklPjkxg_HqM[@M`t_PuM{BNP|_XzNcAN@x')
X10 = Graph(':~?AC_C?_CN@s_B?Zb_\\bO^bG]aCPCcVaSRacTaoicogcwhe?ZD{kDsIDsED{PBkQBsRBK\\B{XBSNACMASPDSOCsWCcjDkbCkaDK_C{`DCCA[CAkGA{HAsEAsFA{LAcFAkDAcJB{JBCDBcKBsHBcIBSGB[E@{C@sJ@cD?{K@kG@kH@SpIkzFswISxHs{GCoGdNICqFSuG|LItKIdDGs~H[mD|IILRI{tHDBHL@GSsJC|e|XLsrL|YJ\\[JliMLjMD]L|^KD`LlaK\\cKlkLtgLLeK{@MPr_HsMkAMpv_XyNkBNX{_PwNN')
X11 = Graph(':~?AC_C?_CD?cC`_Fa?GaWPagG@{JaKE@sL`SM`K^Bs`CCL`[HbkVacIaSOasNaSKacR_keC{REKYEKQCkSBsL@sH@S[CCTBKeDCkECiD{FBKcDSPB[^CCNACVCKKAslECmD{[BkaDkbCcgDKjDc\\C{^DKYDsWD[E@[D@C]cSbIS`I[dbXU_cFj@XhhXePWh@HhpVgHAehPgXCeovfHOghEfOzfpFeXQe`Rfx?hPNhXKfC{LdSilULs|L|[Jl]J|iMLeK|_KLaLdbKddLtYLlgL\\ZLLnMC@MPr_HsMkAMpv_XwNKANP|_XzNf')
X12 = Graph(':~?AC_C?_CE?kEcO\\cSYBcZbs_Ck^CsXCKWC[C?kK@kF@CMBKOASRBsg`SaaGSag[`WY`wVao`bW_`GW__R_gV`?^`?SdGr`Op`GJ`O_aGV`_Oag\\`oT`GQbO`aWd`_b_wfacJ@kUBkPBsL@sQAsNB[ECceDSNB{OBcqHcWBKCj@XixXdWkeGwfGye_tdgmeWveOudwofXDfxBgPCfh@g@EfpIh@Hf`FhhNhXMi@Qh`PihUiXSj`\\k@bkHajp^k`fkhel@jlHilpnl`ljXpjPo_HqMk@MXs_XwNKAMpv_XzNkANP{')
X13 = Graph(':~?AC_C?_CD?cC`WH`SN@SHaCN`sL`oO`gN`cJbgJ`c]bk[BkZBsRBSSBKWa{UakQaKYbKZDc[D[F`CF`C`cSod{qeKkd[iEShEKeD{dECgDkfDs_Cc^C\\AgK}fkzfcuekyGCxF{sFCrE|Cg\\JhdGHTFHLEHtDHkDI@T_pNIsEIPS_hPI[H@SFBSGBKVEkWEsPFCQE{iFShFKrEcMHSLHKgGsfGkeGcdG[_HC^G{[ISZIKSICRH{Ck`pjXpj`\\lXkkxgkhekXikPhkHok@njxmjpl_HrMc@Mhu_PqM{BNX|_XyNcAN@x')

# List of graphs to process

graphs = [('X%d' % i, globals()['X%d' % i]) for i in range(1 ,14 )]


def check_all_isomorphisms(graph_list):
    n = len(graph_list)
    print("\nIsomorphism check of all pairs (a dot means non isomorphic):")
    for i in range(n):
        label_i, G_i = graph_list[i]
        for j in range(i + 1, n):
            label_j, G_j = graph_list[j]
            if G_i.is_isomorphic(G_j):
                print(f"\n{label_i} is isomorphic to {label_j}")
            else:
                print(".", end="")
    print()  # Newline at the end

def count_k_cycles(G, k):
    count = 0
    visited = set()
    def dfs(path, start, depth):
        nonlocal count
        current = path[-1]
        # Early exit if we?re going too deep
        if depth == k:
            if start in G.neighbors(current):
                # Normalize to avoid duplicates
                cycle = tuple(sorted(path))
                if cycle not in visited:
                    visited.add(cycle)
                    count += 1
            return
        for neighbor in G.neighbors(current):
            if neighbor not in path and neighbor >= start:
                dfs(path + [neighbor], start, depth + 1)
    for v in G.vertices():
        dfs([v], v, 1)
    return count   # each cycle counted twice (once forward, once reverse)

def algebraic_connectivity(G):
    """
    Compute the algebraic connectivity (Fiedler value) of a graph G.
    INPUT:
        - G: a SageMath Graph
    OUTPUT:
        - The second-smallest eigenvalue of the Laplacian matrix of G
    """
    L = G.laplacian_matrix()
    eigenvalues = L.eigenvalues()
    eigenvalues.sort()
    
    if len(eigenvalues) < 2:
        return 0  # Trivial case: empty or isolated vertex graph
    return eigenvalues[1]


def domination_number(G):
    """
    Compute the domination number of a graph G using MILP.
    INPUT:
        - G: a SageMath Graph
    OUTPUT:
        - The domination number (integer)
    """
    p = MixedIntegerLinearProgram(maximization=False)
    x = p.new_variable(binary=True)   
    # Objective: minimize the number of chosen vertices
    p.set_objective(sum(x[v] for v in G.vertices()))
    # Constraint: each vertex is dominated
    for v in G.vertices():
        p.add_constraint(x[v] + sum(x[u] for u in G.neighbors(v)) >= 1)
    return p.solve()


# Print properties for each graph in the list
print("\nMain properties of the graphs\n")
for label, graph in graphs:
    print(f"{label} | Ord.: {graph.order()} / Size: {graph.size()} / 3reg.? {graph.is_regular(k=3)} "
          f" / Girth: {graph.girth()} / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} ") #/ Alg.conn. {algebraic_connectivity(graph).n(digits=6)}  Dom.num.: {domination_number(graph)}")

print("\nSymmetry properties of the graphs\n")
for label, graph in graphs:
    print(f"{label} | Aut.group.ord.: {graph.automorphism_group().order()} /  Cayley ? {graph.is_cayley()} -- vtx.trans. ? {graph.is_vertex_transitive()} -- edge.trans. ? {graph.is_edge_transitive()}" )

# Check isomorphisms
# print(f"Are isomorphic G5 and G6? {G5.is_isomorphic(G6)}")

check_all_isomorphisms(graphs)

# Compute the distance distribution from a given vertex v in graph G
# Returns a list where the i-th element is the number of vertices at distance i from v
def distance_distribution(G, v):
    from collections import Counter    
    distances = G.shortest_path_lengths(v)
    distribution = Counter(distances.values())
    result = [distribution[d] for d in sorted(distribution)]    
    return result

print("\nDistance distribution from vertex 0")
for label, graph in graphs:
    print(f"{label} distance distrib: {distance_distribution(graph, 0)}")


# Counting k-cycles for each graph
print("\nNumber of k-cycles for k=3 up to 10")
for label, graph in graphs:
    print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 11)))
    

for i in range(1,14):
    nx.write_adjlist(globals()['X%d' % i].networkx_graph(), 'X%d_adjlist.txt' % i)

# from 1
'''        
for label, _ in graphs:
    base = label.strip()   
    G = globals()[base + "nx"] 

    with open(f"{base}_Zedges.txt", "w") as f:
        f.write(",".join(
            f"{{{u+1},{v+1}}}"
            for u, v in sorted((min(u, v), max(u, v)) for u, v in G.edges())
        ))
'''       
    
print("\n")
##