# SageMathCell online  https://sagecell.sagemath.org/?q=nwdfqv
#  Q'8d++ (13,3)=856, Moore bound=2042. 
#  Modification of J.Gomez's Q8'd+ 851(13,3) graph by adding 5 new vertices and regularizing the resulting graph. 
#  Found by V. Pelekhaty in August 2021.
#  Ord.: 856 / Size: 5564   / Diam.: 3 / Avg.dist: 2.81882 
#  13-reg.? True / Degree histogram: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 856]  / Girth: 3  
#  
#  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False   
# 

import networkx as nx

pelkh856=Graph(r":~?LW_@???K??@O??F???G@G?O?_??W?{??CO?_@?A??@g?o@_B?E?K?W?o@_A?a?G?_@_C?I?Y?S?g@OA_D?I?S?g@?G_F?M?WFw@oB?N?M?[?w@_G?l?Q?_A_KOC_H?Q?c@GAOC?O@WCC@WAoD_J?U?k@WAoD?OA?DKA?C_V`xBqF_Ng]O{_YBqFcNG]O{_K?u?s@gBOE_L?Y?s@_C?V_M@Q?wOWB_f_N?]?{@wB`C_N?]@sBgFOM_\?wGsBgF?}_\?o@oTgF@C_\?}@{BwF`^_^?}@{BwFoN?d?}@{CGG@__`@?LSCGGOO_`@?G[CGG?g__@kDGI_Z_}AYDEAGPOqOPBN?gAGVGG`X_b@EAKCOzoPAV@CL[CWG_XCJ?oAOZWHOQA|@GKKCgH@w_d@GNsCgHOQ?yACD_MO\`IAn@MAWcGH`Y_eGMAWWOxOR_eEmA[Cowa[_eFAA[CoVOSBl@OOKD?loSCj@ONSD@FOSBP@OHGRgI?W_gFAA_FoP?q@oB{HwdGIaE_j@SRSDOmoJ?iEwTCDPDoTCH@SMcDPQoTCP@UAkE?p@dBKGYB?Zo|an_oH]B?YWKAFDF@_PcE?|A?_oDcM[E@VoWBP@cN_jPYavDp@cOcEOyOXDJ?gBGegK`m_qGmBGVWK_]AIHYBGjwK`\_sF}BOZ?wOYA}KUBOagLAoDx@gNGhpdbK_sFUBOewLAf_sESQWhwL?cC\@gOOc`RoZAIEOS_sGLamDz?kBWU`SBG_uEmBWf@NA^D@@kNOc@eOZCF@kMSEpGOZBCHABWL@QO[Cr@oSGrWM@_EF@oOkF@Fb^_wFCNG]pUO[DeJyB_YgMAO_wASOgtgM?\BOFiB_]PAat_yBsJgiWE?\Bl@sPovGM`ZEN@sQOiPTAuE\@sIWXOsO\CAMmBgP`Io\DgJmBgY?uO]BYN]Bo]GN@]EKMM@gF`JB@_{Fw[cF`Way_{E{PgcpMb\_{IWYcF_f`|_{AwIojpnO]BmM]BwcPoO^CoL[^[Fom@`EH@{UOnwN`DBmIsUsForbp_}IGY[FopaACOMeBw\pvo^AeF[QSGOp@dBKGWXkGPVbu_WACSWowOaHCmM[\gzwOaKGXACO?~gO`hD|ACUO{wO`rBqHsZ{GPBaeENACMWi@ncL`CE[VCG`KBe`CDoX{G_paACONqCOg`cbKF`AGQH@wP@vEuPACOk`wBr`CE?YKG_fAqFePeCO]pKcF`EFKZwzGP`pBqFkT_uaFobDAKICWY`[b?EUOMCWPOqArFoPqCWePtObC]MK`CGpAb~`EE?PgfpgobBKFCUO{wPaZE?Kg\CH@?bIFzAOJWtATocDgN[b{H@Ibc`GFWZhCwQ@gDtAOQOiPTAuELAOHwoGQAeEMMqC_ROla^FEN}C_S`FCE`IJCWGz`ybxG|ASN?vAGodAqDwXpHwQaeENASLwbPHa\GSRYCgWOuazHH?kCg^`SBy`IHW\[HP?avD}RsfsHPAAvFvAWROyWRACFuP]CoVPhck`KGk_`AQEcMH`AWLonwR@{DYJSUw{QMoeDIKOgKH_b@sF?PQCoOOta{EnAWDG`qOdL`KGO^XNgRACFvA[H_W@NbP`MGGPp@gRaOGURShsHpVBsGsSyCwU`hBTEkL_d@RgR`qEqPSfHRgRaBGASchsHpQBDI?SyCwf@NA^D?MShsHota{FiOccSHota{`OI[X@OgS@kB_JsjKI?nbOHTA_Mgv`obaFWPID?^q?DD_SA_U?{aLogBsGg_hKwS@OBWH[]PHwE?gCuMaD?h`bb`I`A_RWipsOiBCESKo``kco`SIK`XDGTAVDwPuDOWPVc@HGUADOb@ack`SFKYOtPjBWIBAgLGxQaDEI]TADO_@yDV`?AgXGrPfBNE_LCYOspiBt`SGoWhJAlo_@SC?P_pPockI`AkQgmALojCcIcTOlaBcQ`UJO^`JqqDe`UDkZXKwTa@FeTeDWPOq@gFKSUDW\`fblICUMDWb`cbKF_QglcAOT``JHAkMorqEdAJV?kD_g`SCEG^AoUOq`}d]`WEKOOa@zdT`WDoZhKWU@fCeMOgxSGU@vBsLOfh\wUAPEKQGdhSQuoK@WH_VPFGUAkD[NwjcJ?b`LBMMOg{J?rbcHIS]DgZpEaRCyKOd@XwUaUD}PiDghaACHGYOwakJPWbzIzAsNo`pwdLIsTmDgZPsdHJEV}@OJO{BRI?VUDgLPEBDHXAsKwxACdF`YBWJod@Zb_HjAsMorq@DA`YDwYgw@yct`[FSYHNqzOmCSKGdXZgVAZDqK?XX?qNomA}L[ZPMahEJ`[I[`@CwVAoF}UIDo^p{CyIeTmDoZ?wBiIOVyDogPvCDG`AwNwf@OBwHATMDw_pzDWKpA{LWaPrblF]SknkJoxBLGoR_fpXQyOnAsL{epagV`EC_KKcxYgVa[C{H{S?naNOnDGOoaKJo|A`GIP?psJwV`uE]OwgSJpVB}IKTGj`[WD_nBGIw^pSamEC`_Iw^g~amOoAqJK_@Oqoeb`_GS]PTBJooBSM_fHQa}OoB?Lw[Gw`uCqKRB?MG]O|akE_Rkm[K@FbGHQUaE?eP]cUHAQKdsK?nB_HiSYE?cpOcDG`B?NwtP{DRJVB?GogPTAvGIPAEGZ`pbjIWWMEG\@fC{JdBCPWpqRDh`aDsZ`LBCOpCsIsVXGBGer`aIS`PDqKcdL`BCN_jPYavFsT{sSKPAB@F[NS^HTbIopCsJkXXGAfdo`aHgVXGAveXLzBCROmqODEJL@WAwKOY`SChBKKOXOrAEFGRkq[KpEBvG_WEEWjqBDSJoVkqHhgXabESNsdHlgX`hEyPWcHGqVDk`eG?WpWRBEL`eH[Y`QbVOrBeJgePfwXa?CgKWXXWREorCCGg]HBaGeB`eC_U?uq_d{`eG?VGpaoeL`gFGV?tq\DQK|BOR_f`Na_E]S_tcL@@bHEWN?kPbBaOsAsMWfxegYAOFePKo@`RBEN`gDcLWuqNdBJZBOTp@qhdv`gEKR_h@}CjH{ZUE_dPebbIQTCppjwY@LAuGc[w~qfdULXBOM_nQWdOKKXuEgWPDbqG]QOnsLPQc?HCQsiHnBeotB[Lw[Gw`uC[J\BSJgyA]eXKwZMEge`gDFLVBSM_]`]cpKzBSO_qAnEJMPBSN_jPYavGITSmsLOy@{DyQCdhKRMotBgGcVhKRMouBSFgZ`FQrouC]KC\o|P{cSJ~BWUX@ADCUImVUEoW@td@KlBWMG]O|akDuR?s@vwZADEMU?q@cbWfB`kIC^PJB[FR`kHcXpPAbDNI_YuEoQp@bRHcZ[wsL`XcIImVUEo[@HArGSQCix\WZ`bCCG_WhVrDF@`mF[V`LBAEfLOYcz[LpPC@HKZkyCLod`[CMMSaxNBKOvBMLcc@YgZaqGUTWkX\BqovCoLGYgt`kDKLTB[QG|AJcXHIVuEwV@TBdFWRog`eGZ`[COMScXJq]EWN@B[J_WPqc{KpB_So~qTEyMdB_NooaVdcJKWcwkM?vaLCeHs^@Ca}OwA{MggPdrtFp`oCWUHAAkdrNDB_QosQaeZLGZGucM?{AxE?Kk_XKrPfY`oEsZPDaLdgLRB_G_kqDDVJjB_LguaLcdJOWWsxxG[@lEsNcbXYBREs`qHkYXQrWOxD_OO`HBQFDWJc]MFGPOq@tD}RWsPuG[`^FQP_f@NaqeTNhBcSw}qRexLyZwvxsW[aICwNCaHGb@oxBWF?[@Fasfy`qF{W`MQmEGMC\YFGXOubWEsP_bXRQsOxAqGgTG{QGdzKFBcGORonbvIWYC~cM`BasGWSsjPUq{fh`sE_ZxEatdoJaWw~kM_laHFMMs\xOBIFr`sGCWXVRBfF`sHGTGi`ZB}HOZ[xsM`FBuGiWH?[Ao\@uDOJwehgRdf[`sFcOoh@}CjLi]EFOS?wATEYSct{M`CATEYSctxyw\@MC]JghX\bwgV`sHSXgwqQDHL][qFgW_q`eCKNCghfR{O|C?M?dP\cBo|BQKO[OzaXejLe]}FgdqACHGYOwgPZbko|BeNkbXeRMErOd?kFgb@SBhIqZow`qw]anEeMKaPariGT`yIKVxJqqDeJ{]aFWNO^FINC]K{hxbrfgNQ]l?CNO~AFEqQcmy@SEGX`yEcW?pAEcrLU]}FogP[D\Jy]K|SN_w`xBuIo^`EbKGR`{E?]XQRAEfLOYc~SN`BaNFKSsjPUr\fA_WBwOguqSDsMS_`@cN_tBHEWN?ehibyG\`{JKXxDRDFP`{EoQGy`vdWLo[\BcNpVBMG]VgpHrsKOI@}H?\XTQ|EyMK[cxcNpQAzI{Vgn`xw^`YEAMw]g}QbdyLE^eFwf@NA^D?OgfhYA|F]PLB{LWpqWdyKuYOuPlBug]`}GKZ`GaUdPJeVh@SNoxBJFsPof@dsGo~AIFGPgjP|C[Km`EFw[`|C[H[V_qyCW_AWGOP_f@NaqdfMwaaG?Xp`CuLY^LB{O@GbiI[T_kpcb[FFMVC?J_}Ade_NzC?Mw~qNEUMi`XAyESVP?DcLCaHcBHEpM\C?KW_`CBYHMVT?[O@PAxE?Kk_XVA~fha?JSXo{AQD\Ks_eG?YPTAkEGRKrXirvp?AAJOY@DAPeGM_\TBCOPFBgImZcvhnb^f@PxCCOGv`obaFWQomQ@g_`uG?PsqiCCUp@AuNGg`PafdOLC^mGGY@cCoL_^?}h|bzg_aAHGTGi`ZA|J?WK{kOPIcDIAUczYIwD`@AKEKU_sAIEGKu\@A{OPKb?GMS?lPnreFWaCEoM?paYEnNc`hF{O`RayI}WG{`yruG?aCF{ZhHa{gCaCD{Yg|qeE`L{^[~cO`WBSGmPcch`rhhDaCDcPOxA`dULm[LFSO`LcEHwUkm@[RFF^PNCGMgq`}c_Kg_xECO`OAsE_Lwa`YrCFOaCD{K_|qJDKLA\s~cOpAB^HUV_nXcRRGHaEHg``MQ^dkMk\hCkOo}AlDiJ[XhCrEfQQNCKJg|acE^N}_D?QAsePBA_ISVpEQPDaKA]IGW\@~C^JEXL@yJw`aHCUM[\gzqheuMIbyGWZ``bVHsTGtp{SOpBAeDSKoYa?cRJc\xFSOpGbiGET_v@prmpBBGE{N_hPZA}JCWC{SP?xAkFsPojP]bJepObCON@?QJC`HEQwrQDCXpCDaLGYgt`kCOKW[tG[P?ubDHcYo|qEwa@]FgSgrp~cepCCkOkfXZRjf\N?]DDKP@RA{JAW?oh`bFfeQjCOLwbPHa\FITOuhqC]pCB{LcdH\rLfJOI_aGwW_q`eCKNgiXic@hTaMG?Xotq\DQLu^tDKPoxb@F[NS^HWatFMPzC[LHAaTeCLMY_tHps`pFCWJkh@\BxgraMI{Z`Nq}fTOk`\BIEwa`FBGH[WxCrKFhPEeaGwgptc^IcWgzaRWbabFUP{exUqrEIMw]DGARWbaBEeOGePYqwEvNA^lCkQ@DAwIGSWhxSAxfmP\C_Mg{qoDgMYapFIVgc@^FwT[rXhBXEsOIdmH?^pfcoJEZg~qIGc@kB_O[d`grcG~QDC_RWqPeBoGgX[{qXwcAfFKPspHtrmf_NAd@LsQ?oabFUP{pPvCepGBoNWjpYRhgwaOJ?ZXOQpd{K_XpAaFwcAWEOPSjPcrcfgPkeQHGd``cNKi]O|XzC?HbaQE{PgcpMa}IMVG}QKgc`}EYRCvHnR^E~NwaiHGV`~DTL__PJcQOucKHCQsiHgb`hEaQF_XOwPzD]JQWSyY?C[PHCQIW[wzPvc[KO\|HYYwcapE}RsoYBcMGcQ?fQHG]@BbuH[RcjpYRhfvPoeaHGZ`ScJHSY?wPtCaIBaQF_]pVaseqMeb`N[Q_yBsH]UOkpXrggzSDCgSgxQLeOKcZCzAScuOKASDs_HURUfIOO_pJSQ_}AlDiJ[ZHOa~gRO{f]HO`@hBTEkL_eXmB|GeaSGkV`PQyfsPgbTEqWGd@XCsKSaPOrJFbRBCgI_]pDbHEgPgsXxSLpIAuFo^xTbUFjOScxIsQ_vAEGCOkdPgBWfAMWcPMCQ`@AGC]JgexQqzFcNaauHWYq@CCGQOs`pIROf@QMguHWf@NA^D?KO_PCBIFdRLCkJO]`|cAIgY|?qUSnpJDGMc_PDaOcbH[W[zYRCtPJD[M?_PMr@GOPAdtMsQoxBpGCUClX[AweMM_bxOCQpGA~GCSgnH{ByfuNma}@GQp@aLEeMCePXRZfzOYaUHW_pZBHEeRGiHlr|gUPIfiH_k`nB`FCMog@_SHGYRpCWH_g`sCYKY\d@iRciHnaWF[[W{amdkMg`TFQ^ge@[CMO?hhUalemOMdaH_cP]dHJoVkqHhbvgoaWH_X?~QIccJIW{qXyCEhcaWEKOOa@gCtLk^`CydWe@fGIQ_rxpCaiNaWGsR?qAIc}JEXK|@{CqOIAWCwPwmadduNaatEcR@KBGGiUOqXyCqPLCcIcTOl`tC_KW\xIIYWeaTECP[bHHRLFfRIiA@OROsCGHKXwwpqReHGSVCsMo}AndlM]b\OIcGeaMDqK?XX?qeDvNYbEHgl@lC{K?WSopbsGg\RjCsKG_PgccHgZS~IQdJOIAYDk^xTbGekMm^|@QTc}pMCILOepLr]F~OA_H@YItLPMDeLsb@Lq[C}JIVx@yGCxpMC]JgcPQqzEPMK^C}iJWf@_ESNsexUBTgHQmiqHoePbCPHmXcr`krpHaTBCwSGxANCvKU\hHyZWf@iGKQ[exfRah@QQdLPsR_w`xBuIo]xLqmDmMcbpN{S?p@dBKGW_hVBYgMRAjAI?[pcDWK?WSopbr}HCRTD?LH?AGdvM}]hFY[dLi[a_I{\@LaugCPgbTEqWDPpOC?Jsb@MA^DdLW\LIQbWgAKE_PwrpxBtfkO?`xTsS@Pb]FAMG\`QrLFBPKgAI?cpJblFcQ[p`hRxHYRlDCJ?^`[C{LU[xHa`tHPPAoIWZXRBKe[Le[\Ci_gg`WBsHW]XHbDfrQqd|Mymwg`WA{O[jxnBigUOm`dKqlgg`WBoKcX_{AjD}Nyc\LcSOk@lFwP[bHHQzF[P{hQIGU?vaLCeHsXxGBMfhPAiiIGkPrCsJ[_LDyQdQPPDaMWe`ZbtgBP]iQIGi@WbaFKROlp]C@gnS_iQIOY@|cNJg\hDaMSnITacJO\HKQtGHP[ftSQhTRj?acHGTGi`ZB_IMX_wiIC~PQAuOO`HBQFD]Lu_|KylGhAMEePoo`hrSEhNC`|TKS_zBCIiVs~y?S@GJQCe}IOdPwcaHYTCpP{SlhwTxDGOGnphCdHySOo@ibhHOS^DGLOc`kC@GeVGpxhRdF]PshaIO[pNAtE}MovP|CfhoTQkUIWaPWBfFYM{ePXsBgpTAkQIWepzChK_XGuHzsjHrTrDKPOrQJC`HEQws@yCMikaeD{``WR[GQOoeTQYhdXPRBWF?^pCAyfXPmb|RSSo~a}FERkthtCIhPS[k}IW[OybBEQMCi`^rQfwQOeuIWWPRb^HGSgqppCdH~aeFSWXTA~esNoc`LkT@Qb\IQX[wIIS|iBSKgaI_\@BbEIYTgjX^B|hBRUlYGgT?m`cGKTsvQCCPhgTnDOO_ma_EZLGZGu`sCeiHU\DON_jPYavFGRSlA@cXi^ULDOLoq`}cTJe\lFieWiAYFmQ_pH{ByfuNmdTManWi@tEENci`^ruFwQOeuI_ZpDbSGsRwgXgrqgZTVDOPWtALCyLE]TBAEtTjFaiG{YOtPjBWG}YGshxsLIlVDCWIg`P]C~LIZ?xyBSfHSSWkiIgWADdaLIZcvhnb^gPRGjE@OTPObXIOXSshpbcfKPMgU@WTPKagFgQkp@hRdflQofpVSTPXbVFIRgiPYRQgIP_htWkTOw`xBuIoWhSr@edNqcTLquGS`TGqSOghPqcDHISSkh`SB_PTCmKC]PHq[EKNc_@JQ\gb@TBSOCaX[bnF~Psh`[cTOtB@GAPKkp[bSfHM{bhRCT_zbFIqWG~qOSchRRQlmIoWp@AGDuSGtxrSfiJUXDWUOyqXdjJ_VCpq@SUi_UBDWJ`AaVdcJKZ\AaWdXpUCoKC\o|P{ciKM]xIy\T^PUCaKwbXMROfUNKa@QIjtmpUDCLoghdBcF\NSalOIvDwPUBMNgaP]Rjf\N?]DFaddtPUDCLo^H@AaeSM?[_|YIt?pUBIFSWXTAwD~Noc`LiqDvpVCwHwRwg@{CkKY^PJa]T[PVBcKGix_R|HER_fDNQtwj`jF}POn@]rGeeMob`QyyWE@VD[Mge@ZBdGGOWbHRqowjacEsSOgpRqgERMCahOa|WjaBDqK?XX?q_emMaclPQrWjaOEaPsrxwsMGcQ?i`Z{TolCGGoU?o`lcHhbTikaIwUaCD_LIZGuqCshhbTinAIwU?lCGJ?ZGuqCspifTjD_JOX`YcGGkU?uqCspit_kDgJWV?m`]A}E?Ko``OAhRtDcKoapiCYHsYK{iEsUIj_UDsMGtprc]Jq[|DQVc{JCa{M?[xLQaFfPwghQYtWD`_EaWGzIKsZHXSCl@[sA?J@fBOEcLOYou`mB_HLF{YPaCrLUZw|PzsQHoSIlp_SD_p`kB{F{O?_P@aCCIQ}EOZ?}etLkZ[v@mb\e{LyZ|N[A_vCJHSY?tHnr`G~QGiTWCZaDciHmY?spocaIFU@@WLw[Ox@rBgFSMo\o{A^DWYQNW^p_bwIeY[zYFdYJ@aqEGOGnq\C|K]YgyQSDCIN_kEGOOa@DAJCWGwPwc@Ga\DnGw_pGr?EUMYdpLQxTuKBWTHC\PUBQEwMM^|@A\DGjI_kESNGdPJAVCoHcROepMAiIv@[QpKA}eMMG[XIQktpJc_WHWTgrAWD|MG^\IQktpKRaqH[X_{aReKKqYW}QUczJY_QHcYx@q_DiMo^\FIhtVJZcuHs\@\A|fxPAgdWyxTyoL?kFkQOgPPAbDGISSohpZCWdCLoghRq|EQKg[`DY_UAkJdCLodhOqaeSMOalNa_WEabFUP{o`abmHLR?ntaJGGJa_DGMG^`IrXEtP?cxRyuXNadD{UGoHwcJHSRwhXWR@gJ@EBwHwTgj`VaoDaJGUWlB_OKAoJC[pLAvFVOEaPDy[dQIfbCJOY?tqIEGM__@Uq{gOAwDsJkV_nP^A~EUM[\p?qEo_DqK?ZGu`lb[EyL{[?z@vb|`?JcZow`|BzFwNw^x?A?kXWtA?WOopaBDEKK[X?r@wF?OioeGgrameYOQ`dEiQszhyT}l``cBOOAHFGMS[oy@sbiFUMs`qnwOB@EiL_]G{`xbsFkN[^@mS|o_ByLW^H@AAcEGMO_`PAqEEO_mHw``FQ~FlPyf@SY{uFKe`QIk`xCAGcQGePOahHQfiGUf?sDHDaLCZGwPsbpFqOCmMQqYDHGaRCfHOQcdPIqUDPMUdx`[BOScoHaRGeXLAYcuIcpXbJFWScWHoRkf`NQ^d?IASGk`XUVohH]SWjXVAmd]I}U?kHWeMoHIY[@IiTcjhWQsdlJbAeHkb`cKckxYAsdiJUUolhZbFE[OZBGJ@[axdsJiVWmx]RBEPKqYYEP]BHERKgXSqpdrKEYLelpa[K`jDoJwVsnp^r?E@KCWKpxkWE_qKIW[p@aRDEJKWWsuHmUDOqGGVko`fRNE^L?YCsPgrSjy`cIkrXhBSEiLUYothjbVeoUN?gFXDr_fAME[OwhprcFKWGoawqVTcJqVenP]i|dzjxW}qAFWWbefMM]\?yHsbhfoOA`TcSB?\fIMg_L?a@SBGFOQ_h@aDwE_zHo\[z@uRlFZMw\wzxwC@OzMy]C|hzbvfpNc^K}`|cJGs`uGcyhxBuFtO[_|AACSHGROhBkXOwqqFwNq^g~X~B}f}OO_m@IEcLg\O{`|CAGSQGuQ?d|`kASMGkPmb`FQMs]G|P{cDJrDwCaSHGaTCqHsSGhPSalHQUUMOHHYaLEaOc`hCQIcXGyQChke_QCWK_^SdhKQYc|IASShHSUN?cGiGsYh`RCeLKaXSrHfROkaHxMSshiRUepLiZcvhyTKqDekAofagDUJXMY\CyhuRmf`NJBgfa]MkflNq^t?I@SCgPOihuGpNM?]hOyaTDIJSWgtPqbuGKPa][lNiaDGI\S{h|SAgTPica]``Ji]tGieTOidTQitUIlT\jHYItDijUUml`ZIutqJwVvLT?QmD[iyTujpVindvkZY`DcNhOtdJJUWktXqrtgJ[WhIkoivTnJ^V?mD[QwuCKVX@?t]I~D}j}V}o@_J?e@kDWL?_AwUBQf?UQmXfzSehlSYitZ~~~~~~~")
             
     
pelkh856nx = pelkh856.networkx_graph()

# List of graphs to process
graphs = [('Pelekhaty 856   ', pelkh856 )]


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" / 13-reg.? {graph.is_regular(k=13)} / Degree histogram: {nx.degree_histogram(pelkh856nx)}  / 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")

##
#