# SageMathCell online
#  https://sagecell.sagemath.org/?q=eilbsb
#  F. Comellas and J. Gomez, New large graphs with given degree and diameter.,
#  Graph Theory, Combinatorics and Algorithms, vol 1, Yousef Alavi and Allen Schwenk (Eds.), 
#  John Wiley & Sons, Inc.; New York (1995) pp. 221-233. ISBN 0-471-30437-9.
#  (Proc. of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, 
#    Kalamazoo, MI, USA, June 1992.)
# 

import networkx as nx

H3=Graph(r":~?JWjW??BWLasO?AaIGl[??uBWJR??OwnQtO@@YB{kK?OhAbJV?CNowQro@C_K{kc?_Q@GJ@?GIWhAtoABiMgk[?`KbEJL?KB_LqsOBBEIkkk?o~baJN?KROpqrOC@[C?kK@?qAkJJ?OMoyqpoCCOJwlS@OQ`HJ@?SKgjQqoDBYLclK@PGbOJH?WBgMAsOEAsJOkS@_zbkJF?WQOsQqOF@]CCkK@olatJD?[LouasoFCuK_ksA?R@IJ@?_J_lapOGC?MKk{A@Ca~JT?cDGOqdOHA{J?`sAO|BdGn?cQ_qqOOI@?Coh[A_namG\?gMGzaMoICyKGc[AoX?yIX?kJgjqFOJCELobSApDbSHL?oCwPAdOKAiJcacB?vbnGz?oP_saROL?{Csh[BOjAvGh?sOGvQLOLCiKccCB_W?zIX?wI_mAIOMBoMWa{B`NB?HF?{D?OadONBMI[aKBp@BZGt?{R_oQPoO?}Ckh[C?sAdGb@?NGxAJoOCSLKcsCOW_xIX@CKohaGoPB_MsbkCPHbIH@@GDWPqboQBCJGdKC_}BhHv@GR?rQXOR@CD?hKCooArHR@KMW{a^ORDAKOfCD?Y?}IP@OKGkQSoSCIM?gKD@FbUHj@SD_PQboTAqJkdcDOyBoH|@SPgtqYoU@ECwhKD_ja{HX@WOova_oUCkKweSDoY_{IP@[J?maUOVByM[f[DpNbDHp@_DOPaboWBUIcd{E@AB^IB@_S?oq[OX@AC{hKEOsaiH^@cNWyA\oXC[LSekE_X_|IP@gLOiAVoYBcNCfsE`JbKHd@kI_wAkoZB_KShkEpDagIf@oKoxqmo[CEKoiKF@NApIn@sJg{Qlo\BoLWh{FPHayIj@wLWwaRo]BwLCaSF`EaaGp@{KOzAQO^BgJs`{FpOAjG|A?JGuAOo_CGK[akG@KAsGvACIGuqYO`B}KkdsGPHAxIFAGKWxQZoaBmLGeKG`BafHzAKJOzq\ObBWKCd[GpLAoI@AOIo{amocBqKwhkH@MaiIjASL?valodBaLSiKHPIarIfAWJwyAkoeCAKOh{H`DA{InA[LOuQQOfCIJ{aSHpNacGvA_KGwqOogByKW`{I@JalGpAcJ?yaRohBcL?akIPFauG|AgIWzQZoiBYLOdsI`CawI@AkKgvA\OjC?K?eKIpKaeIFAoJ_xaYOkBiKgd[J@GanHzAsIgyQlolCCL[hkJPIAhInAwKw{AkomBsKKiKJ`EAqIjA{JovqmonB]Ksh{JpMAzIfB?LGyqOooBeK_aSK@JAbG|BCK?uaRopCKK{`{KPFAkGvBGIwwQQOqBuJwakK`OatGpBKIOxA\OrBkKGdsKpLavHzBOK_zaYOsB[KceKL@GAdI@BSJWvQZotB{LKd[LPCAmIFBWIwoaiOuBeISjSL`FB\I\B[LGqQkOvCKIwjsLpObcIdB_K?sqjOwBuJ[jcM@JBmI`BcIGoqKoxBmJkckMPLBhGlBgKWrQNoyBWIccSM`HBoGfBkJOtqMOzB}JGdCMpBb^G`BoKwpq^o{B]IGe[N@IBkH`BsJosQ`O|CCIkesNPEBWHTBwIgnQ]O}BsJOfKN`MBaHZB{J?tAkO~CIIWjcNpJbeI\C?LOoAjP?ByI{jSO@FblIdCCKGqaiP@BcJ_jsOPNb[I`CGIOtQNpAB[JodCO`CBqGlCKK_pAMPBB{IgckOpLb]GfCOJWraKpCBkJKcSP@GBgG`CSL?na`PDCAIKfKPPMbYH`CWJwqA]PEBqIoe[P`Ib`HTC[Iorq^pFBaJSesPpDBjHZC_JGqqjPGBwI[jsQ@OBnI\CcLWsaiPHBgJ?jcQPKBZIdCgKOoQkPICGJcjSQ`EbdI`CkIWrAMPJC?JgcSQpGb_GlCoKgtaKpKBiI_dCR@CbfGfCsJ_pQNpLBYJCckRPKbpG`CwKosA]PMBoIOesR`DbbH`C{Jgnq^pNB_IsfKRpNBiHTD?I_pa`POCEJWe[S@HbXHZDCMOa`~pQCGHK`[So|a[GJDONoeAEpTBiIC_{T_uANGBD[NOeQBPWBaG[_CUP@aOGXDgNgdP~pZBgHw`[V@BAKGJDsLogAEp]C?Gw_{VozaVGBE?OOaQBP`BqHG_CW_wAZGXEKOgfP~pcBwGk`[XOxaSGJEWMobQEpfBYHW_{Y?~a^GBEcLwcQBPiCAHg_CYo{AGGXIGW?v`}QbEcM[`Ch@cboGDISXgyaAQeEGL_^shpjB`GTI_XwxQCqhEKMw_[i`]b[FzIkXOy@}QkEANC`CjPhb^GDIwYwuQAQnE[MG^sk@abjGTJCVozqCqqE_Ls_[kpbbeFzJOY_{`}QtEUM?`Cl``BhGDJ[WWwqAQwEiMo^smPeBYGTJgX?uqCqzD}MO_[n@gblFzNK]o}QnrrG[Qcl[{qGcnJDNKa`JAqrsFmNgj{|AOCqJTNOcXMAqRsHKRSks|P{BzI~NSaxMqsrtGsSCk[|QMc}JNNWa@KAhRuGeQshs|aJCiI`N[cPMQnRvHIRWjS|qSCrIxN_bHOakRwGwR{ic}ANc{IlNc`xJafrxGcQkiK}QIcpIZNgcHLqlryHGROjk}aRcyIrNkb@OAirzGuRsi{}qNDBIfNo_XAaar|GGO_gk~a@CHIJN{_xBAbS?GIOsgt?QBCJILSOghPantCIMSglDPAcDKJ@SOhHQqo~~")  

# Make a copy to work on
CG740 = H3.copy()

# First block
CG740.add_vertices([728, 729, 730, 731])
CG740.delete_edges([(139, 474), (168, 474), (142, 555), (221, 555)])
CG740.add_edges([
    (474, 728), (474, 729), (168, 728), (139, 729),
    (728, 729), (555, 730), (555, 731), (221, 730),
    (142, 731), (729, 731), (730, 731)
])

# Second block
CG740.add_vertices([732, 733, 734, 735])
CG740.delete_edges([(114, 634), (138, 634), (192, 661), (222, 661)])
CG740.add_edges([
    (634, 732), (634, 733), (138, 732), (114, 733),
    (730, 732), (732, 733), (661, 734), (661, 735),
    (222, 734), (192, 735), (733, 735), (734, 735)
])

# Third block
CG740.add_vertices([736, 737, 738, 739])
CG740.delete_edges([(86, 639), (143, 639), (166, 665), (196, 665)])
CG740.add_edges([
    (639, 736), (639, 737), (143, 736), (86, 737),
    (734, 736), (736, 737), (665, 738), (665, 739),
    (196, 738), (166, 739), (737, 739), (738, 739),
    (728, 738)
])


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



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} | Ord.: {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.conn. {algebraic_connectivity(graph).n(digits=6)}") #   Domin. number: {domination_number(graph)}")

CG740nx = CG740.networkx_graph()

# Write to adjacency list format
nx.write_sparse6(CG740nx,"CG740_s6.txt")
nx.write_adjlist(CG740nx,"CG740_adjlist.txt")

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()}" )


    # 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 from 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")


##