# SageMathCell online https://sagecell.sagemath.org/?q=sgyljz
#  (6,4) = 390; Moore bound= 937;
# Graph with 390 nodes and 1170 edges communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
#
# Voltage graph Z_15 x(3) Z_13, D(2,2)
#    voltages [(2,8)<>(14,4),(0,0)<>(13,6),(9,4)<>(7,7)]
# Degree Distribution: [0, 0, 0, 0, 0, 0, 390] avg. deg.: 6.0 max. deg.: 6
# Diameter: 4  avg. dist.: 3.444730 
# 
# Ord.: 390 / Size: 1170   / Diam.: 4 / Avg.dist: 3.44473   
# 6-reg.? True / Degree histogram: [0, 0, 0, 0, 0, 0, 390]  / Girth: 6 /  Alg.conn. 2.26352
# Aut.group.ord.: 195 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False
#  
#  

import networkx as nx

loz390 = Graph(r":~?EE_A?G?_A?G?_E?W@_E?WA_I?gA_I?wB_M?wB_Q@GC_Q@GD_U@WD_U@gE_Y@gEaWAOd_kHWd`CHWd_sF?daYHgeaYHwfa]H?faaIGgaGIGgaeIWhaeEoi_{IgXAiIgiamDOjamP_nCUGpD`KJPDbcPXDb?NpD`[PhE_oG@EcOPhFc]Pw[C]QHGcaA`H_[BpH`wQWVCeNPI_kQgwCiQhIcmD@JbkQwFbgT@bdSWxBEMWw]CoVPbaOXHc`sXGLBCXWuEUXWGE?XWFAy@ou_[OHeeYDoZEYNpedkXwbE]XwKE]Jpf`ON@geaAXVEc^hjFyW`}`S^h?Es]@}cO^x~`?OP~dG_GoCw_I?ao^Q?bWNQ@gE_X\GEAPU_cE@^_cShvGITQA_wKQAgIN@YGM_wlgWeG]HaFpoGOeGzHaDP^G[eHsHeeXKEoeWR@sdqXhiS`ZHiHAYf_eh_HmD_rDwewlEiJOsFiJPshGfHjHqEA[bGRa[aCfXYFCfWUDQNaNIWkX?JEUQpbk]a]JEG`|JILPNFckgUEsaGUGuD_yCCjxSGUC@SGuSPSHQkw\COkwaFO\qr`SkyjJQLAscsZAs__CaEJQ[QPJUGPAJULPhdoiAuKaVrGfGqHXHOmRG`odrHd?ZqTKeLQc`cLQFIAFOtD[VbF`obQQKiqh@E?qgYBkqg^EeYPtIyobJ`CJAfKmZaGKmSRJhCibKcGWRKd?`HyLy]qzKsviOLyD@qIwrr]d?nwwD?fawcCS@oFcvW_L}NqcIkvx]FsvwYB[UR^b{jr__g[qIIswG}GQ`AJKQuB``KMQvMEC@tMEGaHI?wYiJowgMFKhiRLWybric{w{H?pBbNMA@\K[|GmGogRBNQGprJcsHrLQD@]FKbqT`GVAe`ggqeLiB`xH]B`\J{ogMB[Spqmw|WVBKart`ofqwNUM`WKw|WcJo|gqGolikMo|sE_gEQ|OYUahLg}cE`GJ@wLt@xUIGmbZO]bBgcKbBNMQBo{FcbAgIuFOqF_tBWbGdQnbGSpuHAC?PFklk@OaC?uC{gsGaOPCH`GRQaKuJ_wL\DhpJs{SKPYgb}eGgbbNeApYHSgazKMDP@CsyBmcsjRFcs\aMIeC`iJwsRobKMQRKvCsV_{KpQE{oCVcOWCW`CZa}MiGpUMtHIPL\?sXQQCQDLKxSA`wnbyOuBA}PAJppIsnbULmRpWIoygWA?ZbBLuMp]Ew~c@ewbadJuEC`QUApNFOabQQUW@|QYMQHLK|xBEg~Sq`ciblQdKg^BcxbzPQKRRPuB@?LLBCYdScRBLKzBodc]QHP@CwL@OLAHLmaQdKCtwsQ|KwnE{bQ`M\Kx|H\LHWH{xcIaGWaDR}MA{NtLc~bCVrePdIHjIgureNp?hqHSfs\QEK?{DCfroh{oRTMuEpPRpOHTGghAyN|OIVI|OX[EooSJ`{KQMMmBRSQlJgLEGYcRRycq_MdHxRD[fckSiirnNH?sKSiUqkJ?pBN__ErqPTJWGB?yCz_gMBWPTITM_gYsYSYArXMPFdL`KUsTRDPHoFWmSyT]]qGLTFtW`KE`lP@QwsD[ccpSeG@BDX?SpiomC?RUN`AD{ZS{TUDqdI_wtZTuGomMxGsuTuE?yF\Gs}b[MaFPtShREgltATMGPPF?is}bWmr@NhXGNKSsCPTpXW`ECaqgLaFo`C?RCna{zrxQyNQRHWjaxUM\BhMpETfUeF_oGTGTHUeO`tG{odHgwbrNSTRd`bwRadN`WhAFogqzMybR{O@ITodT@CLRlYDpfokBQMpCwZFk^ASHyE_mGXIIQLcvBpNhZw_J|Fc_VL\X[EC]aFS\\X`HWoBUOESbTLXBDUUudbEM[~C`SqLpUI\LtKVQpbqO|GC{f[pRELgwtJ_o\aDKxSWkCo~dEVt^yoLo~sQQ|SycPDCcuTT]Z[OTFCjS\UgkBt@SbRdRwXKH@CDPdU^")

loz390nx =loz390.networkx_graph()

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


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

##