# SageMathCell online  https://sagecell.sagemath.org/?q=ebzadp
#  Q'8d+ (12,3)=786, Moore bound=1597. 
#  Quotient of the incidence graph of a regular generalized quadrangle by a polarity with duplication of some vertices.
#  Found by J. Gomez. Some new large (?,3) graphs. Networks 53 (2009).
#  Ord.: 786 / Size: 4716   / Diam.: 3 / Avg.dist: 2.83357
#  12-reg.? True / Degree histogram: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 786]  / Girth: 3  
#  
#  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False   
# 

import networkx as nx

gom786=Graph(r":~?KQ_@???K??@O??F???c??Ao?_@???o@oCO??K?e??@oCo??O?e?K?W?_G_B?E?K?W?o@?R?E?S?_BoA_D?I?S?g@OA?R?M?[?w@oB_F?M?[?oC_T_H?Q?c@GAOC_H?OBK@?C_T?~?S@[@WAoD_J?U?k@WA_H?k@{DC@gBOE?\?WBs@gBOE_L?]?{@wBoF_N?[GS@wC?__P?a@CA?LoG_OCi@CBO[OL_Z?u@kBWEoL_Y@y@gSwE`R_\?y@oUWFOM_\?y@sB_poMBF?}@wDGF`Y_^?{KKBwF`Z_^?{LKBoR?xBR@AA?VgG@U_`@?E[CGGOOB\@?F{C?zOOBl@CKcCWG`W_aBUAKCOvoP_aFIAGDwGa?_aGAASC`@oQAh@GM{C_sOQ_cEIAOLGH@@_cG}AOV@FoRBZ@KMkCoioRCP@KQCCp?oR@l@KJ{Cob`v_eHeAWeWI?v_gGuA_TpAoSBJ@ONsD?{OSBV@ONOdwIAEC|@ORsDoh`[Az@[PSDooOVCj@[N{DoyAO_mEiAwQ@DoVCIIAAw`POOWC{IWSwiGK@w_oD]B?YwKAV_oGuB?XWK@}D^@_IwlGK@VDh@cM[EOp`eBN@cJGlgK`yBz@cSGiwK_aCt@cL_ewKaM_qHgWKEPLB@_sHWV{E`Nak_sDOVKE_pOYC]HCQSE_\aB_sF]BOYGL?|BP@gOWqwLABCMKmBWbGLaRDx@kJOkwL`CBr@kOOrGL`hB_FEBWh@UoZBB@kNGtGL`xEh@oLkF@?bH_wDSVCF@Ka[CyJuB_Iono[BiLaB_aGMAdDT@oDG^pZO[A}L}B_VpgB^_yEOXowWM`n_yD_U{FObAH_yFGYKFPPAh_yG?Oo`pdO\CoKMBgL?tak_yGcR_yWM`oCQMeBo`@eo]CUM]BoT`Yo]DEIyBoV`lo]CgKIBo\_|`{El@wJWZgN@ZB[HEC?Som@\DxA?S?wGOATDfA?GwY`eO_CSLOZGugO@~FnA?M_]`tO_B?IsT{G?tBKFzA?LOr@}o`A{IaCGapho`AkJwXsGOz@zBwMaCGd@YAyDvACO_{wO`mEONmCGgpmo`A_EC\g~wOa[DELs`[GPPb\GVAGLG[?wbFFtAGQWkgP?mAsKACOWPAaoDbAGS_waBOaCWL]CO_`yOaBqMK\[G_lB?GbAGJOo@vcP`EFS\GzpwOb@IGC]SGoibBF[PUCWepQb`GRAKP?sWP`lESN}CWVpSobCqHoRglwP_jA{LECW_PBBqGtAKOGm`xCY`GIGZwx@qcG`GE{XG~GQ@WDyPAC_e@[OcC?GWOw|QOOcBGIiC_[`rOcCQLaC_e@[CAHNAOR?mARocAcDO]cHPEbU`IF_[{HOjbAGkQECgUo~BwFqPeCgXPVOdC{IWSwuqBodCmJSdSHOtbLG@ASN?xqWOdBoM[eCH`@buG~AWRwvaAOeAgKCW_pQHOeBOKW_KH_zblHfAWQolaSoeC]HCQOsgE?eBCImCoW`TcBI@AWKOiq_OfCsJcd[Hop`eBMIof{Hoka~GhA[PohpiofBWKkXws@~OfBeModpJwRa`EwOUCw^PGBpGzA[GO[`bCR`MGwYhPgRaMDuLSgsIOh`[AyKWbKIPIbuG@AcPOiqBohD?MshCIOtB@EGKSdSIOoBQH_R[fCIOyB]Hz@SDGY?s`iBUEoLgZ_vaEGVAcNwl`pcUHXAcNwl`lBbGlAgP?iAAcK`SHcR_fPxb}`SIS\@PaeDL`SDSX@FWT@tEyR}DOVphcnIVAgLgnaToiCAJOVOmqIDQ_kAgEO\@ZdH`SEsVpDqTd]`SEsUGnaTd]`UHO]O}gTabFQM{]@PWT`uBuFo[HMwT`UESPmDWZ`GBBHKTuDW`@ZcPGmP_i[IpDahGLAkJosQOcpJDAkJosQOcpIWTYD__@BAFDiPGhsJ?|AHD[OQD_UpKBwFqOED_OOkBLG~AoSOxqaOkBcLkg@OQ`OkBGLWeXXgU@nECQcjXWGU?{CWNKdHSWU@WEYP{l{J?kApEYOsbxZwU`kD]K?d@VGU`|DcPSicJPAaMD_JC`KJOkbFGsQGcX[WUaYE[NO^{JPObjIT?gDg[ppCx`YEKKoXpjcqJJAsEgh@yc|IvAsMWp@pCxJzAsMWwa[d|`[F[[?za^D{`[EGY_uPlCtJHAwL?nARckHYTiDoT@eC_J`AwOWkqGDP`[G{QGc`UcG`[HW]w~GV?nC}Mgg[J`NbiIEWeDofptDBKRA{S_zAceG`]FcZ`Ma|onBALSe`WwV`YEUK{Y@FAvOnBQF?MGnqQDX`]GGVHCqfonCWIo`XBQFOnCeNC^[JpHbpFuUgq[JpHbpFuVSq[K?qbWHkUeE?Yp]cdH[TaE?^`LawG]TAE?Tpcc]JZB?PgiaDOoCmNS^h?a@eQ`_HwSohprDFKNB?N?vpqBdHwVeE?bPTCIIYXiE?VPEaiGSXiAoK_h`[AyLCc`\wJ?qB}MC^XXwJ?qD?NGfPVaoda_kBGQgyPvboGeX]AoK_oBIGUOs`pSgJ?qCSKKe`cGJ?qBSIcb``GX@sDmKShHWAxoqBKFOUwrqcd_JfBKL?iALCaHEWMEWbpGaQD{RGpsKozasDsJkhP[bPorAgFgYXIA~OrCELs^xGQtDj`eEGX@AQhorC}NKfHVWXaUFOPSe@dgXaUFOPSoHdbWOrCkM_ahdbWOsB{Lo^PXQyOsCmMoaHDqKE\LRBOKgqpfbOGKTQE_TpiceJyW?oKL@Ea~HaWuE_]@[cKIIVCssL@NAeDMNCfXVGY@jDWMwbX_gY@jDWMwaxEr@OtBAH?XH@qfOtCCL{[_xQ?De`iDgZ@Ia|OtBQF?MGiaKeDLrBSNGmAcDnJiVWsSLPHanFKPWrHjwYaKDyR?exMBFotDGMO]hNQld~_kBSS_|Q]dZJ~BWMo]o}AuIMV?sCL_vAjG{WcpParZOuCgMs`xfBUOuAkLGchVa}OuA{KW`PSWZAbFkRojPngZAJEAKOWhLbEOuCGLw^h?a@dc`kDWYPHQZdVJw[aEoT`RBQHIVoxCLpKBjGgXktsLoxAqIKSohhZbQOvC?GWOww`~Db`mD_RWtqTdzMRB[SO|A^dXLxB[PGoAVeRKgXUEwZpAaoDaPsp@lWZ`OBGK[_hRwZ`cBwK[[h@QffU`mEOWx@Q_dNMlB_PooaYeQ`oDkSG}@{c}IoZuF?Z@VC_IUW[u[M?kbUHMQodh]ReOwCsM[a@ebNE^LZB_Ngup}Dh`oEKKoXpecGI_\EF?[pYdBJYYEF?^Plb{JQWCzsD_[@|EuNolHfrnOxDIN[g@OQ`D^MDBcJwr@pcCIkT[ycMPCA{HeXEFGTPiBXEsQcn@qw[`tDeKwg`ZBQoxCqHoRgyaHEWLTBcOGwA?cmJO\eFGZPUc^KKZ]FGa@]CWHeXC{kMPCA{F_RKgPcRqozAeDoJguqVeAM^BkM_rQID[MzBkH_W@Yc\KY[]FWUpDBwFqQki`lG\`iFMOSnh_B?fg`uF{YpNrMeb`uI?WO~aweoLaZIFWdPVDEIWSskhoW\`_DiJkZPFREfFN^BkJ_W@Yc\KY[[|{N@HaZDOSOk`nW]@hB_FC\@@A}Fh`wDgZhKrCeIKU\EF__`hd?IASGr`gW]@xEOPGjPvbofa`wECU_m`\c^KW[o}CN@QA}GAV?tkN?eAaEePwi`uW]AKEqNKdHSQyEr`wEWP_{qSdPJgZMFgfp]byJ[YmFg_pkCzJ?XksxiG]aUDSSSkXoB~O|AgL{[_xQWeGM`BsPwcPHBtHKS{v@}G]`aDoPkqXdBIfDNbBsMwqQGcVGoTc{CNOsBMFGMW_P@a|ff`yDsL?r`rCEJuY[{{N`DbsHMQodhRbZfy`{DwUPGBFfJNdBwIO`@jc}KqYUFoT`pCKHiWSycN_vBjGOVg{hyruGA`{IKW?~AvdtJkYiFo\_|`{EMP?jXuW^ADCgJ?UHOqrFA`{FkO_pPjc}KqYT@cN`AAFEmOKfpeRQgK`}GCYhNRLE]K}Y@@{NoybJE]L?apUBmO~BYMo_x]RrG@`}DSZ`KAZcwKM\IFwVp[cXKc[_xhrbxo~CqHoRgjAcDhL|B{P?{QTDOLk^uFwRo~BBGGW_vpzg^`yDIJ{_@Baue]LXB{NOhP^c?JYYowcO?p`eBMJ[bpcRdFla?HgTHPqsD~ME[QG?[pdCNI}\iG?UPocuKK\K{kO@ObBFyOG_XZBVgVa?FsYHNBKEaOZC?PowpxCdIkT[vH}W_@kFQM{]@Aa{FbOHC?GgZpoDDI_Y|@[O?kb`FqRWopmbhg`a?Dc[HLayeEMeaEGG]@eCTI{UCkPvw_aLFmQ_iPlRzp@C{IWSwn@~drL[`eGGTpoCqKG\WyxuCNp@BUMg`H\rqGBaAFwY_uPlCxKmYPAKOOqarGsQGcXcBcfsaAH?QwjQdDfLxCCQ?dpRalISU[uHnG`@nFYOk`hBa~FiONCGSOoPaBDFuVGtIDW`@cDkPodpbbbFmaCD_TwvaYEBMiaAGOaPvBuHGTKvPmr|pACoIkcHQQtDjL}aeGO_@BAFEcRgqphcGPABcFoWpCqdd\MG\mGO[`bCMGeSkjhablpBAeDoJgxa[eKMqaeGW\@]cYHCQKr`tB|pBBSL{[_xQdDPLS`AGWdPkCHJ_XguyGG``_FiPSpHabDedOjCKNwiaXDYMU_]GWg@ccgJG]S|XzBvPBCSJ_^xQq}FAPqbiGWQpDB[G_VGxQJW`aTEoOcm@kbZg_PObyGWdPkCHHEV?uxysOG}aGFsT@KAZcwIq[X?SP?uB\IOS{tIBCHGRaGC_SGqATDbNS^IG_UPsC|KeXOqhusVPCBeJwbHerifyQFCOKWX_rbrGkW_sqDGaAMDgJgVX?A|e~PpCOROspvCFJ[ZgvYGs_pCDAK_cPIapfiNccaG_gPWBGHSUK|P{ccPDCQJK^P]Q~fBMGbQGg_@BAFDYRCj@qcBPDBcJobXebNE^Me^qGgU@tCzKc\hD{POqBvGaP[b@`rPGWaIH_Y_uPlCEJYZdBqNWaaaEWQWlHwrvftNkc]GgP_qbuGgWSsIDga`nF?SSi@jsDgeaIE{ZGwAUdDI_Y|@YHgb@jE{SWh`RQfElO[dQGodphCDJ]VSmpksQg~aKD[\hNrFf]NA]HDkP`NAeDMKWdXXbsfpQVCWN?oPaBDGyXcyH}Gb@}DUKwdxUreGGORCWPgl`~DyLybIGoXPzCSKIWgsIDcjpEBIF?]pDBAe`Okd]GwUopBwFqPKopgCKh]aMG{QGc`YbzJoZxE{PoiAOFMRgqHvCWGpaMHWYpAqEcMJWZXByNGba^EYOoc`YBrFsQTC[L?uppdHIkT[taCShPFCEIwe`VrcFLM[_MGw\pLbAGwX_yP|sWPFBmFkRWoaMEJKo\G}{Q@PbJE]L?dHXrsFlQXC_Q_tQADrLgaDCyIC`PGB[Log`SbWEpLc_tICQ?jBkI?SCgPcBmgkaOGOT`KqnD`JC[\?cQ?z@zBwJ{bxdrffxRHC_Jo{QHECLE^xAyWGcAJD]Jc_H\r_f~PjC_PWjp[c@JmZgwILWcaXCwHsYxAaxEwPGbmHGa@XB|GCOKnpoCZHnaQD{]`BqoEBLMY`BQVGc`TDgMkf`bboGiaQEs[PPqhejOS`lI[QP?aDD_JCepVRagDaQISWxGQQdiJU][}AQWc`tE?Pwm`dbgF~O?eUHGTOrbNFURoppwCTHwaQDSQGyq]EMLc]@DQ]Gd@xEEQ?rhtbjfWNyeeHOh@dCfHWQskhxBxhEaSEKOOiQYd[MQ_EHOU`sbnF_RwphvsThyaSGoUw~A}e?KAZpEY[GdAREaO_dp[RYgaQ@CgKG]`xCOKCYPBaFSnpIBQF?MGwQ`dSL[_|IKQ`@AhHMRSj`qS?hiSBCgOOiQUctIw[KxI?T?pJAeDoJg{Q`eUNEbHN{QotAxHARwlPYrhgUPxCkK?epuB{IyZd@qYctpJD?KwYhGAhfYOO_dMKQoyAkHMQodhbbVgdQ|CkNwnqCD~KE[Kw`{S}PJCiKkXwsAYd}LC^`ISQpDAQEwP?gP[bdGlQEciHWa`mCOH[VGxQJSWHBQTCoMOiAQeLLS`|IyWSpPKCoK_ep^R?E@LI^\IcR@CaOEyO{mHqsWGpQUgqH_U@xdFKy]S|XzCZiDaWE{U_m`\c{JI\PBINwe@cFONs_P?qmEvOaeMH__@BAFD{OgoPobyHvaWIGYXFaiD`Mq^x?YUCxPKDCLKbpTBkf}OEeDMSROnbfFsTguiBCHGRRHCsSgjpjCZIa\|?Q[syIQaYHcR_fPecpJwYO~QSGe`TAuN_^HPRMFcPogMHg_P`CEKQWgpXnBxHuaYEsUhMqqFUMm\`AaOgeaGEuPCaxEAwFHP[cpPkROyamHKWotpvcPh_aYDGI_|AVDGKm]dEa`Ge`tD[QWp`jb\gbR?fLSSROyamHKWotqGskH_SsiIHogPiBXEsPohpvSAhoSlCwPowAHdnJiVWwyIcbIIa[FsV`AqEcMKI[C}A]gf@XFmScrHyCZI@SMgaHoWor@fFSNkjXlCDHha[FKThHBFeoLaZHCaVtOPMBWJKfPXbHfNOscAHoe`eCsJgVgsX~s?HPa[DCQ_qQVdwLK^tI[R_uAoDeRgkprrkGYQ?iqHoZ@XbCHsUWxprsLH?TXC{QwqaXdzL?^lCqUCkpNBUJ[g@OQ`DbMc`TFiiGf`VFcSOhXerrGxPsgYHw]@SchKeXOqhjCOHYS~C{Roh`RbPG}S{za@svIWa]ES\GzpwC@IqZXAAYGfaLFAPGlpqBefMPQc\PsRo~BBGGW_vpzcLhNRrC{NooqAEGKUZw|p|cLhxa_GGWGp@acHKM[?|i]tZPOBqIkd@cbTg`PMa`Jiewg@YFkSgrPfbNffPigAI?cpbCqJ?VcsxiB{hUa_GoZpDQufDPWc`HqRtDpODGLGbPGaPdON?_PLadwg@hB_FCUpMQsfOOmcDTSS?oblF}Ooj@mCEhaRND?KGzP~cKIoZ`@iXt[PPB[FgV@NqsFTOw`tFYjWg`uBuFoTPIrGehPCdpRkSPPbWFEPsipTrlg@R]hMIGT`ydEIWSsr@ycXiAaaGkZwx@qcSJW[XDYQTFpPCGJs_h`b^frRoftNqkWg`]FKMw^pVr\EzO]eTVkSPIA\EQQ{n@hb}hMQeiyIGd@ccnJoXSsp~S?HRT\DGPwcPHBaGkVKxaJseiHacE_UPNQrfPOobxGaPTSpQBCMk_@VaodaLe_lKqnGhA^EmPciPvbofaOKetQkS`JBFH_R[f@\rOf{QikYIO\pAaoDaQgq@jSNHZS|DGOWoABeCLy]{}h|cyiracDOKw|AcEVNQbPOagwI`RAgDSIoTok@XAsFkOwfGI`]A}E?KGW_p`cBIFCRghwI`oBcFKM_\Oz@vBoFcQGhgI`\BKFsNo^p?A@CCGKO_cgIaGCQGgPWb@EaMC^@SJ_Xo}ARCgHSQodpKAXCt@SRofpOA`DCIKS_hWNaDDOIcTOipUAlD[KOY?uWNaqDeJOUgl`ZawDqlaBwn@]a}D}K?WGo``bNEsNeBwpPbBFEOKcXOqpeBLF]NaBwk@\BPEcLKY_tPjBVEoMQBwkP\bZEwLsZovpoB`FCNABwxPrBfFOMc\OypuBlFoWABwUpwbqFeNO]g|`zogFsNk^_~P~B~G?ODZcIAACDGKO[`@AQDCJGoQsfCIA@cNG_PCaPCqICTGkQKe{IA@CXGsPkb`FQNC^H?]DWKIAFCcHIQWcxIASciHUSGhcIAEcaH]R?eHKaXcsHiRWhkIA[cyHuRofhNa^d?UxA_axJA_dBIGSSgpPqcDHITBC[XRafdOIaTGiXTApDtK|BCj@UQlDZIwTsjpVr?hs`aQCixWqqDdJKU[l@YQzET`aTWl`ZQvDnJ_VCmP[rDES`aR_mx]A{dyJuVonh^dsopJAUgo@_b@eCKIWWoxaBCopJUWkp`bRFENK_XCqPcrNopKkX[r@eRLEZKwXt[[MbSeiLUYothjbVeoLs[KxsM`vErLgZSuplr[ExMY\[|cMa~eqLwZsvpnr_F@MC]C|[MaeFDMK[[x@qRdFJMW\`Y[MbRfNM_\CyPsriFTMk`t\cMbkfYMu\ozhvbnf_UpBgt@kR\fbNG]S{pxrsFhNT?g|hzbvfoNa^G}X|CHg\PP?gm`|r{FxNs^k~`~TpJq_SKx?A?S@GBOG_T?q@sHG[_S^|@QAsEGLO[_|AACSRgo_SFh@ADCIgUOm``BIEcWgy_SJgfAFcNg_PAaHCYHCQjY_SH?}qASSgiPUapDiJcVgx_SSk{P|SXGrPgbTEqLs[JA_UblFaNS^G~Q?cDGQRskhi_UcPGqPscHHQSclHaRSpIG_UaXGiSCghQQedPIiTcxiF_UHseyTslHZQwdtJqVsoHj_UHlJAWSphcRIeXKyYCsh|_UI|LaZSvHnR_fDMQudpJh_UfTMq\s{HxRsflNauDxJw_UcxMa^c~i?SAgHOY`DAiE_WcLPIadDiKSYgxPyhT[jA_WQw~qcdHiSSihXQyeD[JI_WhDRYfDMi]S}i@SIgddjR_Wh@RIhdRigTQihTYjDUj@_W`lUIkdXisTijXUyudvjz_WOpRQhDViyTujpVind^j?_WixWYpDajEUMk`XIwdpjw_WN_qagtWJKUYkxXysDgjQ")

     
gom786nx = gom786.networkx_graph()

# List of graphs to process
graphs = [('Gomez 786   ', gom786 )]


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" / 12-reg.? {graph.is_regular(k=12)} / Degree histogram: {nx.degree_histogram(gom786nx)}  / 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:
    for i in range(20):
        print(f" dist. dist. from vtx. {i}: {distance_distribution(graph, i)}") 
    
# Counting k-cycles for each graph
print("\nNumber of k-cycles for k=3 up to 4")
for label, graph in graphs:
    print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 5)))

print("\n")

##
#