# SageMathCell online  https://sagecell.sagemath.org/?q=smugmm
#  P'_11  Graph with 133 vertices and 1274 edges, 14 vertices have degree 13 and 169 degree 14
#  deg. distrib.: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 169]
#  diameter: 2  avg. dist.:  1.923497
#  Girth: 3
# 

import networkx as nx

P13=Graph(r":~?Av_C?_C??S?_C?_C??K??k??{?_?G_?B_[A@{@@wO`?N_oN_gNA[F@{C@wQ`gN`ON`_N`WNBKH@wV_WN`OO`_O`gOBsJACMA?\_gO`?O_oO_wOCcHA?a_OO_GP_O[DCKAoaDCJA_cD?i__RCgg_gTCWg`OQCogDKGBW\DCLB?_D?k`oYBogDkFBG^DCEAw`D?q_WfD?n__P`WPEkEB_\E?t_gSC?nEkLAWaDOt`OTBosEgx`?QC_qEkMBW^DWtE{KB?dDGt`GYCGrEg|__XCWmEkFAwfEGtFCBColEgz`OP`_PGSGB_]EGvGSIAobEW{GSAA_jFpAGcJAW^E_~GSEAgeDw|GSFAOaE@?GSCBW`DhAHKLBOcDGwGSHBGfEOxGSMAw_DOzGPG_WdD`@GPK__[BwnG[FAo\EOvG[GA_dEWyG[AAWlF`B`oTCGkF@B`GQC?sFpB`WZCWhFHBI[EB?aEG~GXS_gYCwoFXBH{LAweDX@GXO_WcDp?GXQ`gP`O[C?qFPQJSDAocDg}GxOJSKA_`E_zHPY`GRCopG@DHxY_OTDOvHpSJSEAO]DowH`RJSFBWdDw~GpUJSJB?fEX@G`TJSCBO\D`LJHY`oXCOhF`HIHY_WbDW|H@VJSDB_`DGuH`WKKJAo]DwuH@XKcLA_\EGuHpU`oRCWqEpJI`^`_TC_oEpDJpe_OQEWuHHQKhg_oZCwiEpIIxZ`GWBwlEpLIHb`?XCokEpCIX[LcIAwdDouHx\LKBCOsEpEI@_LkMAKFAHp`W[COkFXDIp\MKHAodDOwG`QKPnMKCA_eEPGIhZL@p`?RC?hFhII@]M@p`gTBwmFpEJHkMHr`_QCwlExJKHlMHt_OZE@@GxPK@iMKMB?cDwxH`NJ`jMKEBObE_yHHWKXeMHs`OXBgjG@SKhmMHx_gVBorFxMIx^KxpMsDAKFB_bDO}HhNK@gNH}_oUBwhG@MIh\Lh{NsKAW\Dx@HHaLHvNsGAgfDW{H`UKXnMp}`oQCgpFhFJ@ZL`}`GZBokFPJI@dLXrNsAB?qFXEIX]KxzNsJBOeDovHPPJxyNsLBG`E?~H@QM@sNsCAwcE`CI`cLPtNsBC?rFHDJH`LpwNsGAKEAII`G[C_jFxHIXZLh|OII`oUCooFPEIx`LI?PSFA_]DH@GhSKXkNQFPSIAWfD_}J@cKxwNyI__TCOrHXNKPoNaBPSKBW_Do{Hp[L@zOiIQCGB?`DP?GxXJxeMiCPSABOpFHGI@\LxxPIIPcDBGdE_vHhTJpjMyI`WVBglFhKIP_MYGPQL_W^EOwHPUKhiMaEPQN`g[CglFHII`fNaDP[CAo_EHKIHdKpvOIJ`oSCwmFxLI@aLQCPYV`GTBghFXFIxcL@sPIJ`WQCGjFPMHx]NAFP[DBWaEO|G`XKXhNIJR[FB?eE_{HXQJhmNh~PYW`OYBwiGHRKHjMqGP[ABGnF@DJ@^LhrOYJ`_VCWkG@EJXoNQEPYY_W]E?}HHTJ`nMiAPY^`_[CorF@FKXjMQAPiV`gUCwsFhDIXgMQEPa[`GSCWoExKJH\KxqOYORsFAW`DoxG`VKhlMQGQI^_gQBwkF`GI`aKpqQY_`OZC_pFXTJxoMQFPyWSSCB?]DXIJ@_LHqPISRSGBOaDw}HpQJXiMQ?RIg_oXC?lGHEHxcLxqOaQS[AAwhFPLIp[LpqOIURYc_W\DO~HXPJpkMQDQi`Ss@B_fG@GIH[LHrOyPRqg_GUCH@HXUJXfNIAQa_Sk@A_^FhHHx^LpzPITRIfTs@AW]FXLIP`Kp{OqOSIb_GTC?~G`WJhjNQ?Py[Tc@AO\FHEIhbLP|OYURiiTk@B?bF@MI@cL`vPARRYaUC@BOdF`DIx_M@tOIQQyjUK@BGcFPIJHaL@uNyLRye_GVCOvGxRKhnNADPqWTIt")
         
         
P13nx = P13.networkx_graph()

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


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