# SageMathCell online  https://sagecell.sagemath.org/?q=zcbwcj
#  Q'_8d. (10,3)=650, Moore bound=911. 
#  Quotient of the incidence graph of a regular generalized quadrangle by a polarity with duplication of some vertices..
#  Found by C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302.
#  Ord.: 650 / Size: 3250   / Diam.: 3 / Avg.dist: 2.84253
#  10-reg.? True / Degree histogram: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 650]  / Girth: 4  
#  Aut.group.ord.: 87360 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False   
# 

import networkx as nx

del650=Graph(r":~?II_@?A?C?G?O?_@?A?C?G?o@_B?E?K?W?o@_A?G?W@?A_E?M?a?S?g@OA_D?I?S?g@oB_F?M?[?w@oB_H?Q?c@GAOC_H?Q?k@WAoD_J?U?k@WB?H_L?Y?oAgBOE_L?Y?{@wBoF_N?]?{@wCOG_P?a@CAGCOG_U@M@[AwDoJ_V?m@[AwEOK_Q?oISBGEOK_X?q@cBWEoLAf?u@gUGEoL_Z?u@sB_ioMA^?y@sBgFOMBH?y@wUwFoNAb?}@{BoqoN_S?{K{BoiOO__FYA?RWG@k__DyACC?koO_`@CK[COtOPA\@CNKCWG`s_aEYAGTgG`K_d@GNsC_gOQAx@GMKC_uoQBB@GOsCgI@KAh@OPkD?|oSAn@OOcD?xOSBR@OKCD@EoTCUHKQcDOuoTA`?cAgWWIaE_iFyAgVGI`p_iDAAoYGJ@YAz@WIOgWJ@o_kGwRCD_naHCx@WKSD_~oUCQH}Aw`PSoVCWHeAwRPQOVAr@[O?_WJ`u_mEqAwVgJ`uCV@_NkE@@Ae_oDKRsE?vOWBiJUB?VorOI?oHCRSE?kOWB\@cK[EOyAq_qCwS[EPCAIDN@cIsEOtA~_qFeBGc`JoXAl@gJWpwL@d_sDCSSE_|OYBMJaBObpJOYBeF_U[E`Bal_sFgU{Eozau_uFoX[Eofa__uH?R[Eol@c_uDSWKEp@ak_uEkLwnWL`c_wCoI_hgMALEL@oO_fgM@_DiKeB_]p\b?_wFGZSF?sbM_wD[RSF?oAGDj@sIgdGM`{Dt@sHwiGM`jB]KqBg_pNad_yF[YkFOqApEz@sQ?mp`bL_yH?W[F_n`eD_LqBo_`Mo]AeIgWCF_kATCx@wQGq@ro]ByJyBo\PjO]B[K}AWF_hai_}EgXgsgN`sEh@{HojPyO^CcK[\SAON`xDp@{KWkpoo^AkHYBwa@DAa_}FOYcG@FbDEQMeC?XPXB]`?DCSwzwOAFDFA?MW]@kB}`?DkQ{G?rbI`?FgV{G@Bab`AFwVkGOubJ`AD?T_|WO`pEmLk]{GOmAZ`AGkQWoPsO`CKI?_sGOoauFDACLgqpeoaBkLc^kG`EBCFJAGHgipVBp`CDwTwwwP@kEaOu@OG`Aa`GJAGO?_P[oaAqDsR?mwP@XCpAKPGhABobAsDsRHEGP`QDQNMCW^p]ObBCJOUwwGP`gE_OeCWb``Be`EF?YW}wP`~DxAOH_T@Vbv`GGOZGwgQ@zCoMaC_bPgc_`GFGQggPubt`GE?TWjaBOcAmJc`PCWQ@hEGPYC_[`Obt`IFcQ_xgQaGCSLS[CHPHBKG{QMCgR`Wbz`IEgWXEGQ`UDsOeCgWp?AgGEO]Cg\@NadFeQeCgWpSCFG|AWOWt@mOeC_KsYPFWR@jB]K[acH_farFrAWIgmADoeBGIs_PKgR@vDCN?]pIgR@{CkM]CoTP[CJ`MFKN?g@wcc`MFgRWxWRaFEmLk[[HogauFzA[PwqqMOfBMKCbHEgR`ZDyOsfKHoqakGIRACwSPZBZFzA_KOiaACp`OF?Rg|ATogB}HSR_ygS@QD_N_^xPGSAHEkMED?b`fca`OE_X@CabogAsDsVpBA[OgBOK_`@CgS`kEKP[hkIOkazE?O{e{IOnAeGEO_d{IOeatF{SMDG\`NBnHNAcO?_PLBh`QGSZOvgSaKE[PmDGb@fBZGvAgQGsAOdV_QAgLooaHdK`SD_V`BaZOiAeJOUw}a_oiA}EWTH?AVOiBiIO]PHWT@|CqMo\kI_n`rCCLKZkI`@BREyRyDWV@^cOHzAkKGhq?cl`UFCSWzaROI@UD?UO~A_OjB{H[\[IpBBWE}MOkCIpDaRESP{isIoubDEQPShSIo~AVFUMsgSJ?e@SDoO?hCJ?xBFEyRmD_bPiCRHeRUD_`@ebQFcUQD_TpXbkFYQeD_YP?aaHASY@OJ?|alG[TyD_W@JByIfAoLGg`_B^HASYDgV`IBwF}TIDg_@?agGWTqDgZ@NadHCSSl{JOeayGGS}Dg\``b`HsRyDgUPWbiHTAsP_tQHCq_QAsOgr@yDb`YGSX_|ApomBaKGZ`MGVAEE_N?]pYayomAwJOUwxqTomA_Jo_PRagOmB{Ic`XUwV@`CqNc`PSWV@lDGPsg`[wVAJCeLKa`KWV@`CqNciKJokAqFOQQDw\PabHFCReDwcPhBWGkRADwSp^cEIVA{JwX`JbvIgWUDwZ`Pc_ICS[lsJp@BIFiUWn[Jo}afGSPCjkJpGbWFGPWeCK?t`nDAP{gXZGW@cCoNoj@UR?oH@_GKYGzasdw`_C{LWmQ?dL`_DSTwyqRooC_LcahJrDOoBwIkTpCAlOoBmKOZwxAZooA]JcXH?QeopCMK{]XYA|OpBMHsbpGq_do`aFKN?q@oCu`aDCVp@qeES`aG{YpEAVEF`aFgTPAQoda`aESQgf@|dVK@BCJWhPWBeGaQUEGUpWBeHITAEO^pUCNJ@BGPotplcVHYWaEOW`Lb}IkVyEOS`]cBGOSgq{K`CbJF]U[lX]WX@oEALwbPNQwoqAsDsUoyQREZ`cE_S@Eq_Dl`cF?RwoPnC|`eHGZPEQLCsK\BKIolPqcgHWXyEW]PHaeGYT}EWR`\b?GIScqsKotA]GwR{mSKpCAIE[NCkh\gX`sEKMKf`ggX`bCsNsih_gX`xDKKS`hVwY@KAgKC`HSRKosBQJW]XKRROsBuL[ZX@qTd~`gE?XWxafDOL`BOMOnQKDiJ^BOPgj@oDCJwVuE_`@Lc]HER_pkL?ja_FuQKgPUrHOtCCHOb`LrCOtA}EWX_xQeep_SBSNgdPicDHMVyEgSp`cLIoTcr[LOyayGqPglHZWY`mDaNCdxhrTOtAoH{Sg~QlEVLlBSQGi@pdBJrBSLW^PicDHMVwpKL`EAfEwSCm{L_zA~GgU_mH\GZADCmPsepbGZ@LEIKc`XTrLOuC?GCZ@?aQeCLzBWJGgp{d`JCX?u{L_nBIFMSonhjwZ@kDcN?]pJbSouA{Kg[xRApEn`mFoYp?qCCcKC[AEwTPMb}IyXWvCLofbGG]TOrsLoqBNFQSkthkrbOvC_IgZpOabdu`mEkLwk@vcoLDB[OWdPMCZHqWyEw\p^CVG{UWmSM?yA{GkU[lXZBhOwBSJOUw|QUed`oEKY?yAdEmMJB_HooaDCPIkXqF?T`QBvJ?XKr@mW[AGCSHcc@NRDOwCcIc[POAkDwLBB_NGsqBCeKA[MF?c`SbaI?VaFGU_maaFwT{qhlG[aHCkP{f`aRFoxBOJK\pLBPoxAcDsWxCAie\`qGwTgvpqC~Ju\eFG[@[CTJIUwyCMO~bSGAQ_d``R^oxBCKsYOyqcejMPBcIOpq@cOIiXstSM_uatFgRKehiG\@}EsOOdH_B]OyCUHKSowQbDyMvBgI?paEDRL?YC{CM`BAYD[QGfX`w\@`E[Mgh@jBboyBaJkW@CaqDoMhBgJ_f`{B~I{XOvSM_xaECsQGfX`w\`dEaMo\hRrXFK`uG{TWj`mdDJi\]FWUpObyIwXCukMogbCG[TGrxwW\`fD]N?]PKbQFa`uFgZH?ATEBKK[EFW`pKC`HsRwpXyG\`rBoJcaXWqxfR`uE[Tw{aXEcLZBoH_T@dCQIsYG|CN?safFoN{lHfb_o{B?KSXHGaRduMfBoO_nptCGIEWG{KN?jbWFgT_jH[bjo{BcH[``JrJFK`wGsUP@AZelLeZUF_]pPb`IYWw}h}W]A?CGJ{\PJA`eANBBsM?dADCPH[XCwsA_]`aEEQ?ch\Rio|CUGwUH@aZEqLo[uFgS`eCUJAUGs`zg]`gDON[l@fr_O|AsDsYg|QjdrMlBsNwfpQbaIWWk~CNPCayFOSCoX`bqG?`yGwQWkQBCuLcZaFo]`NB[ISWcpx{w^@rBoHg`XJRIfI`{E[So}QrdjKy[IFoSPfCSJ?YK|{N_lbYF_NWipZblO}BIKW^@FQRDzM]\yFo`p\b?FMS?ohvr}OH@{G{Uh?a]ejLu_QFoXPbBVF}Pscp]rfo~BAKObpGqQDxMa`AFwV@kbrIgU[lheBkO~CKJc[pOabd}NK^yFwS@gcWIyY[tPzW^aJCeI{_xMRWevOPB{LgipVBzJKXkvkNowaWGQR?qxqreo~B{IC[@QrCFp`}DoKouPxcbIgUszCO?kbVEuNGihZBlgYa?EoT_}aqd{KwZo~KO@?A@D?LshHabzp?AYKkaXVrQfkN`C?OgnPuBlH}WC{@}w_AKDkO?f`jb\GFa?DwWHGQSCkJo\P@sO?zAZG[ROqXeBbp?BWGCR_j@|DdKwZqGGc@YAvGIRku@lCCp@CEJo[hPa~faNM_EGGX@`C[HQVonhsCEP@A]L?bHEanEeNVCCMweQEcrHiXGxCOOi@{DGMKh@XrEfsaAEkLwiP}dcKqZ|CCOOibRFaTKlxuSMP@B]FoS_wq\DGKY^QGOa@DA}FUSSo`xR|PABqHsZwxAfeKNkaiGOT`jBmIcVCm`vSKPAA[K{ahVB@ehMU]eGOWpcC^HSV[xqBw`@sCiHoa@KbGFHaCHGU@?Q\C}L]ZX?sO_tAiFwUKrPnbaG`aCCwXxDQmD|LQ]eGWZ`Ub}JSY?sHosQpBCaJK_XAA[EkLq_MGW\PDAUEIO{eHdBapBAeKsYPDqlegNSbUGW^PPB]I[T?ox{cTpBCCJ_\HPB?FbN~CKJ?t@vdPJ_\ozqEw``^BKK[bXIq|FQOZCKMgd`YCNHaXOwhtWa@KAgLKbXWrTfpPrCOK?hAJcyH{Xsz@}wa@VE_LweP`Rgg^PLCOPgn@~CiLE[kxiJWa@hCqOK`@VA|feOtCOMOiPsdQKQW{uyLwaACDgJ[`xRqvE|O\COLw]p`BnIIXS|`zSBpCBuKG\xPRBETNY_]GgXpIC@IuVW{ADcMpDCMJCa@RagDqLw`AGg]``bmIGXW|`{CCHDaIDCYhFqtElLe^\F{POqa^DIPSf@fblf}aIDkX_vpqCpKC\PBsPOx`wDOMkiHbb\GqaIG{VO~ATc}IqYGwyJgaaNDsNodXgbbfoOUay@OP_jBJEwQ{o@tSOPECcJs^HHrSFEPWa|H[P`CAIDkOkhh[B_GKaKCwYwuqMdhLW^`FkP_yAkFMT_jH`r[GpaKEKS@DAZe_LA\X?KP_{b@F_NWgXdBvGHQLCWLOepYCAHsTgnPxCMPEBSHk_PJAYdYJs]PBcPpFAzE?Ngc`hbcgjQ^C[Nwp`xDAIMXG|I?s`pFB_IW\_zQiELLkbUGwS`lC`JKZ?}qMs_pFAsDsXovQWD~M[aUGwY@LC?IyVonhxSLhXaMEGRpCq[eXMy^|FAQgbaHDiOwhXZr^FCOZC[KOf`~cRHqWWrHvR~pGCKJK`hRAuF@Oa`QH?U_walFIT[pPkrYgsaOECSPEQLCuKw\[~aVwc@OEgPol@jbyfxQ@C_LgdaAd`JCV_{IDSkPGCUHKV?~QQedMWadIKQ?mBLEcMKdp_RhgcaOFwWw{Q_eRKo]`?aPwc@pDYMSixabYf|PhCcMgipVBiIkWouaLcuPHAoLC[G}ALClKG\@C[QOvAWGGU?mxwbrgXQhCcIWuQPDfJUY{}aMgcaAD]OohP[QyE~OfCcNgp@yD?K_]l?iAsaPHCaJc^?~qREhMOa\ICQOn`eDAPGfhebkg?RBCcJ?hPgb`HYWOyAGsvPIBGIKb@NBNf[M{^hKcQ_t`nCmO[jx\RpgWQlCgQ?np|cgHWYOwiIcePIA]L_bpGqqeqNcbqHO^@abHFeR{qHycBHGaSF[SwxaieJLqbLFAXgdABDcOchHRaxfBM{_}HOTPdB_HgWKopscOhraSF_OWkaCdHIoVKwYBwda?CAK_]hPbJfnOScIHWV`McUHuXkzP~S@H_aUDcXwwaXctJ{[|CQ[gd`LEkOgc@XBFepNebyHWb@^BvHQY[tPqcSHMaUGSU@AaGdGJY[HAQ]wd`kCiHo_pVa{f^Omd]@GQozAiFOTKp@msWHhaUCsYo|aODcKeZC}YNn~~~")
             
     
del650nx = del650.networkx_graph()

# List of graphs to process
graphs = [('del650   ', del650 )]


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("\n Main properties of the graph\n")
for label, graph in graphs:
    print(f"{label} | Ord.: {graph.order()} / Size: {graph.size()}  "
          f" / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} \n"
          f" / 10-reg.? {graph.is_regular(k=10)} / Degree histogram: {nx.degree_histogram(del650nx)}  / Girth: {graph.girth()}\n ")
          # f" /  Alg.conn. {algebraic_connectivity(graph).n(digits=6)} /  Domin. number: {domination_number(graph)} ")

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


# 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("\n")
for label, graph in graphs:
    print(f"{label} distance distrib from vtx. 0: {distance_distribution(graph, 0)}")
    print(f"{label} distance distrib from vtx. 1: {distance_distribution(graph, 1)}")
    print(f"{label} distance distrib from vtx. 2: {distance_distribution(graph, 2)}")
    
# Counting k-cycles for each graph
print("\nNumber of k-cycles for k=3 up to 5")
for label, graph in graphs:
    print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 6)))

print("\n")

##

#