# SageMathCell online  https://sagecell.sagemath.org/?q=maocst
#  Q'_8d. (11,3)=715, Moore bound=1222. 
#  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 degre et diametre donnes.Eur. J. Comb. 6 (1985), pp. 291-302.
#  Ord.: 715 / Size: 3770   / Diam.: 3 / Avg.dist: 2.85714
#  11-reg.? False / Degree histogram: [0, 0, 0, 0, 0, 0, 0, 0, 0, 130, 65, 520]  / Girth: 3  
#  Alg.conn. 4.08392)# /  Domin. number: 65.0 
#  Aut.group.ord.: 3223015124558532858347520 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False   
# 

import networkx as nx

del715=Graph(r":~?JJ_@?A?C?G?O?_@?A???O@?B?G?S?o@oCO??A?G?W@?A_E?M?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_V?m@[AwDoJ_V?m@WQwD`J_X?q@_SWEOK_X?q@cB?lOKAt?u@kBOhOL_YDa@kBWEoLB@?sKCBgF@T_[Cy@sBgFOM_[EU@oZWF@l_]Dm@{BogON_^?{KsBwF`h_]FY@w\gGOOBr@?HcC?vOOA~@AA?UWGOOCH@?OcCOqOPBX@CHkCO}oP_aF]AKCOjOPCZ@CPkCgHAA_cC}AOVGH@s_cE}AOWgHAJ_cHEAOcWH`JAeDQAWcwH`~_eD]AWaWH`t_eEmAWWWHaRCx@KQWfGIAPCqHgR[D?voSA^@OKSD@DoSCD@OJcD?yOSA]I]A_RpRoTBT@SJOVOnOTAaIeAg[wIaSC~@SPsDOpoTCF@SPolGIaMDh@WPOkgJAQD@@WH_jGJ@X_kGOOg`gJ@x_kEyAoVwJ@xD|@WNGngJa@_mG[T{DohAe_mFAAw]@^oVB?E[LCDpJa`_mDaAw[@bOVB_KYB?XGK@vDx@_HgiwKALC]H?UCE?jOWBWKiB?^WKAWC|@_IosWK@UEb@cJWswK`e_qD?TSEO~OXBQKMBGdPMoXBkFkN_nWKaKDl@cNougK`}Et@gNOoGLA?Ep@gHoiGLAUDD@gKkE_ibL_sG_UkE_u`pBcKaBOXPqoYBIMUBWQoh`SD^@kQWsgLaHDL@kKGnwL`~EKKkXcEoybg_uEkZ[Eoja`_uECVwzgL``D}MyB_TPLo[C?KUB_R`Wo[BYFCMOuWMAGDMIsTsF?|Bb_wESVWzGMAUE^@oQorp}O[CkK{^cFOo@fBOJg\[FPBad_yDGU[FOkA[DEIQBgdpiBv_yGCXKFO{Bc_yF?ZcFOhArGB@sIOkq?o]BWLgZwwGN@vFD@wHglaAo]CoLK^SF_}bB_{EOVg{GN@UCz@wPgbpGAi_{F[[PAgN@vFCOiBwdPgbTEkNeBwX`]Bl_}D?U@?GNaKDV@{Mo]o}BeG`@{JWfgN`hEn@{NoqgNaKDUPYBwb@TcU`?GGXCG?vbW`?C{Uh@gO@sFIMc\PAWO@[DDA?QGePLBLFpA?PWiAKo_BCK?]KG?vbWG|A?LwuANO`BqM[`{GPHBOFjACH_l@ZawGDACJwmPxO`B[LwcKGPDAhGpACO_`PBBC`ADcR{GOka^H\ACJGfqVOaC[IobSG_l@\A{I?dkG_gaqGHAGOWpwP@bD{KCWOzwP@iEyPuCOd@fBu`CFK[HBWPABEMRQCO_pbcs`ECkIWT@[cH`EGc[w{WP`~C}NaCWcpnCu`EFSTH@gP``DgJ[V@EWP`VEGPwchHgP`jE_QmCW\PScEH~AKMgiQBC~`GFsRW|gQALC]H?[WzwQAWEqROfHMgQ@LDuOuC_Z@fcl`GDWWhFWQ@cDaPiC_\pRalD[OOgCH?qApGsSmC_X@WcYIVASP?w`todCkLgZwwAXodBYFCMOsqSodA[Js`[HOibBG~ASKglaIdI`IFgTP?QBcGIBASO?fPzodAiKKbxSwQ`TEEP{i[H_z@zBwI__PMwR@}DCNUCob@qbhFSNICoS@_CN`KHSZ@KgR@hEYQwdxKGR@ZEOQCiSH_rAtGoSaCoS@_CNIxAWI?oAFd[`MEKUXDqcofBeIS_hOgRaBCwIKS_}gR`PDsOgaHCanOfC[MO]CHpIB[HpA[LOtARofAsDsJoqQODP`MEgY`HqsofBSLOcxYWS@mEcQolCI?kbEEUKocXSGS@^D]PWbXFAbogAWJ{a@VWS@xDKO?fsI@AADCKIC^KI@DBgFZA_QOuqWogCcLkeH\GSAQEuRCmcIPJb\HmVMDG[@fCgJNAcJ?pqPDN`QDGVooP`CKIvAcK?XosAqGeSYDG]@UCBHxAcOGg@}B|F|AcOwwPuOhCMMC\`^gSaFFAMonsI_mBIHGTYDOW`WCSIJAgM_ip~c|`SC{V`BalOiCCHw^[I`DbeF[NK]`^WTAPCqHgYxLQxOiB]LCYgtaTDd`SGGRo}rAoiCCHw^X`WT`JAeDOWXCqpojBiLK\`TGTaRFCQ_hXRQfOjCQLgZwwA@eA`UD[Vg~@}b}I@AkLWiaZd_`UF{UpGa|ojBAHs``ZwT`jDSR[k@cGT`jDSR[k@cGU@^CuOgaHCavOkCGGSOokQODx`WEwSwjPVCwI}WyD_R@acVJTAoNGrpwDRImTaD_UP\byIBAoQOwqRdI`WGgZH@R?okCSLc_h_RMOkCSLc_h_RMOlBgKw\XSWUaJEyOC_xABCET`YDoVooP`BvIDAsHwpqIdhJUUqDg_`XC^JpAsKOgADdl`YE{T`KqnEQ`YHCRGe`ochIRAsKOgADdlLHAsKOgADdlLHAwJ?n@{Cz`[F_YGtPjBpIdAwQwxaTdG`[DGXPEQrOmB?E[L?faCdoLLAwM?iqZD[JAUGpkJ`BbVGKWOr[J`?aoG{QScp]gVAVFKQkh@iwVAVFKQkh@iwV`lBaFGTHLQmeJ`]ESRxBayDtJkYIDwa@nB~KMXaDwR`aCSJPA{IgmP|c}`]HW[xIabek`]G?U_lp[CcJnA{NOs@vBrFgTADwR`aCSJOZYDwR`aCSJOZYE?b@mCCKKXiE?YPQcsHqRgjXbwW@uBuFoY_zqfooA_KcbPXrZooCiMOdhPbSooB{JKbh^a~e?`_EWR_gpQCLJeYEE?Up\BuHxB?JWm`zC{MHB?JWm`zC{MHBCOWlQPd|`aHO[gyPtCkIIYiEGWpPCOJcX}EGSPcCUGuPokhmgWaMEoO?ohaRDEX`aFKXgzQjOpAsDsJoo@{c|L~BCLOiAWdYKXBCMWrPudUMXBCMWrPudUMXBGR?yAVCnH_SouCK_jA~FiR{gXPB`OqByI{cH^GX@LEKKkX`EAqEx`cEoSpKakeP`cGsPwc@lcAKEXYEO\phBqIi[]EOX@OcNJaYMEO^PVc`Jw\MEO^PVc`Jw\MEWQoh`SEYPslhnWX`jE?OOhHqwX`VDOOsn@lWX`~FIMc\PEa`E_`eECZ?|asdjJW\YEW\PcClKOWyEWcpYbnI{XorhfgXaHDCROfHMagen`eD[T@BQ{EtMzBKIwiAEdwLi\uE_`pLcqI_YiE_W?r`gEqNSl@twYA@FEP_fpfwY@QE]QCm`\QzE~`gF_WhJaVcoKMWqE_[@\cAIM[oxxsGY@WDMIsTpBqzeyM|BOQwkPxD\KrBOOGwqKC}K}]]E__PpcWH{X{{{LPHAoFUTkq{LO{bIHQWWq@crIOtCSHweXRrVOtAWLCYgtaNdrL|BSO_`PBBeGiRoshxgY`XDUOknp^r?ErM~BSJwtpzdfMjBSLonA?cFGOSWxsLOnbVFmU[yh|WY`^EmN[kxtRyouC?MOapEqMCzLE]eEoTPQcOJsZc{CL_|BHHWWOqKL_fBSHEV?wSL_qb[FqUWyXuRlFo`kHWUWzQmD`JCXYEoZOw`qDsO?h@pwZAGCwIKS`KQhEo`kFgXHJBAEPNvBWNOqQUECKa^mEw\pbcjKIWcpPar~OvBWJwWGoaBDDMTB[K_vP{DdMg]}EwRPfC]HIQWmPoGZ`UDWOcnhlb\e{NBB[PgbpGA_HkTWtcLpKAqFaTgrCLo}b`GqRssPzGZaWDcNCjPeCCovCoJG]HUbKGH`oDgJgV`TCMJwZ_z[M@FA\HiTStXkRXOwBSJs^xRBcOwAaLKc`[R_owCgJW\o{pyDXKu_YF?[p`ciKEWs~cM@@baGgR{gXPBRFg`oEKZOvpoBzJG\C}SM?gbRHGVCwICG[@PEeQOmHoSGOxB]J{_hQqedMMZBcOOyAJd?LA]UFGcPKaYD]N?k@ecCOxA]LGc@ZraFDMK_yFGapOcwIgYeFGW`lbyJE\G}KMOyBEEUKocx_bFg?`qDoSpAaGcQJuZ[{SMPDa`HoTOtIEw[aJDAR_i`iSLoyBKLw^_~P~DiMo^YFOdPYAvDoMojxdSAOyAuIc``]RYF[`sD?Y@GavFBO^BgLGmQ@dIMRBgNoxqHd@LGY[t@yg\AKC}R[iXTqkElOnBgMo]o}BCHOWCqP~w\@hDqOKhPqSQoyBQJc_XQbcgd`uCkIWT@jcfJm[\A{MotaoGSPCaP`r`Fi`uECYGtPjCwH{XW~{MpCbIFsTssYBw\`VFKOSm`\QzEPOHBkMgfaODFLq^YFWcp]CVI_\KzHubmOzB}Ik]@YBWGdPQaiFWaPdByIyYL@yJg\aHESNgjhgsFgm`wFKRXFaQceIKZO}CN?pbNHkRoqh}s?gA`wHOVXEQffWN@BoIGuQTd}J}W?xIFW]@iDaOcoporso{AsDsJowqBDrKc_MF__pRalD[NCkxjSSO{C[KS^@UrQEfLO`HEKN@IAzGqS{z@wCZo{CgJkbHRrkF_PnBsNoh`tddLUZCuQGw]`uBuFoSHFqaewNhBsLGjqDeDKQWgwHyw]`OEuQcnhqCNO|AuM__H@qCDqKY_]FgX`hCrHyXk~SNPEBEEUKo]xUbRGLPZBsQgnqIdUMa\s{XxCZO|BKLGeXNRLfyQHBsKosaXc|Ku^hGcN_pBOHgRcfPMrKf|QFBwJ_xqADoKW_UFoapaBuIwUCkPfsIGn`{C{ZpJQ|FKM]\@BcN`GaXCsJcbPSbjf^PtBwLwl@ZawGYWOvxxg^@sC}Psh@mbyfvNpBwOOiPvdeLSaEFoV@rcCJ_Wp?iQg^@[FMOOm@bCAhI`}Dc[gyPtCBJaWl@ARg^`mDiOooXoBqo~CGGSOoi@uDcLWa]FwR@kCgJw[hBYFsOO~CSK_^_~P~DXLC_xDcNpHB?GeTSy`wc[o~A}KsexNq`dCKo_@GKNo{aaHCSoupmr]Fp`}EwUhBB@f?NIdQFwZ`YcKKE[?{iTG_AUD{KCWPEAiFUMubmG?a@bbtJ?Y@AADSJGqa?ESXpKa_E[KyXw~aNw_@MEyQwdxKA|fJOtC?NOgAOdJIYSwuh{g_A?DWNGkXjsQP?BYFCMOkaFeALy]`IkO?ib`GCU{pq@cgP?C?Io]PWrVgcRDC?O?j@xDbL]aPKSOPEaNC_Kc^XVrQgRPVCCNghPvBrFgUgtqHcoP@AkMO^xZbGERKg_hHcOOeb[HSVcxqEG_`cEgRSgHdr{hAaAF[R_gpQCcISZK}[OPKAyGgTKixUBif]PpCCL_kqFE@L{][|hzcjP@AYLodP]RfGWRTCCHgvATDxM[``LSO_wAuG_W_w`pRbFkQtCGQwnQJCZGwTCyPwSYpABoHscXQRZfnaCDGZOvpoCkJo[tBIZG`A@DSMslHYquEhPCeEGO`p`bxI{YDAIKG`@WFCO?lhbsCgJOWc}GOW?r`gEeRCgPeb~H?aCF_RhGqcevN]fMGO]@McbIQZ[|y[w``JAeDO[HKR?fPPAfEGWWPUCkIeT[j@oSAgkaED[ZgzQdEeNydPJYVG`aREMP?gHqByfvNoeMGWYpOCUGuPonHesIHMaEFSUO}QvEjLaZGzyZg`aHD{KCWPGqtELNKcEGW^pfC?I}Z`BaMW``~E[O?jxmCMGxSDCKNwra?D^Lo`pFI_ga@hCuPOn@dcFHIQadIG_b@\ccJQUkl`cRqhBaGFwXw~qnExOu`|CAMc~PCA_MKehaBhfXMsa\M{P?rAfDYIwdPSR`GGP^COJWuPvBrFgScsY?ChpCBkFkN_kP|dlL_]HLKP@IbDG[SGwx{SqPCCiKS`pObbfpRGgqG_dPacMIC[[}IXDEPDAkL_\XPrOfzOA_HIkPPKBGGURwxh{CpHdRKgUGgbPFaOE?P{l@brsg~aICs[gyPtCrKM\HDA\Wa`vDiN[m`\QzEhN?eaGgX@SChI_[Owhpc@gqaIFsXh?QBcGIyZ\BiMs~pDBWIGah\rLGQQ`CSL_gaIdvKs`HIAdga`kDCPSmxecHHOSlCWQ_p`dbKGWRkxX{soiHaKGKYP?qmD`JCZTBALS}PEBeI{^_~P~DoL]\xLcP_gbgHmWOyqHcxhxRtCWJOVOnBZFWS_s@}SlPEBSICaX]bME\K{`LHydGb@bDKQ_iPnSDGoaKGwVxGarEMNM]s|qOGb@bDKQ_iPnSDGoS~CWKWhaSDQLy_hEAfwbaJDyQCkxartHCQMcaGw\@ZBtJeYozaYwb`aDSQwdxKAff?OGatR[PofbaHcWWyaHSSgiRpC[LwfQKD}J}W?rABsciRaMHCRGe``cNHw[g}qVtDpFAwLgZww@xDELC^|JKPp@BRGCTkupmr]GVPkgAGw\@ZBtJeYozaYtQPFBgJW]h[rUF[RUiQH?]@YAvDoNgmPjblhlTRC_J?v`wDDLI^pJCQ?wA^GmVsqyCCIgUQYg}H?S`rcwKIWcpPtSQHqaOG[VHGAqeOKeXO|APgcA@E_OSjPksLGvPybxNkQ@JbCGSPCaPNRfFqQygiH?W?r`gDQQ[ipncBGpSzC_J?v`wDDLI^pJAjgc@WE{N?ghhR}HWT\CcKgiqUdTME_d@YBCTi_aQEsMG[`NCYJwXTAIRDGpHCkKg`hNq`dCMQ]|KA`gc`MFKROfHMb@fWPCfQHG_@gbTEkOOjHlCKgwSBCcNOk@zDpLY]DLQZswIbaQG_V`FQqEQNWcIHGTPjbnIWYOsxiB~HUTbCcP?nAMdcKc]pGQnWcaGDwPsk`cbuHATzCgO_`PBBSGKU?vQFc]HzaSD{ShIqiE~OMaxEYLDMPIAqLo]HQqedMK}^hIykGd@KFGRWoPtsPhuaSHGXHAQ_FKM]\?}aVdCPICSJgbpHQRDbKW]lGimgd@mCwIKS`EQ|eXOYclQSQ_{arFoU{tPvRpfcRMiYHOR@qCuKC\\CY\daPIAWMOep_bjgbRkkR~~~~~~~")


     
del715nx = del715.networkx_graph()

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


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

##
#