# SageMathCell online  https://sagecell.sagemath.org/?q=nmtkkl
#  Communicated by G. Exoo (November 1, 2005). 
#  (7,3) = 168; Moore bound=302;
#  Ord.: 168 / Size: 588   / Diam.: 3 / Avg.dist: 2.67665 
#  7-reg.? True / Degree histogram: [0, 0, 0, 0, 0, 0, 0, 168]  / Girth: 4   /  Alg.conn. 2.53590
#  Aut.group.ord.: 84 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False
#  
#  M. Conder found an optimal (7,3) = 168 Cayley graph:
#  Ord.: 168 / Size: 588 / Diam.: 3 / Avg.dist: 2.67665 
#  7-reg.? True / Degree histogram: [0, 0, 0, 0, 0, 0, 0, 168] /  Girth: 4 /  Alg.conn. 3.00000
#  Aut.group.ord.: 336 /  Cayley ? True ---  vtx.trans. ? True -- edge.trans. ? False

import networkx as nx

exoo168 =Graph(r":~?Ag_C?_C?_C?_CH@CG`CG__G`CG`kAACCACB?wOaCOaCWA{RA{LA{PA{DA{EA{QA{@B[B@_Zb[Z_wZa_`ccc_gTCcKCcc_wg`Oi`_i`WNBo^DSCB?idSK`cKbSoE[lEGrd?r_WjE[ME[kE[FBSRFSQAo_CoyfSyfS_C[CBH?_OYBodGCSGCTGCzGCfGSUGSCCKCCSD@woFhEcpIa_`FG}HSJGXGH[RChLb_uFpCHlLcw}`WfE{fICNAoXEslIcAD_nGhQIdSb?bEHQ`wvJC@@OQEoxJDTJCHExKeOvaobEPGf`]_g]F?zFx]jsBBpFIKLCXDHXafhajxah`bfxbaXEH{SB_nEh`KsIFhEH@ZLKHB_eD`cLCsGXGIHXL[hH{_Dw~IXXipm`gxIhVKhlLsJFH@G{nJPpaGgFXXJXplxpbwwFxFHHg_oSB?qGh^MkMAO`Ghf_w[Gx\KhvkHvlPwf`eLc|GXHIPVNS\D@`KpgM`{_gjGXTNHzcGpK`gMP}boqIx[Lhq_wME`RJXnOCBDGkJXfixrOSNBPOJxqMaA_OWEPMKxzag^F?|GHdOkaDozGp\Kk@@oUBhBKyFk@yN{\FHMIX`KcNDHCHHyNYIa_aEpcLyH_oJGpxNYBPcIBwsGhRO[UDopJ`lMaMaOoI@TJhs`GbDGnFABQCLBweGH\PKA?WMB?}KIQ_GMBGdJxeaGmFxCJhcQceG`HJX[NK\DwoHpPPIU_odFhXLhxagaD`OKqHRCAD?pI@[KkI@WXDGsFyY_GHDGtFXnb?jE@FI@VRcPC?mF@JNS@BGYEPPNI]_gICPMIHs_o`CotG`VSCTCOsHX`MSE@GdFpTNQaaGjE@QJxl`GtEp@IXfSc[CgpFpHO[TBgjH@JLye")
conder168= Graph(r":~?Ag_C?_C?_C?_C@_K@_K@_KA_SA@CA_OG_SB_[B_[B_[C__O_cC__E@WLAcCAsD_gR_kD?wI@_]_kDBKEBg^_oQ_oa_oWBSEBSFC_d_wP_w[CSFAw__w_`GMC[MBOe`sG@sG@sM`?PAWSEOta_\a_iacSbOgbOqbO_CojaW_c?zc?jEGub_ecotaGjdW~GKGAwXEwwFkNGCNAg|`woE{H@wx`GNFSNE?wbWgESQB[ZF{ZCg{HKZFcJCGrGcPCG}cH@cGiH{`E{[Cwta?fcxCI[fDpAHPNcxAI@S`gkE_~aWkG[kFXMI[\D`OJKkFCHApEIcHB@EJsHFhQJcTCXLIPVJcTEg{H`aagrJ[TEPAIpaagsIKLB_}bG[EXWb_xHPQJCaE`BJp^KkKCPAHsaEgwH@gaoaKHcLCJD@BL@kd?yHHMJcVD?sHslEW}I`TK{IDg{J@gb?lK@eL{lEOvHXn`P?GxMIsIBh^KCIBxG`OQFXAI{OF@CH@\LsKA?{GHLa?nMcUFpPJsUG`VJh`LkUB?pFGyGhbbhdNC\J`hNCKDHJMp|dG}H@OIHXJ{RDH{dGrMCJEHFJhq`WmFHONcJDxHaGxFXILHkaG^MyCawnE@EJPhaxKIhzax@KxoMYI`gcHQEPcXC_oGpOMILc_xIhUNKQC`mOiIc`eNQ?bpEHhVKPdK{mEiDPAIQSmIxtOAGQKKG@FH`WMxw`_iIh`MqCOkQEw~HXRMcWGXSJXwPaOb?~HhRK@tQc^GXJHxTJPZbwsLPvNaDdPQMI@OQQQkiKy?OQH`gpGxRLYFPCLCgyJQEQIQaWyGHHMHrOCXIp^NH|PAKbGzKhiLaCP[dHhlNa@Pq]cgqNqCPq[dwyH`^NX|QCnKa@OyWRqd")

exoo168nx =exoo168.networkx_graph()
conder168nx =conder168.networkx_graph()

# List of graphs to process
graphs = [('Exoo168   ', exoo168 ),('Conder168   ', conder168 )]


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()} / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} / 7-reg.? {graph.is_regular(k=7)} /  Girth: {graph.girth()} /  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 7")
for label, graph in graphs:
    print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 8)))

print("\n")

nx.write_adjlist(exoo168nx,"Exoo168_adjlist.txt")
nx.write_adjlist(conder168nx,"Conder168_adjlist.txt")

##