# SageMathCell online https://sagecell.sagemath.org/?q=kmgqkg
#  (4,7) = 1320; Moore bound=4373;
#   Ord.: 1320 / Size: 2640   / Diam.: 7 / Avg.dist: 5.71948  / 4-reg.? True / Degree histogram: [0, 0, 0, 0, 1320]  / Girth: 7
#   Aut.group.ord.: 660 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False
#   Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
#   https://web.archive.org/web/20091014041644/http://www.eyal.com.au/wiki/The_Degree/Diameter_Problem

import networkx as nx

loz1320 =Graph(r":~?Sg_?_?_?_?_E?D_D_D_D_J?I_I_I_I_O?N_N_N_N_T?S_S_S_S_Y?X_X_X_X_^?]_]_]_]_c?b_b_b_b_h?g_g_g_g_m?l_l_l_l_r?q_q_q_q_w?v_v_v_v_|?{_{_{_{`A@@`@`@`@`F@E`E`E`E`K@J`J`J`J`P@O`O`O`O`U@T`T`T`T`Z@Y`Y`Y`Y`_@^`^`^`^`d@c`c`c`c`i@h`h`h`h`n@m`m`m`m`s@r`r`r`r`x@w`w`b@w_o@w`}@|`|`|`|aBAAaAaAaAaGAFaFaFaFaLAKaK`HAKaKaQAPaP_QAPaPaVAUaUaUaUa[AZaZaZaZa`A_a_a_a_aeAdadadadajAiai_pAi`aAiaoAnanananatAsasasasayAxaxaxaxa~A}a}_VA}a}bCBBbB`CBBbBbHBGbGbGbGbMBLbL_eBLbLbRBQbQ`RBQbQbWBVbVbVbVb\B[b[bFB[aSB[baB`b`b`b`bfBebebebebkBjbj_MBj_~BjbpBoboalBobobuBtbt`uBtbtbzBybybybyc?B~b~`WB~b~cDCCcC_`CCcCcICHcHcHcHcNCMcMaTCMbECMcSCRcRcRcRcXCWcWcWcWc]C\c\`?C\_LC\cbCaca`zCacacgCfcfagCfcf`A`A`AcoCncnaICncnctCscsavCs_ACscy?UCxcx`_Cxcxc~C}_jC}cjC}bwC}`I_fDB_HDBdB_}_VDFdF_rDF_EdJ`qDJabDJ`K`KCP`K_B_iDQdQ_xBYDQ_O_O_OdYDXdXa{DXdXd^D]d]aDD]_sD]dc@GDbdb_mDbdbdhDg`\DgbxDgciDg_W`XDl_zDldl_K`HDpdp_@Dp_wdtacDt`pDt_Y_YB^_Y_t`[D{d{_FCKD{ae`NAe_[AeeCEBeBbmEBeBeHEGeGcZEG`eEGeM@yELeLbCELeLeREQaNEQ_tEQdTEQamaJEV`lEVeVaa`zEZeZaVEZ`ie^bUE^cFE^aoaoDjao`faMEeeea\C{Ee`s_\@s`M@semElelc_ElelerEqeqbhEqaWEqewAkEvevaQEveve|E{b@E{_BE{d~E{`{a|F@a^F@f@`oalFDfD`dFDa[fHcGFHbTFH`}`}D@`}aXb?FOfO`jDeFOcIarCI_aA?CIfWFVfVdLFV`NFVf\F[f[drF[`aBIF[faB]F`f`cgF`f`ffFebrFe_fAXFeehFecQbnFjbPFjfjcEb^FnfnbzFnbMfrcwFrd`FrcScSE~cSbJbqFyfyc@EOFybWa@BW`SAqBWgAG@g@dvG@_\G@gFGEgEdHGE_oB{GEgKCOGJgJbuGJgJgPGOcdGO`X@fGOfRGOb_c`GTcBGTgTbScPGXgXbHGXc?g\daG\cvG\babaETbab|ccGcgcbNEyGccVDcaEBcDc_h_hE`_hAr`C_FGlgl_TFFGl`PD?`PD|`PgtGsdOGsaJB|Gsf|GsdkdMGxcrGx_PGxd__dD@G|_JG|dUG|co_yH@eKH@etH@_uDmdm`LCl_eHFdZFcHFbdCyawCUCy`Z`ZFJ`ZA@_Q_xHNhN`FE\HN_^Di_^DR_^hVHUdyHUa|BJHUgfHUdAdwHZd\HZ`BHZcu`VDjH^_|H^ckH^dY_GHbeuHbeJHb_CDCdC_ZDV`WHhcpGMHhdoEw`IBiEwaLaLFt`\ALCVag`jHphp`xGZHpatES_aAtFPathxHwecHwbnDVHwhHHwf?eaH|eFH|`tH|esaHETI@`nI@eiI@eCa]IDf_IDgHIDaYFAfAapE@aIIJenGqIJdEEM_WC[EMa~a~G^_jA~Bd`ua\IRiRajFpIRaBE}`SABEfaBiZIYfMIYc`ClIYhjIYeUfKI^epI^afI^eIazE~Iba`Ibe?Ibem`kIfgIIff^If`gEWeW`~Eja{IleDHSIlfCGKamDIGKbpbpHBb@BpDocKbNItitb\H`ItcXFg`]AECXGd_jCXi|I{fwI{dMEjI{iLI{gSfuJ@fZJ@bXJ@gGblFhJDbRJDf}JDfWcAJH`CJHhQJHb}GUgUcTFTbmJNgBHuJNeYFa`{DsFacbcbHdaNCbDEbYc@JVjVcNG~JVbfGQ_kAwBfFz`\Bfj^J]gaJ]dwE@J]inJ]fig_JbgDJbcJJbf]c^GRJfcDJffSJfgAbOJj_QJjgoJjbKFkfkbbF~c_JpfXIWJpgWHR_TCQE]HRdNdNIFcdDNFC_mCp_mC~IddqGu_ZBABiDq`U`UEaF~`UJPhYhCK?gkK?czK?hPdKGvKCctKC_UKCgid[KG_PAgKGiUKG_~DWH[h[`]DnGg_\DLKMfmGp`FB_FGGpdxdxIhbrDxEY`_DZ`_DhIBdGHW`LAOC[DG_c_cFKFT_cJrgwheK[hMK[ddK[gnduHXK_d^K_`GK_hKcqKc`B@uKchsKc_LCmGygy_kDDHI`NDvKih]IV`xDkFqIVebebJJdyEbGWaQEDaQERJhfEHy`~CeDIFEayayFuHI`]Ayi]iGKwhoKw_LENKwiTe_HzK{eHK{`yK{hmeoL?_u@tCKL?jYL?abEkI_i_bAFBHka@E`LEg{HtajDAG[HtfLfLJldOFLFmbCEnbCE|JFe[I[apBsDsE[aGaGG_Gg_kAGh{iiLSiQLS_~ExLShrfII\LWerLWakLWiOeEL[_CAfBYL[iwL[`pEAH}h}aOEXIMarFJLaiaJZb\F?H?JZfvfvKIfMFvH]buFXbuFfKagYI}bbDzE]GYc]c]HCIMbAC]jajKLoisLo`pFbLojXfsI~Lsf\Lsb]LsiqgCLwaYBXDeLwkULwcFG?JcjcceGVIobdFtL}i?IxcNEUHaIxg`g`KeecG`G{cgGBcgGPKEfoJ_cTDPFGFobkbkHeHkaOBkj?jmMKjUMKabGLMKivg]J`MOgFMOcOMOjSfYMS`gCJC{MSjyMSbTFUJAjAbsFlJQcVG^MYjeKVc~GSICKV_RHDgaHDIadRGtLYdDFNFqH__wIGJQ_wCe`RKZ_TKJMcjwMc``HAJ}``Gm``D?juhLMib}CzEyMilMMid`HJK\__K\dzH\Js_sDEHBMojCJzdhFiIeJz`DHffwHfI?d|HVK}dnEdG[G}_EIiIo_EBs_`J~`FKfMykSMy_nHcKY_nHO_nDikQgjN?bKDdEON?kqN?cvGhK@`QK@dPGzKO_ADoHdNEk^LNeRHYJGLN`vIH_fIHJeefHxMQeXGbH?Ica[JKKOa[DzavLR`xLBNOkoNObDIEKubDHqbDESkmiPNUdWENGMNUmENUetINLTaCLTfNI`KkaWEYIFN[kBKre|GwJiKrahIj`XIjJCfPIZLufBFxHaIA`iJmJs`iDPaDKvajL^NelKNeaRIgLQaRISaRE}lIhnNkcmExFcNkliNkeJHlKxauKxedH~LG`eFCIhNqlVMFffI]KFMFbZJLaJJLK^fzI|M}flHgICJgc?KJLG_GC?FNcZMJb\LzN{lgN{chJILm_pChIuchFglejTOAekFbHSOAmuOAgHJRMLbgMLgbJdLcb{FmJJOGkzLjgPH{KbLjcLJna|JnKBgdJ^MggVHEIeJEbMKfKk_yBMEdbhLncNMVOQmCOQbvJkMI`bBvJWbvGQmAirOWeAGLGqOWm_OWf^IpLpcYLpfxJBM?bIGWJlO]_dMN_dGtJaK~_@C|KK`LJ|NigzIkJGK`dYLBM?_J@kDYGbdrMxc~MlOf__M^Ofd}KHMaaTD}Jxd}Gu`SM]_pKROlnaOl_}Mz_PHgK]M[`VLr`VHVJ?LZ_rDfKg_ZKXNSh\IIJiKDcoL^Lc_|A]CoFxdHMbdhNBOx`QMtOxdSKdMwbFDSKTdSHW_aMs`bJvO~nKO~_KMd`BHEKAMq_`AHaHHxKZLv`dEPLCapKtOUh~JoKFLXemLzMq`nBOEmHgfFNdeRNXPJaCNJPJfQL@NM_HBxFQKp_yFQHyawNIaTLJPPoMPPaaNf`tIkLUNG`RAzazIZJ~MRaVEzL_`~LPO?i`JMKbK|eCMVM[a`CAECHEe\NNe|NnP\auN`P\egL\Nc_zCjEgLL_GEgI[aEN_bFKnPbnwPb`oNPafIIKyN]aDBlblI|LRMhbHFdL{cTLlO|jBKhK~MPgAMlN]bRCqGAIkgZOPffODPnbgNvPngeLxNy_B@lGeLha]GeI}c[NubxMBPtotPtcEORbXJoMMNsavC^c^J^KvM~bzGNMWbbMHOjjdKLLZLtfWNBNGcDD[FWIIfpNzgPOZQ@cYOLQ@f{MTOO_tA^F{MD`kF{J_biOKcjLfQFobQFbSN|cJJMLqOI`QBhDKdKJ|MJNT_[CkGrMmkAL`LvM|hKNXOIctEEHKJo_|GtOnhiMjOd_i@fBPHi_@PXd_OyczKhM{O___CZDuduKXLnNj`MDUHTNCk]LDMRMfgiNnNsd^EoGiJM_JHVP@hGN@Ov`[AXCBHG_rPFcuOgddKLMeOqauDHE_e_KtMxO@a?E?HvNYkyMXMhNhiOODOqeHFYIOKha`HxPRimNVPHaMBJCrIm`D@dP|_MEsP]eNL`NgPCaCDrFIfILPMbOVaqEiIXNolUL|M~NRhmOZO_erGCHmKL`nIZPdiKNlPZb?B|D\IK_RAVPj`?EIPKexLDNQPU_RCYE\FsfsLlNdOkbcFSIzOElqNDNTOTjSOnPUf\GjJSL`cDI|PvjqOBPlbqClEFJq_HAhBH_[@qGGQAfbMXOSPg`DBgFFG]g]MHNNO}cUF}J\O[mMMnNjN~iqP@PCgFHLIqLDbRJ^QHjOOXP~ccDVEpJO_z@vBz`MAcF]PogLL|N}Py_K@vFpHAmeNpO@O{_AKQPRPygmHnKQMX_oD^J|QT_MKjOmQO_x@lCLCka?BUHPQ]_}AhGZHcm{NZOVOi_sJuPdPghOIPJuL|`aCtKXQ``?KNP?Q[_FA^BZDUaqCGGnQQ`oBZG~IEnQO\OkP_`eLIPvQWhqIrLINDaSErKtQl`qLbPQQga\BPDfE?bcCwITQuaaCLH`IgngOFO}PMaWKmQHQKiSJTKmMnbEEHLPQxacLFPcQs`jCBC|EicUDaHrQibSC|IBJIn}PAPOQCbIMAQTQoiuJvMANpbwGFLlRDbUMZPuR?c@CrEzFS`IEKJXRMcEDfIdJkoSOoPaPqb{LeQ`QcjWKRLeNZciF\MHRPcGL~QGRKbND\EPF}_WEuIvRAcuEPJFKHohPePsQ^jxKnMsO\`GDZEFGNd_EzJhKdozPSQEQRkTLJM]OF_UCpEpFdeIFdKEL@`WPLQIQvkpLfN_PAakEnFZHTesGNKaL\_eP^PwQjlLMBNIOo`yEDGDGrf]GrK}Lxa{PpQaRN_uLhOKPecOGBGkIXgGHTLYMTaIQBQURB_CMDNuPSb]FXHMHvgnHvLuMj_iAYOsQIhPIXMQN@`[@gOaPwhrIzMgNVaMB}PWQaiTJ\M}Nlb?BKPEQU`HIvNSOBbqDWP{Qy_VJXNiOXccCmPiQm")


loz1320nx =loz1320.networkx_graph()

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


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

print("\n")

##