# SageMathCell online https://sagecell.sagemath.org/?q=bymyuo
# 
#  (6,5) = 1404; Moore bound=4687
#  Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
#  E. Loz, J. ?irá?. New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2008), 63?80.
# 
# Ord.: 1404 / Size: 4212   / Diam.: 5 / Avg.dist: 4.27655   
# 6-reg.? True / Degree histogram: [0, 0, 0, 0, 0, 0, 1404]  / Girth: 6
# Aut.group.ord.: 702 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False
#  

import networkx as nx

loz1404 = Graph(r":~?T{_?_?_?_?_?_?_G?F_F_F_F_F_F_N?M_M_M_M_M_M_U?T_T_T_T_T_T_\?[_[_[_[_[_[_c?b_b_b_b_b_b_j?i_i_i_i_i_i_q?p_p_p_p_p_p_x?w_w_w_w_w_w`??~_~_~_~_~_~`F@E`E`E`E`E`E`M@L`L`L`L`L`L`T@S`S`S`S`S`S`[@Z`Z`Z`Z`Z`Z`b@a`a`a`a`a`a`i@h`h`h`h`h`h`p@o`o`o`o`o`o`w@v`v`v`v`v`v`~@}`}`}`}`}`}aEADaDaDaDaDaDaLAKaK_SAKaKaKaKaSARaRaRaRaRaRaZAYaYaYaYaYaYaaA`a`_hA`a`a`a`ahAgagagag_GAg_PAgao?KAnananananan_@_@?}_@_@?N_@?]a{Azazazaz_\Az_eAzbB?`BAbAbAbAbAbA_U_U@R_U_U?c_H?UbNBMbMbMbM_qBM_zBMbU?uBTbTbTbTbTbT_j_j@g_j_j?x_j@GbaB`b`b`b``FB``OB`bh@JBgbgbgbgbgbg`?`?@|`?`?@M_r@?btBsbs_GBsbs`[Bs`dBsb{?_@_Bzbzbzbzbzbz`T`TAQ_H?c@T`T@b`T@qcGCFcF_\CFcF`pCF`yCFcN?J@tCMcMcMcMcMcM`i`iAf_N?]@i`i@w`\@icZCYcY_qCYcYaECYaNCYca@IAIC`c`c`c`c`c``~`~Ay_r@M@~`~AL`~A[cmClcl`FClclaZClacClct?tA^CscscscscscsaSaSBL_x@GASaSAaaFAS_Kd?d?`[D?d?avD?dF@sAsDEdEdEdEdE_PDEahahB_`\@wAh_QAhAuahBC_`dQdQ`pDQdQbIDQdX@^BFDWdWdWdWdW_eDWa{a{Br`b@qA{_fA{BHapA{_udcdcaEDcdcb\DcdjA]BYDididididi_zDibNbNCEaFAaBN_{BNB[bNBi`JduduaZDuduboDud|AHBlD{d{d{d{d{`OD{babaCXaLA[Ba`PBaBnbVBa`_eGeGaoEGeGcBEGeNBEC?EMeMeM_CEM__EM`dEMbtbtCkapBHBt`eBtCAbtCO`teYeYbBEYeYcUEYe`ArCRE_e_e__XE__JE_`yE_cGcGC~auBCCG`zCGCTb|CGaIekekbUEk_DEkchEk_SbkCeEqeqeq_mEq`IEqcZcZDP_WBVBnCZaOCZCgcZCua^e|e|bhE|_YE|c{E|_hbXCxFBfBfB`BFB_tFBcmcmDb_BB[BiCmadCmCzcbCmasfMfMb{FM_nFMdMFM_}cQDJFSfS_AFS_N@WFS`sFS_ZD@d@Dt_A@AB|CTD@awD@DL_QD@DYbFf^f^cNF^`CF^d_F^`Rb~D\Fdfd_VFd_c@lFd`^Fd_EDRdREF_V?lCACODRbJDRD^_fDGDRbYfofocaFo`XFodqFo`gcwDnFufu_kFu_xAAFua]Fu`DDd_IDdEX_k@kCbCzDdb]DdDp_{DdD}blg@g@ctG@`mG@eCG@`|cdE@GFgF`@GF`MAVGFaHGF_oDv_^DvEj`@@VCgCuDvbpDvEB`PDkDvc?gQgQdFGQ_ZABGQeUGQaQd[ERGWgW`UGW`bAkGWbEGW`nEH_sEHE{`UAUDGD^EH_XCCEHET`eEHEacRgbgbdXGb_EAWGbegGbafdIEdGhgh`jGh`wA~GharGh`YEZ`HEZFL`jA@DLDYEZ_CCVEZEf`zEOEZcegs_XGsdjGs`DAlGsexGsaye?EvGygya?GyaLBQGybkGyaXEl_V@]ElF]a?A}DkEBEl`BCiElEwaOElFDcxhD_CHDd|HD_oB?HDfIHDbLdmFGHJhJaTHJaaBdHJbXHJaCE}_A@rE}FnaTAjDpD}E}_mC|E}FHadEsE}dJhU`BHUeNHU`nBRHUfZHUb_ecFXH[h[aiH[auBwH[cQH[b@FN`@AGFNG?aiBcEOEfFN`lDNFNFYawFNFfd\hf_mHfe`Hf`YBeHffkHfbreQFiHlhla|HlbHCJHlb~HlamF__kA\F_GPa|BPETEaF_`WD`F_FjbJFUF__IDnhw`lHwerHwaXBxHwcE_RFFFzH|h|bOH|b[C]H|cwH|bfFp`jAqFpGa_YBOCIEsFHFpaVDrFpF{b]FpGH_^E@iG`WIGfCIGaCCKIGcX_gEuGKILiLbbILbnCpILcdILbSGA`UBDGAGr_DBbBvEwFDGAaAEDGAGLbpFwGA_sERiWaVIWfTIWb@C^IWck_|FhG\I\i\_aBuI\cADCI\d[I\cLGR_]ATBWGRHC`CBuCoFUFjGRa~EVGRG]cCGRGj`HEdigaAIgfeIgamCqIgc~`QFWGmIlil_LCHIlcTDUIldIIlbyGc_HA?BjGcHT_nCHC\FYFfGcakEhGcGncVGYGc`]Ev_WIwa~Iw_AFvIw_KBfIwdP`fGJG~I|_B?LI|`KC[I|cgDgI|e?I|crGt`GA|B}GtHe`mC[DTFwGLGtbdEyGtH?_dCiGtHL`rFG_BJGakJG_VGGJG_`BSJGdb`{FyHOJL_W?aJL_vCnJLczDyJLdmJLc_HE_rAiCPHEHv`XCnDBF{GHHEbQFJHEHP_OC|G{HEaGFX`AJWbdJW_R?kGXJW_c?uCLJWdtaPGlH`J\_l?vJ\`uDAJ\_dDLEKJ\ecJ\dVHV`qBbCcHVIFaWDADxGYGnHVcJF[HVHa`NDNHVHna\Fi_lJgbQJg_g@@GiJg_N@JByJgeFaeG[HqJl`A@KJl``DSJl_OD^E]JleQJldDHg`\BOCvHgIVaBDSDfG]GjHgbwFlHgHr_yD`H]HgaqFz_Y@kJwcJJw_|@UGzJw`M@_CrJweXaxHNIAJ|`V@`J|a_DeJ|`NDpEoJ|fFJ|_YDzHxa[CHDHHxIfb?DeE\G{HPHx_dCpF}HxIB`xDrHxINbDGK_D@VKGbwKG`Q@jHKKG_x@tC_KGejbKG}IQKL`k@uKLaJDwKL_yEBF@KLeuKL_DDhIHaFBuDZIHIvalDwEJH?HLIH_OC]GNIHIR`cEDH~IHbWG\`CAUKWcpKW`fA?H\KW`wAIDVKWe{b^HpIaK\a@AJK\bGEIK\`xETFQK\fhK\`CE^IXbCCnDlIXJFbeEIF?H]HrIX`NDUG_IXIbabEVIXInbjGm_nA@Kgc]Kg`{ATHmKg`bA^DDKgfLbqH_IqKlaUA_KlatE[Kl`cEfFbKlfWKl_nELIhapC[D~IhJVbRE[EnHaHnIh_yDCGpIhIraMEhI^Ihb}G~`mA}Kw_JDUKwaPAiH}KwaaAsDzKwf]cDIPJAK|ajAtK|bmEmK|abEwFsK|gJK|`mFAIxbiDSEPIxJfcKEmFaH~IRIx`xDyHAIxJBcPHO`XAjLF__DCLFaeA|IMLFaLBFDhLFfncWI@JQLKa}BGLKbZE~LKaMFHGDLKfyLK`XEpJHbVDAEbJHJvbxE~FPIBINJH`cDgHRJHJRccH`aWBcLU_tDyLU__AxBOI]LUbHBYE^LU_ZG?cjIpJaLZbPBZLZcSFOLZglLZaWFcJXcODwEtJXKFcqFOGCI^IrJXabE]HcJXJbcvHqaBBPLc`IDgLc_JBKBbImLcauBlELLc_EGPc}I`JqLhbcBmLhc@F`Lhg[LhaBFRJhb|DeFEJhKVc^F`FrIbInJhaMEKHtJhJr_\DHIA`^E]Lq`IB^BuI}LqbnC?FALq`DGadOJPKALubvC@LucyFqLuhNLub?GEJxcuE[FVJxKf_`FqGeI~JRJx_GDZIQ`sEKL}_tBqCHJML}b[CREpL}_oGrdaJ@KQMAcICSMAcfGBMAg}MAalFtKHcbEIFgKHKv_KGBGTJBJNKH`FDlIaaHF@MI`sCDC[J]MIcTCeFcMI`nHCdsJpKaMMc\CfMMd]GSMMhpMMbeGgKX_WDYE~FxKX`JGSHGJ^JrKX_qD~Iqa]EoMU`^CWCnJmMUcACxFRMU`YHTeEJ`KqMYcoCyMYdKGdMYh_MYbRGVKh_BDGEmGIKh_uGdGvJbJnKh`pEPJAarFbMaa]CjDAJ}MaczDJGEMaaXHeeWKPLAMedBDKMeeAGuMeiPMecKHIKx`AD}F`GZKx`tGuHiJ~KRKx`[EbJQbEFQMmaHC}DSKMMmcgD\FtMmaCHveiK@LPMqdTD]MqdoHFMqi@MqbxGxLG_lDkFOGkLG`_HFHXKBKNLGaZEtJabXGDMybEDODeK]Myd^DnGgMyb@IF_XEzKpL^M}_RDfDoM}eeHWM}ipM}cqHkLV`kEaGBG|LVa^HWIJK^KrLVaEFEJqbkFsNEarDaDwKmNEdLE@GVNEamIV_CFKK`LlNI_gDxEANIeSHhNIi`NIc^HZLd`VEOFqHMLdaIHhHzKbKnLdbBFVKA_fB~GfNQbkDsEIK}NQeBERHINQbfIf`BF\LOLyNU_J?|EJESNU_hHyNUjPNU_\AUFDGdH^_\BFHyIjK~LQaoFgKQ_QCQGUN\bXEEE[LLN\dpEdGxN\bSIv_mFmL@MEN`__@QE\EeN`_SIIN`j@N`_GA@EsGSHo_GAsIIIZLBLMbhFxKa`PCdHHNg_dCQEWEmL[Ng_HEfEvHkNgcLJF_E@lF~MQNk_S?t@fEnNk`RIYNk_LJpNk`FA}FfHFI?`FBlIYJJL\LmbUGIKq_{CwGwNr_OB~EiE~LiNr_]ETFGHZNrbyJV_Z@WGOM]Nv_h@I@{F?Nv_}IiNv_aJ`Nv_qAjFUGuIO_qBYIiIzL_LjcNGZLA_R@zDIHjN}`NCwEzFOLvN}_^?rFHFXN}crJf_oAVG`MiOA_}@^APFPOA`|IyOA_vKPOA`pBcGHHhI_`pCRIyJjLwMFb{GkLP_g@eD[HYOH_yCdFKF`MBOH_I@GEwFiOHc_Jv`DAAGqMuOL`R@sAeFaOL`gJIOL`KK@OL`[BPFwHWIo`[C?JIJZLzMCctG|L^_|AdDmIKOS`xD[F\FqMNOS`H@\FjFzOSdVKF`YA~HBNAOW`gAHAxFrOWafJYOW``KpOWaZCIGjIIJ?aZCxJYKJMOM^caHMLl`QAOE?H{O^`cDIFmGBMZO^_s@qFYGKO^dDKV`nAkHSNMOb`|A]BKGCObaQJiOb`uK`ObaEBvGYHyJOaECeJiJzMRM[dXH^Ly`fBJEQIkOiabE?F~GSMfOi`rAFGLG\OidzKfaCBdHdNYOmaQArB^GTOm_gBLJyOmaJLOOmbBCoHLIiJ_bBD\JyKjMgMvdFHoME`{AwEcI[OtaMDmGOGdMrOt`]A[F{GmOtdhKvaXBQHuNdOxafBEBqGeOx_RAyKIOxa_L@OxaoC\G{IYJoaoDJKIKZMjMs_XD|I?MQaPBpEuJKP?a\ApGnG~P?_WE^amCJIENoPBayBXCDGvPB`QBrKYPB_EAtPBbhDTHnJIK?bhE@KYLIN?NN_CDjIOM]aeB]FFI{PIaGBCG]HOPI_BELb@BwIUNzPLbLBkCWHGPL_|B_KiPL_ZBGPLbUDBH]IyKObUDnKiKzNBNK_N@BE`I_MibDBVHPH`PS`AFAbSCpIeOEPUb_B~CjHXPU`{CXKyPU_oBZPUcNDxINJiK__c?mENIoMuaqBiH?HqP[_lEpbfC]IuOPP]brCQC}HiP]`fCELHP]`DBmP]b{DfH~JYKo_x@lFCJ?NAbjB|HrIAPc`kFcbyDUJEO[PecECdDOHzPeaeC~LWPe`YC@PectE\InKIL?`M@WErJONMbWCOHaIQPk`VFRcLDCJUOfPmcXCwDaIJPmaPCkLePm`nCSPmcaEJI^JyLN`bAVFeJ_NYcPCbIRIaPsaUGEc_DyJeOqPuckDIDsIZPubKDbLrPuaCCfPudXF?JNKiL]`wAAFTJoNdb}CuIBIqP{a@FtcrDgJuO|P}c~D[EEIjP}axDPL~P}aXCyP}dFEnI~KYLkaLA~GGK?NocvDGIrJAQC_PA}GgdDE]KEPFQEdPDmEWIzQEbqEFMJQEd|FaJnLHLxaaAkFvKONzccDYIbJQQJ_eAjGVdVEKKUPPQLdbE?EiJJQLb^DtMVQLdjFPJ^KyMDauBdGiK_OEdZDkJRJaQQ_zBcHI_HDhF@KePYQSdtEQEzJZQScWEjMbQSe`GCKNLeMPbHBQGXKoOPdHD}JBJqQX`OBPGx_]DzEoKuPaQZeFEcFKJjQZcDEXMnQZeNFrJ~LWM\b[CJHKL?O[d~EOJrKAQ_`dCIHk_rELFbLEPiQaeXEuF\JzQac}FLMzQafCGeKnL~MhbnBwGzLNOfdlEaJbKQQf`yBvHZ`GE^FQLTPqQhejFFFmKJQhcjE{NFQherGTK^LrMtcACpHmL]OqebEsKRKaQm_^?fANCo`\EpGDLbPyQoe{FWF~KZQofeHGLMMVN@cTC]H\LkO|ePFDKBKqQs_I?QAcC\`qFAFsLpQAQufLFhGOKjQufTGvK~MJNLcgDUIMLxPFfEFUKrLAQy`H@PAvDT_P?YAFFRGfQ{f]FyG`KzQ{gGHiLjMnNXczDCH}MDPPetFfKbLPR?_s?{BIDB_D?eA[FcGURAfnGJGqLIRAfvHXL\MbNcdLDyImMPPYfgFwLQL^RE`r@zB\Dx_z@CApFtHHRGg?G[HBLXRGgiIJMCNFNnd^DgI]M\PafVGHLBLlRK`]@eBoDf_n@OBCGEGwRMgPGlHSLfRMgXHzLwMzNydpE]JMMhPigIGYLmLyRQa\AdCBE\`d@mBVGVHjRSgaG}HdLsRShKIjM[N]ODeBEKI}MtPqfxGjL_MERWaGAOCUEJ`X@yBiGgHYRYgrHNHuM?RYgzIZMONROOeTF@JmN@PygkG{MFMQR]bDBJChF?aNAWB|GxIKR_hCH_IEMKR_hmJJMsNsOZefEoJ]NLQAgZHLLzM]RcaqAwC{EnaBAcCOHIH{RehTHpIUMWReh\IzMgNhOe_PEwFbKMNXhMH]M^MiRibjBpDMFaavB?CbHZIkRkheI@IeMcRk_eFHFQJ}Ncg|HnMRMuRnbWB]D_FPalBICuHkI[RphvIPIuMoRp_zFYGDKmNnhoH~MvNARscPCVDqGC_IB\BeDGJKRuiFI`JEM{Ru`OFjFsK]Nyh^INMjNMRxb}CCECFr_^BRBoDYI{RziVIpJUNGRz`dF{GfLLODiOI^NNNYR}cvC|EUGe_sCBCKDkJkS?ifJ@JeNSS?`yGLGUK}OOi?InNBNdSBccCiEgGT`HBxCUD}J[SDivJPJuN^SD_LANG]HHLiOZ_dDZD`ExHG`]ChCqEOKKSH_aAcGnGwL[Oe_ODHDNFIGv`rC^C{EaJ{SK_vAvH?HjMBOp`ND~EDFZHi_`AGDMEsKkSN`KBIHPHYLvO{_yDlDrFkHX_KA\D_FDK[SQ``B\HaIKMZPE`xEbEhF|IJ`JAqDqFULJST`uBoHrH{MNPO`cEPEVGMHz_uBDECFfK{SWaJCBIBIkMrPXabFEFJG^Ij`tBWEUFwLgSZa_CUIRI[MfP`aMEtEyGoIZ`_BjEgGHLYS]atChIbJKNJPh_VA^B}ExGYM@bGC{IrI{M~Pp_AAICPFIGjLtbZDMJBJkNaPx`@BFCcFZG{MXbmD_JRJ[NVQ@_kAsCvFkHLMLc@DqJbKKNwQH`jBlDHF|H]MpcSECJrJ{NlQO`UBYDZGMHnMdcfEUKBKkOMQVaTCRDlG^H~NHcyEgKRK[OBQ]a?C?D~GoINM|dKExKbLJOcQda|CxEPH@I^N_d]FIKrK{OXQkaiCeEbHQInNT_fDoFZLBLgOybbD\EtHbI~Nu_QEAFkLQLYOnbODJFEHsJNNj`PESF|L_M@PMcHE@FVICJ^OK_{EeGMLmLtPCbuDnFgISJnO@_S@zG^LzMXP^cnEdFxIcJ~Oa_h@eGoMFMLPVc[ERGIIsKNOV_}AdH@MRMpPndSFGGZJCK^Ow`RAOHQM^MdPfdAEvGkJSKnOl`gBJHbMjNHP~dwFiG|JcK~PK`|AwHsMvM|PvdeFXHMJsLMPAaQBpICNBN_QMe[GKH^KCL\P\afB]ISNNNTQFeIFzHoKSLjPTe~GmI?KcLwPlemG\IOKsMCPdf`HOI_LCMOP|fOG~IoLRM[PtgBHqJ?L`MgQKfqH`JOLnMsQDgdIQJ_L{N?QYgSIAJoMGNKQRhFIqK?MSNWQgguIaKOM_NbQ`hhJQK_MkNmQthWJAKoMwNxQniIJqL?NCOCR@hyJaLNNOONQziiKQL]NZOYRLiYKALkNeOdRFjIKqLxNpOoRXiyKaMDN{OzRRjiLPMPOFPDRdjYLAM\OQPNR^kILlMhO\PWRojyL^MtOgP_RjkiMEN@OrPgRykYLyNLO}PoRtlHM]NXPGPwSCkyMQNcPQQ?R~_aLeMuNnPZQG_LLWMiNyPbQN`KL~NMODPjQU_vLrNAOOPrQ\`uMVNdOZPzQc``MJNYOeQBQja_MnNzOpQIQqaJMbNoO{QPQwbGNFOPPEQWQ}atMzOEPOQ^RCbmN]OfPXQeRIbZNRO[P`QlROcSNsO|PhQrRUc@NhOqPpQxR[cyOIPPPxQ~RacfN~PFQ@RDRgd]O_PaQHRJRmdKOTPYQORPRreAOuPqQVRVRwdoOjPiQ]R\R|eePJQAQdRbSAeSP@PyQkRhSF")


loz1404nx =loz1404.networkx_graph()

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


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" / 6-reg.? {graph.is_regular(k=6)} / Degree histogram: {nx.degree_histogram(loz1404nx)}  / 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. 200: {distance_distribution(graph, 200)}")
    print(f"{label} distance distrib from vtx. 500: {distance_distribution(graph, 500)}")
        
# 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")

##