# SageMathCell online
# https://sagecell.sagemath.org/?q=zuzsvr
# (4,5)=364 Delorme, generated by Vlad Pelekhaty
# The variable G is the graph in sparse6 format .

import networkx as nx

Del=Graph(r":~?Dk_A?G?_E?W@_I?gA_M?wB_Q@GC_U@WD_Y@gE_]@wF_aAGG_eAWH_iAgI_mAwJ_qBGK_uBWL_yBgM_}BwN`ACGO`ECWP`ICgQ`MCwR`QDGS`UDWT`YDgU`]DwV`aEGW`eEWX`iEgY`mEwZ`qFG[`uFW\`yFg]`}Fw^aAGG_aEGW`aIGgaaMGwbaQHGcaUHWdaYHgea]HwfaaIGgaeIWhaiIgiamIwjaqJGkas^glauJgmayJq?a}Jwob?`wobC]wpbEKaNbIKgrGiKwrbQLGsGYLWtGELQXbY??ubWawvb[cwvHyMGwFeMAAbeMP|bcewyFiMgyHUMqHbmMqkbocG{IANG|IeNQCbsdg}HuNg}HENq[b{^G~JMOAbc?bH?cCeH@F}OQvcGhhAJqOaDcK]XBH]OqqcOqXCGyPAdcSaHDI]PQxcWdHEFyPatc[chFKIPq`c_nXGIsrxGGMQQncc_HHGKehIIkqxIJ}QaFckbXJH{sxJKURA\KiRAKcophLKARQhLuRQDLaR`~cwfBScwkHNFiRqWLmRqrd?qHOHASAbLASQeMESQHMYSQydGjBadGnHQGOyxRHCzhRKMSq_KyTAvdO^HSHSthTKETQRMuTQaMQTamL]TazdW_b|d[^Rod[lhVHWrXWFk{XWHcshWJP@HXIOwHXG{xxXK]UawO]UaINmUagLeUq}OAUqiLUUqENaVAJMaVA]LqVALKQVQZKqVQ@NYVQpOyV`xOAVatLeVaYNuVqjMuVq|MAVqGP]WAMOyWBALIWA^J?{H`I{tx`Fx@x`H[}HaGLEhaI[yHaJ{xHbIS|c\eKpRLeKccJeOdBzQaXA?OQXAqLUXRHKqXQ`NDFhdGtBxeG\CheJcvHeIsxsee[mBIe[jbqQeXqEPAYA@PQYAUMXFxgJOvXhIG}csecasDecprSNIY`zPUYaZMlGhiJWwXjIgzcjekmrOekacLeooRZRmZA]NxKHkG|?XlKOtcueshBxQ}ZQROYZaAOeZagNTHHmJwrbPe{eRiPqZp|PeZqpMHOxoIW|sZf?oBWSQ[ACOa[P{Oi[QoK|MHpH_|CmfGpbbSm[aPP`OXqIKySdfK]cKfKlrPRe[q[M|KhsJouc~fOiR~QE\AHNx?htHszCkfSor^S}\QOPXSxuI?xSffWbCRTQ\bGLxQhvGT?tYf[mbRS]\qkNpGHwJKqs|f_^rBPE]ATNLK~")   # (4,5)=364 Delorme



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


def check_all_isomorphisms(graph_list):
    n = len(graph_list)
    print("\n Isomorphism check of all pairs (a dot means non isomorphic):")
    for i in range(n):
        label_i, G_i = graph_list[i]
        for j in range(i + 1, n):
            label_j, G_j = graph_list[j]
            if G_i.is_isomorphic(G_j):
                print(f"\n{label_i} is isomorphic to {label_j}")
            else:
                print(".", end="")
    print()  # Newline at the end

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 graphs\n")
for label, graph in graphs:
    print(f"{label} | Order: {graph.order()} / Size: {graph.size()} / 4-reg.? {graph.is_regular(k=4)} "
          f" / Girth: {graph.girth()} / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} / Alg.connect. {algebraic_connectivity(graph).n(digits=6)}")

print("\n Symmetry properties of the graphs\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()}" )


Delnx = Del.networkx_graph()

# Write to adjacency list format
nx.write_sparse6(Delnx,"Del364deg4D5_s6.txt")
nx.write_adjlist(Delnx,"Del364deg4D5_adjlist.txt")
nx.write_edgelist(Delnx,"Del364deg4D5_edgelist.txt")

# Check isomorphisms
# print(f"Are isomorphic G5 and G6? {G5.is_isomorphic(G6)}")

# check_all_isomorphisms(graphs)

# 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: {distance_distribution(graph, 0)}")


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

print("\n")
##