# SageMathCell online  https://sagecell.sagemath.org/?q=tdstuc
#  P'_13d  Graph from Canale with 187 vertices and 1330 edges. 10 vertices have degree 13, 125 degree 14 and 52 degree 15
#  deg. distrib.: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 125, 52]
#  diameter: 2  avg. dist.:  1.923524
#  Girth: 3
# 

import networkx as nx

P13d=Graph(r":~?Az_C?_C?_C?_C?_C?_C?_C?`cK@{L@wO`WN_gN_WN_ONAcC@{@@oNA[I@{F@{H@{G@wY_oNBCL@wQ__O`?O_gO`OOCCLACAA?^`GO`WO_GMACEA?e_WOCcFA?]`_P`_PDSHBg]DSCAwcDSJAgeDOl`?SCwi_GMAodDSDAWgDOk_o[Bwi`OXCOiD{BBW_DOo`gYCGi_wWCWiEkAAOhDOq`_P`_PFCCBg^EWw`?VBonFCDAgaEOw`OSC_lFCLAo_EwwFkAAWeEgw`G[CGmF?y`WXCwkFC@@oZCWuF@@_oYCgpF?z_WWDGsF?{_wQD?oF?~`_P`_PGsFBg_E_yGsBAwdEp?GsEAg]DpAGpG_GMA_`ExBGsJAogEP@GsHAWcEXCGsAB_bE?zGpL`gXBwpFpEHKIBWeD_{GsDBOhEg|GsGB?aDg~GpK__QCwnGhEIKBBg`EOzG{@@oVBwtFPF`GTCwuFpF`gSBooG@F_gUCWnF`F__RCOvGPF_w[CgkFhFJCEBGcE`BGxX`WZDGrFxFIcABO_Dh@G{IB?gDpDGxT`?QCopG`FI{@?OB?_D?oF@?H@OJ@oP`_\COtFpNIx__o\CWkFHPJsHAw_EOxH`^`OTBwsFHRJ[CA_dEgxI@X_WUCorFHHJha`WRBouFHLIxc`g[DGlFHMJ```?XCGoFHQIsFBWaDoxHXYK[@@oYD?nFHGJ@g_OWCwpFHNI`d_gQC_vFHIIhh`_P`_PLsABgcDw~HHZLPm_wVCwlF`GIxkLsLAggEgzH`YKHcLsBA_aD`@HpTLhm`OUCGpGPIJxgLpo_oRDGoFPOJhhLpq_g[BorGhJIpeLs@@oXCoqFhPI`fLsGBWdEw}Hh]KPmMKJBO^DpCHxXLXmMsCB?_EpBIX[KXmM[HAObE`?IPWKhmM{KAKDBgdDhAIPSK`uNcAAw`D`CIXYLHxNc@@oTC_oF`NJ`aNP{_wSBwqGhLJhdM`{`?UDGmG@PJXkMX{`gRCwsGHJJp`L@zNcJB__Dw}I@TKxoNcBBG]Eg~HPWKXwNcCBWgEGyHpULPvNcIBObEXBH`VLhpNcHB?eEwzH@XKpqNcEAOaEo|HH^LXtNcKAKKAIH`g\ComGXLJ@`LHyOAH_oVD?rFpIJ`dNX}PKGAg_D`DHHXL@vOqH`GSDGnGPNJpbMh|PKFAocEozI@SLhxOQH`ORCgqFxGIpjMY@PK@@o[COpG@RJhcNACPIN__XCWlG`JJxaMQBPIO_OZBosFhKIhkMqGPIJ_WYCwvFPQJPfM`~PKDB?^E@@IHVLPoOyHPcJAO`Eg{HpZKppOiHPsIBgfE?|HpXKXxOaI`WVCOsFXPIpaMa?PSFAghEHBIPTKpzOYIQ{DA_eEoyH`ZL@wNqI`GUBwkFxJJ`cMIGPSBAWbDo}IXSLPtOqI`?[C_tGHGJxdMp~PQ[_OXD?vG@OIxjNP|PQW_oZCGlGhNJ@fMYFPSCBO]EO{HH]LHoOQI`gWCgnG`IJh`LhvOiIR[@@oQC?rGPLJPkMQ@PQ_`?\D?uF`JJhfLy@PaV`OVDGvGHHJ@cLyDPY\_OTCgrFPPJxbLyAPy^`WSCWpFhGJ`hLyFQI__oUCwtG`LIhiLx|Pi]SsFAW`Dx?H`XKPnNyRSKCB_eE_~HxYLhnOqMRAb_gXC?mFXMJpdLyGQaZ`gZC_qGPRIx`KpnNqORIi`GYCOoGhII`kLyBQQYSc@@oWBokFpQJXjLy?Qq[SkBAO^DhBI@UL@nOaTSQg_GMBghDXCH`UKhoOqPRyi`gVCWjGhOJX`KXuOISSIe__TCGjGHLI`jNAGQiXTIo_oSC?jFxQIxaNIDPyaScAAoaDXBH@]KxvNqMRim`?RBwjFhIJPeNQAQq]Tan_W[D?jGPPJHhMIBPYZSkHBGdDW{IXTL@sOyRRabUSDBWfDX?HH[LhqOAQQylU[FBOeDW}Hp^K`rNiKSAg`WWC_jFPJJ@kMiCPiWTYw`OQBojFXNJhiNX~QAYSyt")
         
         
P13dnx = P13d.networkx_graph()

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


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" / 15-reg.? {graph.is_regular(k=15)} / Degree histogram: {nx.degree_histogram(P13dnx)}  / 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. 1: {distance_distribution(graph, 1)}")
    print(f"{label} distance distrib from vtx. 22: {distance_distribution(graph, 22)}")

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

##
##