# SageMathCell online  https://sagecell.sagemath.org/?q=eurdsl
#  Q'_8. (9,3)=585, Moore bound=658. Quotient of the incidence graph of a regular generalized quadrangle by a polarity.
#  FOund by C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302.
#  Ord.: 585 / Size: 2600   / Diam.: 3 / Avg.dist: 2.84932 
#  9-reg.? False / Degree histogram: [0, 0, 0, 0, 0, 0, 0, 0, 65, 520]  / Girth: 5/ Alg.conn. 5.00000 /  Domin. number: 65  
#  Aut.group.ord.: 87360 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False   
# 

import networkx as nx

del585=Graph(r":~?HH_@?A?C?G?O?_@?A?K?W?o@_B?E?K?W@OA_D?I?S?g@OA_F?M?[?w@oB_F?M?c@GAOC_H?Q?c@GAoD_J?U?k@WAoD_L?Y?s@gBOE_L?Y?{@wBoF_N?]?{@wCOG_P?a@CAGCOG_R?e@KAWCoH_R?e@SAgD@N_T?i@SAgDOJ_V?kICAwD`S_V?m@[BGE@P_WCq@cBGEOK_WD}@gTwEoLA\?u@kBOoOL_YEE@sB_voMAT?wKsB_koM_[DU@sBonONBH?{H[BowoN_]Eu@{BohOO__FYA?RWG@W__EiA?XwG@[__FuAGQWGaB_aFMAGSwG`z_aEmAGWwG`Z_cGCPKC_roQAZ@GJcC_}oQBl@GJCC_tORBD@KIsCofaT_eEeAW`@EoRC@@KJkCozoSBwHqA__`FOSASHaA_TWI@w_gE}A_XgI@X_iFUAg]PKoTA_HIAgYGI`mDN@SJSDPBaN_iDQAoVgJ@lDH@WHWdwJ@~Ct@WISD_qAo_kFEAoa@EOVAmJ]AwWGJ`MCl@[MSDooah_mGSP[DouAd_mFwSCE?wAg_oFOVSE?eAS_oGWQCE?noWAaJEB?]`NoWBIIyBGQPKoXCEJYBG]pHOXAuI]BG[pUOXBUKaBGWp]oXAeG}BOSPCoYBgImBOR@LoYBIJmBO]`HoYB_KMBOVpPbI_sGWU[EolAaER@kNGcWL`OCz@kI_agLaFDoLMBW\PVoZB[KQBWY@^O[BGJqB_ZP`O[AUI?Z{F@CAvEl@oMGiWM@]DIKyB_S`Do[B}HYBg`PYbT_yE?S_qwM`MCsLiBg^`Jo\BWKW\CFOjaK_yECVKFOxAo_{FWTsF_ray_{CsRwwGN@iEIMEBoU@GO]CAJCYcF_}aSF^@wJ_i@fo^B]K[[{Fp@AsEb@{HOf`mO^AqICYCForB?Fj@{N_dPvO^BoIiBwTPEo_C?H_]CG?jAMF~A?Hwf@nO_BmIuC?VPRBL`?EGVw{WOACDcLIC?YP_bd`ACcSGwWO`zEMK}CG[pEbS`AGKW@@gO`jCiMACGUpNBn`ADKTO{gO`bDgNuCO[PCbQ`CF{WWrWPAGDuOQCOQpPbd`CEOUW~wP@QDUNECOV`Lbo`CEsQWvaFObBsKGXKGpBA{GFAKKglp|obAWIS[[GogahFfAKJwg@tcU`EF?QouqFobBgGkY[H?uASEwOeC_[`GBP`GFwWgsGQ@MDOM]C_`P\CA`GECUH?GQ@VD[NSbcH?oA^F[PQCgVPMblGjASLGcPncO`IF[POtgQ`NDCMGcsHP?BCE\ASO_naCOdBCJ_^KHOjAnFgPmCoX`ZB}H\AWIgj@zcY`KDcRGzAHoeASI[\@HWR@nCcLg`cH_{ANEjAWN_q@doeCCJs_KHpBa~GMR]CwY@XByHZA[I_jPzCX`MD?SoxAPofAsHo\HCgR`mCoLs`SHoyaMEpA[NGoPdOgAoJ?^@GGS@[CsMgaKI?tAVEqOmD?RPQBeHDA_Mob@jogByKWX`NwSA@DqOSesI?ratFwQmDGQPSbhHRAcLWlpdC]`QGKWO}aJohBuJoZhOgS`RDIL_`sIOpaUGMQaDG[pOBuHzAcJWapqCr`SDcPGwaXOiBoHk]`MwT@eCeO_cxRGT@IDUMseCI_varE[PuDOTPPbUG^AgOOop{cU`SFoVWvq_ojBSJGXHEwT`|D}Lkh@SWT`WDKLKaCIoealFUQ}DW\`MBrHtAkJ_b`pcp`UE[R@?qRDO`UGCWG}qIokAgIOY`AWU@mDiK{bcJ@BbEFyPQD_S@WBnHXAoJOb@ocsJ@AoL?dqBCcIVAoNGmPoDCInAoMge`xC{`YESQh@QQdH`YD{Pgxa[D[`YFgW?uQbdS`YCoTOyaVOlAaICYxBGUaEEMNoaXXGU`sC{N_fKJOwAsEWPiDo^`^B]IKTYDoWPGcCHESuDoZ@[BLGrAwHojpwClJZAwOgp@~cQJBAwMOfPwd?`[E?POxQZdZ`[D[SOsaDOnBmH{]xNwVaCEINwaHWgV`\C_M_epUWV`ND[ModX[GVa?DsLgghTWV`hDaKkcCJojAgEiOkm[JopASGAQGhSK@CBGG?P_lCK?hAfEaOsmsK?waXFiRyE?QpUBmHSU}E?X@HCAHAS}E?^p]b[IETIE?ZPZBOG}VeE?V`FbfHiTuEGQPWbpHaVEEGWpSB]GiVuEGSpIBdHsUmEG[paboG_TiEGUp\BQH]WYEGYpVB~IOSqEG_pNbLHKTaEG]pGCCGuU]EO]PCcAGsUIEOU`\bPH[W]EO\P`bmGWTeEOS@XbtHoVMEOZ`Tc?IMSiEOY@Pb[GeVyEOT@HbfHqV?pcK`BaZE_QSikKp@AYEQQKi[KovaoFuSWhsKo}AKGEPcksKodAtFeR[mSKo{BEFUOgjxcgX`TCmMKg@YREorAqJcYXJRAorBKIOZXCb?OsBgKO\`AQmeT`gDCQGyA]DnK\BOM?jp~DCI^BOH_m@zcsJlBOJwn`ickKEXiE_``MbJHGTIE_XPPBYGgVeE_]`DC@GwUaEgZPUb|IIScssLOqAeF?PCncLOnA~EgQko`eWY`JDcNGep\GY`QCoMCfxZBFotB}Gw_pGAqOtCOHoXxGaiOtBaKC\xAqmEW`kDWQoxa^DmKRBWO?aqAc^JFBWKOhPkcWJtBWHwlp{CtJjBWO_g@eC`ImYqEoYPSb{IESkscL_zbAFSOsk@dGZ@\DwL[dP_RMOvBMI[ZxDq~ovBkK_\hBaleP`mGCRGraSDUL\B[Hgl`yCrJoZIEw^PFcGG{UEEwV@]bUHQWGr[LotAkFqSGhhiGZ`WCcMGfhZRGOwB?K?Z@KBCE_`oGSRoqaRdPLTB_IwdPqCzJSWiF?R`YBuHcV[u[M?oa`EyPWn[M?xBFFQO{jpdg[@}CYO[bhXR[owBWIg^POQgEf`qCcVG}Q[dxLrBcKWe`pDFJkXYFGUpYcGGWTGs{MO|aoEkQSjhkw[`REKL{f@RrTOxBUGo]`Cqve_`qGKS_zQLEBKTBcMWdpfCmJO[UFOYPCbqGcUgrSM_marGKOgiHgw\ACDEM{bHaBFOyA]Jk^hOA|e~`sEGRWwQbDvKjBgIoopoCvI_YeFO\pHbNHYUSxCM`?AjEgQKjplbfozBcHGXHIqpfB`uEoPw{qGdmK|BkKGePpdDJiX]FWR`]bzH}VgwCMojbGEuRWhXjW\`_DkOK`XTrPOzB{IoYXGaoEpMVBkOghptc_KAWkySN?mAsGGOcihhRmo{AoK[ZpLAdEj`wFsTOsaQDXLo[uF_RP_B~HwVwvsN@?a`F_PooxbRjO{BMHw[hPAxeQ`wEgPg{QIDoK~BoModPeckJC[EFgTPab\HiSctpxg]`eC}MOgX\BGo|BoHOXPIaqFF`yCgVO}a^D{LzBsN_j`kC`IwZGxSNP@AgFQP{o`cBio|AqJC_xBQiEgMvBsLwc@zCWJWXmFo``RBmG{WWpHtw^@yDYLCd@UbYFO`{D{UP?aFDWLG\eFoR@^c?HyVsvcN_wAMFiP[lXfG^@sCoL?dHXraO}BIHo[xOaweSNVBwIGoPmCrIWYo|CNo~anEmQ[jxlrco~BaHCX`KArFENhB{IOp@kcqI[Z?{cNoda}FwRko@mg^`]DoOS`xSrOf[`}EsPO}AJDhKzB{P?g`tC\KIWoycNoqA\FKSCmPcruP?BOI?\@QA{EWN`C?OwhPuCZKCW{yKO?vAJFmPSlheW_@ODwNwfP^r\f}a?FSQoqqVd`MC^UG?]PSbTHKTkuhrg_@SECLgeHRRVffa?DgUx?QGDULK\iGGQP_c@IAWCwI?W_`ZCoNwbh\RTfIaADKVwqqJD_LI]iGG_pUbgG]Vgrx|w_`bC[MofXTr[FeaAEkR_tQXDbKY_AGG]pRBvH_SkqPuw_`rDcLgcxZb^FTaCECPGya\DQLc]IGO^`PbwH]S{qHvW`@qDeLccpZr]fUOXCGHooqAdGKE[\?{O_oARFwPkmpjbepAAmJkX`DQmegNRCGL_epjcpJOX?~[O`AajFKP?nHer{PBAcJgXHCqlebNVCKP?j`pcKJ}Xg}qCW``~DONKdpRRIfXaECkWh?qbeAMO_UGWZPNbRHoUCpp}g``]CgNkbP]BSfOaEFCUGuqQdlL}\\@kOoqAOFURciplbsPCCGIo[`AQ}e\Ni`UG_\pZB\HGUkvPsSDPCBQHcZ@LAreKN|COHwqABdCKK[X?[P?jA|ESPOjPgRwPCBCG{\HNAkEvNM`yG_VPHByGwVCu@rgaA?DMNWd`RBHfYaIFsSg|QUdHKk\yGgY`OBPHmUOpP~Wa`[CkO?bH\BTFJPFCSHgoa@DEKG[T@CPOraJF[S?i`krog\aIGCTGxqDD{L?^LA{POkA{E_PGj`hrvpDBkJ[Z`GquExMc_yGoZ`NBUHkUWpH~sVpEAgK?XpCQnecN\CWL?bPuc~IeZO{iEWb@OEMO_gh`RaGAaKFcSG|ATdMKg]AGo\PYB^HCUcv`ssDpECMIg[PAr?E[Na`YGoU`IbxH?VGt`rsQpFA}H[^xFqzenMQaaGwXPEBoH{TCuhxCLpFCKJ?[hBQ|eXNg`IGwR@bCCIEW_wQ@Gb`sDiLwcHYb\fSO^C[M?e`hCtJIW{~aIWb`yDGNCdPSBKF[aMDCVGrQKD]LK]pEkQ?{AwF?Q_m@oBkGHaODcQG~QNDrLY[pCcQ?ia}E]P[jHgbugsaOCgW`@a`EFME_YH?_`Vb`G[Vwrp{cIPGBwIG]PIQdEVM}bqH?X`DBnHyTSuHwsMPGB]HsY`KqpEJNqar~~~~~~~")
         
del585nx = del585.networkx_graph()

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


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" / 9-reg.? {graph.is_regular(k=9)} / Degree histogram: {nx.degree_histogram(del585nx)}  / 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} | Aut.group.ord.: {graph.automorphism_group().order()} /  Cayley ? {graph.is_cayley()} ---  vtx.trans. ? {graph.is_vertex_transitive()} -- edge.trans. ? {graph.is_edge_transitive()}" )


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

print("\n")

##
#