# SageMathCell online  https://sagecell.sagemath.org/?q=ppwekq
#  (5,5) = 648; Moore bound=1706; Cayley graph
# The Cayley group is the 279th group of order 648 in the small groups database,  
# with generating set {a,b,c,x,y}, where a,b,c involutions and x,y have order 9, with xy = 1
#  Ord.: 648 / Size: 1620   / Diam.: 5 / Avg.dist: 4.23957 / 5-reg.? True / Degree histogram: [0, 0, 0, 0, 0, 648]  / Girth: 7
#  | Aut.group.ord.: 648 /  Cayley ? True ---  vtx.trans. ? True -- edge.trans. ? False
#  Communicated by Marston Conder ( m.conder@auckland.ac.nz ) on January 18, 2026. 
#  

import networkx as nx

conder648=Graph(r":~?IGbWAaDKIgTok`ZAyD{HGQoe`NBQEkLgZow`rBiF[KGWoq`fCAGKOg`pCaJCYG{NG]o}`~CqHkRgfpOabDII[QGcpIaVDaJKUglp[azDyJ{TGipUanEQKkXgrpgbREiL[WGopabF?A?K?g@oC_J?Y?{AGCoI_V?q@kBgFoO_b@IA[DGIoU_n@aBKEgLo[_z@yB{GGOoa`FD_SCUPOpYDDDkS[V@QP\DJDwSsVpRpSCxDSRkT`NPVC~EOTcXPUpeD\E[T{Y@WPhDbEgUSYpXp_DPECTKW`TPbDVCoQcRPIpMClC{Q{S@KPPCrDGRSSpLpGC`CcQKQ`HPJCf@OWCDP_oUED@[W[B@aOLEJ?wWsBpboOEP@CXKC`dOREVA?XcGPeoaE\AKX{E@gOXEb@gYSEpho[Eh@sYkF`jO^En?_UcAPYoIDl?kU{?@[O@Dr?GVS?p\oCDx?SVk@`^OFD~BONcLO}ouB|B[N{M@?OxCBBgOSMp@ooBpBCNKK_|OrBvC?PCOPCpACTCKP[P@EPDCZCWPsPpFo{CHBsOkN`BO~CNA_MCIOwoiBdAkM[J?yOlBjAwMsJozocBXASLkH_vOfB^???wwg?_EFF?G?gwG@_CFB?O@WugA_IEv?W@GuGB_GEr?K@?vg@?HE~?C@OvG??JEz?oAWzgE_QF^?wAGzGF_OFZ@?AwxgG_UFN@GAgxGH_SFJ?{A_ygF?TFV?sAoyGE?VFR@_Bw}gK_]Fv@gBg}GL_[Fr@oCW{gM_aFf@wCG{GN__Fb@kC?|gL?`Fn@cCO|GK?bFjAODX@gQ_iGNAWDH@GR_gGJA_Dw~gS_mF~AgDg~GT_kFzA[D`?gR?lGFASDp?GQ?nGBB?ExCgW_uGfBGEhCGX_sGbBOFXAgY_yGVBWFHAGZ_wGRBKF@BgX?xG^BCFPBGW?zGZBoGXFg]`AG~BwGHFG^`?GzC?GxDg_`EGnCGGhDG``CGjB{G`Eg^@DGvBsGpEG]@FGrC_HxIgc`MHVCgHhIGd`KHRCoIXGge`QHFCwIHGGf`OHBCkI@Hgd@PHNCcIPHGc@RHJDOJXLgi`YHnDWJHLGj`WHjD_JxJgk`]H^DgJhJGl`[HZD[J`Kgj@\HfDSJpKGi@^HbE?KxOgo`eIFEGKhOGp`cIBEOLXMgq`iHvEWLHMGr`gHrEKL@Ngp@hH~ECLPNGo@jHz?CL_[a{O?BYFKnK?ov@oJt?GLw[Q|oDB_FWnc@?w`vJz?[MO\A~OEBeFSn{AOv@sJh?_Lw\QyoJBWFWmsA_u`vJn?sN?^bAOKBqF{okBo|@{KL?wNW^RBoPBwGGpCC?}aBKR@KNo_BDOQB}GCp[DO|A?K@@ONW_R?oVBoGGoSD_{aBKF@cO_aauOWCIGklkEpBAGJ\@gOwaQvo\COGwmCF@CaNJb@{PObAxO]CUGsm[GPBAKJPA?OwbQsobCGGwlSG`AaNJVASQ?dbKOcCaH[rKHpHASKtAWQWdRLohCgHgrcI@IaZKzAkQoeBNOiCmHcr{JPHAWL@AoQWeROonC_HgsSJ`GaZLFBCR_gbQOoCyIKskKpNA_LLBGRwgRRotD?IWtCL@OafLRB[SOhBTOuDEISt[MPNAcLXB_RwhRUozCwIWtsM`MafL^BsT?jbEO{DQI{pkNpTAkK\BwTWjRFp@DWJGqCO@UarKbCKTokBHPAD]JCq[PPTAoKhCOTWkRIpFDOJGqsP`SarKnCcU_maiPGDiJkikQpZAwIlCgUwmQjpLDoJwjCR@[a~IrC{VOnAlPMDuJsj[SPZA{I`D?UwnQgpRDgJwiSS`Ya~IfDSW?paoPSEAK[kKTp`BCJDDWWWpQppXEGKgkcU@abJJJDkWoqArPYEMKck{VP`BGIxDoWWqQmp^E?KgjsV`_bJI~ECX_sacP_EYLKhKWpfBOITEGXwsQdpdE_LWhcX@gbVIZE[YOtAfPeEeLSh{YPfBSIHE_XwtQapjEWLWgsY`ebVINE{Z?vRGFsb[LcZ`cRyplEsL{qP|guBZE{XK}{[pmB`Kg]qMOvPoETNZFCZowrJFmb_L{[PdrvpvEqM?p`{GzBWFAWs}K\PlbaK[^IM_u`peNNfFk[_yRMF[bsMS\@fRmpxFKMkrpvg{BfFSX{z{^psBlL?\QNoyPuE`MjFs\OzrPFUbwMk\pgrjqBFIMor@uH@BcFYXczK_PrbmKs\iO?x`veZMvG[]?|RSFgcKNC]`iRsqDFcN[tPyhABrFkYk|[apyBxLW]APO|P{ElNBGc]o}rVFacON[^PjrpqNFaN_s`xHFBoFqYS{kbPxbyLK]YP_{`|efNNHK^`?QaGOccNs_@PSGqPF{OKgqChGB~GCS\A[dq?CDIO`QQp?QADHOjHS_P@qdGUcgOK_pQsJqZFyOOhaEHLB{GIStBKeP~cEI[`iR?~aBdNOvH{`@BQgFwc{Oc``SR{q\GSO{iP}hMCJG[TK~[gqECPIg^qSPBQGDTNzIC`pCqjF}d?O{aPTr~qfGQP?jA?HRCGGaTd?KhQDcQIs_IS`AaHdZOFIka`EQmGCdSPSb@VSAqhGkPkjq@hSCVGsT|?{jqKC\J?_aTpEQMD`ORIsbPFqpGIdWPkbpWsDqrGiPokaBHXCSGyUT@kkQJc]JK_yU@DaNdfO^J[c@HQsFGdkQCc`YRcqtHCQ[lPqhYCbHKUkx[mqQChJW[qVPHQSDlMZJccpIqvFMdoQ[dPZrfq~HAQ_m@sH^C_HQVCyKnQPciJc\IV`GaTdrMfKKd`KQyEoeCQse@\RWr@H[RKmpkh_CnHcV[u[pqWCtJoZQWpKQYDxLjKSePLq|EueGRKep]rZrJHYROn`mHdCkHiVsvKqQVcuJ{ZiX@JaZd~LvK{f@NR?E{e[Rcf`_R]rLHsR{oPnheCzH{WKv{sq]D@KG[AYPNQ_EDMBLCfpOrBFAe_R{gP`r`rVHqS?p@pHjCwIAWcwktQ\dAKS[YY`Ma`eJMN")

condernx =conder648.networkx_graph()

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


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

    
# Counting k-cycles for each graph
print("\nNumber of k-cycles for k=3 up to 8")
for label, graph in graphs:
    print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 9)))

print("\n")

##