# SageMathCell online  https://sagecell.sagemath.org/?q=btcrwd
#  Abas graph with 200  vertices and 1600 edges.  
#  Ord.: 200 / Size: 1600   / Diam.: 2 / Avg.dist: 1.91960 
#  16-reg.? True / Girth: 3 /  Alg.conn. 10.0000
#  Cayley ? True ---  vtx.trans. ? True -- edge.trans. ? False  /Aut.group.ord.: 200 
# 

import networkx as nx

abas=Graph(r":~?BG_C?_C?_C?_?@?k??S??c??[?_?E_?@_C?@[?@s@`GP`wP_GP_WP`?Pa?P_gPAOU_oPA[MAGT`?P__PA{AAGQ`OP_OKAGZ`WPBs@BcHAg``?XCKNB_`_o_CKOBo``WYBg`_ODBo`COe`oQCGb_WZCGd_w^CGf_WWCGa`_RCK@CKIAo`Dk@BWe`oXDGo`GZDwoa?QCwo___C_o_Go_g\COoEGs__RCWeECA?WVDgoE[GBOkDoo`wVDOoEKJAoWDWo`OKB_oFKEAgcCgoF[@@gT_OQDO{FsCBwnEw}_gFBGbF?}_oZDG}_gLB_qFp@a?VCWsFW}F{NA?\C_kFG}GCIAgeDw}`WUC?jEW}`_RCguFpA`oWD?yF_}`GSDgpFpF`?HBofEg}HK@`_RCgvHXK_w[E_{G@K`wUBOnEo~HcHBOiF@@GhK_oZDpCHcOBweDHIHcD@oZC_rGpFH`LIKJAgbDgyH`M_oIBojFXAH`O_OQDG|GXKH{CBGgEHHHcGC?aFHBH`Qa?WDguH@KHkBAwfD_qH@KI{@BhK_WLAO\ColFXMIKLAW]COkEXM`gUBofEGyIKLBW[HhX`gNA_nEhOJcLA?SCWtI@]`gZDPUIx\`OLB?XBO^C_sISLAOdFHSIh^_oLAwjEovF@N`?LA_gFhYK[H@g_DG{IXd_WSCwsGXCHPJIp__OSC_qFxLKKEA_cFH@GxXKSMA_jEPHHpWKkF@?NA?SAgdEXVKCKA_eH@NKcD@GSCWtGhOJxj__IAWSDGiFXEJ@\LSA?_SBgkFPAIXSIhfLkJA_aEovF?{G@PKsEB_kEhBHPJIH``OVCOtFPFH@UKXm`_VBgfEhEJ@aL{JAOcEhEIxdMKF@wOBWaEhAHpNKKCAodEh@IPcMCD@?YCWtG`OJhlMkBAggDGiEh?JHfLPs_OWBG^C?jEg~JH_`oRDgtFxRI`TJPeM{BBomEpEIPaLHv__WDowHHZKhnMsOAWmEPBIhXM@t`GXDozHXNKXlNKD@WVD?hDonFHAHh_NcKAogDGiDosGxMI@eM`}`o^DoyFh?Ix^L@tNkNBwmF`@HPYKxkNCFBg_DovFxUJxkMXzN{IAgeDpSKPiLXyNcIAOgDonEXGJ@`O[AAgmDwpIH\Ls@Gp}_OQCwvGxYKXcLPuOyGa?UBGjF`DIpaMHvNyG`GVC_|HPMJhlNQ?PCDC?lFPAJ@[LHwNyAPAHPSBBw_CWdEXHHx[Lp}PCJ@_WBw_D_pGpOIp`OaG_HCK@eKyG_oZD@DI`dL@zOqG`?[E_uG@TJpkNHzNiGP[JBG\DOrFxZKXjMQ?PAH`w]DGwHXQJxpOIDPCMAo\COzGHLJ`hMYBPAO__YDWxFxGIHVJ`hMYGQ[GBWlHPZK`rMh}`_YCg{GPXJX\L@vOyO`G^COxG`ZJpaLPzOAL_gVCgzG@RJPZKH~OiRQqV`_]CWcEPGIXSJPZK@|PSMBOiEwyGXZMHyOqJ`OTDGkExZKhhL`qOIKRCNAWgEPCIHZK`jMxxPqUa?_Dw|GHJJXeKxuOyT_oUCosGPEJPZJxmOYZ_WRB_jEHFJX^LhwNaORsFBoiFHIIPdMhxOySRSFAwcEHHIhcLHpMaFPiZ_wYDgwHXLKPbM@}Ri^_wG@GNAObDWyGpXKpqNaNQ{F@?HAWUCpGI@fL@qOQDQQa_wXD_nFhCJ@^M@sOqRRA`_w_DGqGhPJP]LhnNQOQqb_GVGSGAwcEHJHp[KhiMyEPqZTCNB?eDPBJ@lNYFQYWSIg`GWCgqGPPI`bL`pMaOSAg`WUBwjEXBI`\LHxNyTRyg`o_DwsF@?IxaK`lMP|QacTCDAWTCw{Fg~IP]Lp|NqgTIl`O\CWuF_|GxVKIAPY\SYgTSMB_uEw{FhHI@_NaHQqeSygTcBBGaFHEIXcL@uNQ@Rag_HDKpfSig_OYD?zHPNJxnMQCPQLRQg__]Dg|G@UJH]LXwOYQSQgUKKAOkE_yGHLJpjMiDQI]TAr`O\CgpGXCGhIHheMpwNiDPyk`W[FXGIPaLqEOyNQI[SYp__ZD`FIP_NyNQAZSQmTysUkAAWlE_xHHUKINRI^SA`T[MBoeD_~GHNJhiMaAPyUTYv_oWBGYCwrG@MKxhMX{PyUTQr`_TCOqEXTJxlMyAPyQSyhVKBAocEwwGPVJ@]LXtOaJPyV_gOBwiEpJI`cLxqOYNRqqVkKBolFXBG`DIxfL`mMp{PIZUSCB_fEXAHxeNQDPaLPqSRi`USB?_TDWsHh`OAEOyIQqiUQy_oQCOpFx?J@_NqXRQ^SAbUSEBgnEOyHHQJhiNACQYpUQvWKJBGYCoqGxUJ`hMX|QIVSqqVsI@WZCx@HHPJH^LhvPY[UQxWSA@o[CgwGpGHp]LXtNyWUQw_gNB?bExIIhaL@sOYTRqqVbE")
         
         
abasnx = abas.networkx_graph()

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


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" / 16-reg.? {graph.is_regular(k=16)} / Degree histogram: {nx.degree_histogram(abasnx)}  / 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)}")

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

print("\n")

##