# SageMathCell online  https://sagecell.sagemath.org/?q=lveyuh
#  (3,9) = 600; Moore bound= 1534;
#  Ord.: 600 / Size: 900   / Diam.: 9 / Avg.dist: 6.93289  
#  3-reg.? True / Degree histogram: [0, 0, 0, 600]  / Girth: 11 /  Alg.conn. 0.282379 /  Domin. number:  
#  Aut.group.ord.: 60 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False
#  
#  Communicated by G. Exoo (January 28, 2008 ).  
#  

import networkx as nx

exoo600 = Graph(r":~?HW_@?A?C@OAOC_H?c@CAGCOL?X?q@cCOGOO_`@SAcDGIOX?p@aBCFOMO[_xACCCGGOOd@HAQCcIOSOg`PAsDcJGUOp@`BAECLOYOs`hBcFCMG[O|@xBqFcOO_P?a@CSGcPGaPHAPCaHCROePKaXDCICSGgPTAhDQIcUOkPWapDsJcVGmP`B@EAKCXOqPcbHEcLCYGsPlBXEqLc[OwPob`FSMc\GyPxBpFaNC^O}P{bxGCOC_H?QDCHGQOcaPCQGcPGsPcbHEQPC`HAQCdPIQSchHcRCeHKQ\CxHqRcgPOQ_d@ISSchHQQhDPIaTCjPUQkdXJCUCkHWQtDhJQUcmP[QwdpJsVcnH]R@E@KAWCpPaRCeHKcXCqHcRLEXKqXcsPgROe`LSYctHiRXEpLaZCvPmR[exMC[CwHoRdFHMQ[cyPsRgfPMs\czHuPu_ENAIg{GlOFFfHs][fgDbubyNYSSBp{q@FrIYAW~HAb{cD@[^{oP~oq_uOIWh?hDO^GJKc_kogPcG`aOaWsHqDqhGVKiDXBhUcMe\A{aKkQGoE`ePQUhDHTOvGnFSa{Tg\cYeyPiUSNqMr`GzDyGXGHqc_dtC[c[DQPr]aUQYJHHhpPNHRDsdKxghckeaQqAsTqVrTH^@iJXKhkcq_|D{ekAQYp}bERaSHMHhPfHvISf[`gtc}fYRyZSZq_otIBGyMXPG[dC_\F[g{NQbrmbuSiPHQgZP~IZGshkMh@dOfQTAFs`qho`IfCIPXTgQdUaLG{jKIQkqmceTqXhVHtQVI~?Sj{lhLdabAUICsfqqpdJJ?ISXYGsdg`\I[l[ZQtpadUUyVHZgrQnJb?CmKYhXdsaQVQLslqzpLJnFIVX]ggdyelJ{nkEQ}pIeEWABh_GDRFKFHCo[ShdeEciWYASrrCqXKRHIYXbGEeKclL[p{CRFqYeuXINHcgPR^KjCCqk]hpeWaIXaDSxrLq|KvJy\XfgUe]a\M{sK[ROqeG~Awqcqa]rMI@?Wg[SbOOQJrDg`kwaBreI|@WkKEaqO]JNFgncIbGqAHPBG^CaaVRmHDBWckMa~o}KDCGokPbCPMIvIg^[TaDQqIXDwaCmahPaILEWhKYbJpmKtFGrk\a?p}FdLGa[`aTrYJ`GweKBazQQJTHWlkebPq]GrIGbcj`~RiHhJWh{HbFOAIjJwp[o`yrEHtLWasQakOIJfLw_cGaZp^CrOKxhwGbaDfaY{{S`p]sZMk]QLgaxyFVNLG{WlGRQfgb]Iu]xmBtPrDbNgt@zGzatfyZg|s[PVsxMw^AQgky?F\NdJ[ZlNrSfscyJm_pibzOBFJSStX}GmaVgQ[G~SepgsKL[^qRwtYFfCN|IKZLCbWG?_QI]ahpc@PDEfP_zy@HObViyZD?soPls]Lc_a@WzYperOT?{XLHBYGK_eBelHlSFQHD~Q[uyCHEbBhS[xASppsslLq`QCGqyWFOOlASX|Kr\gW_MAeepscLPtFVRovaFGPbLj{ZtBsHpotAL{aADWWZAE~PD@SD|QB_Gc`eEepPoSRQxE~SkwYIG?bbi[\`DSQPrtPMIaqAwRYiFYP\@kILTrbgo_}DUjPhsXPJDJU?xALGK`Nkk[dEsLOhteMSbaIwcZMFJPtBsJ\ZBeG{_YM}lxrs^OP@nVGzqOG\`xji\DGSNo}twLYcQGW_Y|ecQL?SN\_RhhGaAF}sPtCdPdCFW[yiRGU`bkY\dHsKOruOLkdALWiZHeeQd@sT\eRlhSaqHMrxjCj^~")

exoo600nx =exoo600.networkx_graph()

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


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

print("\n")
#