# SageMathCell online
# https://sagecell.sagemath.org/?q=aypopo
# MMS  (13,2)= 162  Graph with 162 nodes and 1052 edges 
# 13-regular; Diameter: 2 avg. dist.: 1.919255
#
# 

MMS=Graph(r":~?Aa_C??K?_?B_C?_C?_C?_C?_C@?[@?_M_K@_K@_K@_K@_KA?WM_OC@wX_SA_SA_SA_SA_SBA?Z_WPBcBAO\_WRBsBA_^_WTCCBAo`_WVCSBB?b_gMB[E@o[_wMBkG@o]`GMB{I@o_`WMCKK@oa`gMC[DA?X_oPBKFAOX`?RBKHA_X`OTBKJAoX`_VBKLB?X__OBWlEsCAG[Dov__QBgnFCCAW]E?x__SBwpFSCAg_EOz__UCGrFcCAwaE_|__WCWtFsD@wZC_u_oNB_dE{F@w\Cow`?NBofFKH@w^D?y`ONC?hF[J@w`DO{`_NCOjFkL@wbD_}_gOBOcDkEAGYCgm_wQBOeD{GAWYCwo`GSBOgEKIAgYDGq`WUBOiE[KAwYDWs`gWBOkEkDAW`CoqFp?H`W`WOBokDwzGpHIhY`?UBWhEgwGXNIPYJ[EA_aC_oF`@HhXJSFAgbCgpFg~HXVJP\`_PBwiDgxGxIIpZJkLAO_DWmFPDH@SJX]J{HAw[CwrEpCI@RJ`\J{IB?\D?sExAHpPJ`]K@`_gUBodE_yGHOIsGA?`D?mFhCHPXK[JAWZDWpExFHhRKXc_wWC?cEWxG@NIhb_oVBweEgzFxMI`bKsIAObCwlF`BHHWK`e`GPCOhDw}GPGIxcKxg`gTBgiE?uGpKIPdKpg`_SB_kEOwGhJIHdKxhLSDAG\CwpFXDHxX_wOB_hE?yGxMJ@k_oQBWgEOxGpOIxkLkJAwbC_mF@AH`ULcGA__DOsFo~HHRL`n`gUCOeDgvG`JIhlL{IAW^D_rFh@H@QLhoMKKB?`CgnEpBHhSLpnMKHAg]DWtF`?HPPLpoMPr_gWBwjE?wG`HI{HA?bCosFHDHhQMkLA_ZCwnFh?HpUMhu`OPCGcEgyGpJIXt`_RBghDo{FxOIhtNCJAg[D?lFp@HxSMpw_wVBoiEOvGXGJHuNHy_oUC?kEGuGPIJ@vN@y`?QCOdEWzGxKIHvNHzNcDAgaD_mFHBHpR`_OC?fEgvGHKIx}`OVBWdE?}GhIIh}N{HAo\C_qFhFHHSNsLAG]D?rF?~HhWNq@_wSCGjDgzGPOIP~OKGB?[CopF`EH@UNyAO[JAO^DGsEp?HXXOA@O[EAWbDOnFPCHxPOAAOaD_gQB_iEg|GPLIkEA?\DWrFpBHXUO{FAGZD_sF`CH`SOyG`?TBwcDwvGhOJAF`WWCOfEOyFxIIQFPSHAW_CglF@EHpXPAI`_UCWgE?zG@GIYGPYK`OSBoeDouGxNIyHPQK`gVCGhEGxGHHIIHPYLPsDAw_D?nF`FHXQ`OOCOiEGwG@OIaO`_TBWeEWyGPHJIOQKLAW[C_sFXBHPVQCHAO`D_oEw~HxUQAR_oWBohDg|GhKIYPQ[JA_\CgtFHCH@WQISQkGAGbDWqEp@HpTQQRQkFAo^CwmFpEHhPQQSQqV_gSCWhEWvGpIIcLA?^CgqF`AHxRRKHB?ZDOmFX@HXWRIY`_QBocEG}G`MIQX`OUB_jDwxFxKJIXRcGAw\D_lFP?HhVRQ[_oTCGfE_wGxGIiYRi]_wRCOgEguGhHIqZRa]`WPC?eE?|GXOIIZRi^SF")  

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


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()} / 13-reg.? {graph.is_regular(k=13)} "
          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)}")
          

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: {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")
##
"""
OUTPUT


 Main properties of the graph

MMS    | Ord.: 162 / Size: 1053 / 13-reg.? True  / Girth: 3 / Diam.: 2 / Avg.dist: 1.91925 / Alg.conn. 9.00000   Domin. number: 13.0

 Symmetry properties of the graph

MMS    | Aut.group.ord.: 93312 /  Cayley ? False ---  vtx.trans. ? True -- edge.trans. ? False


MMS    distance distrib: [1, 13, 148]

Number of k-cycles for k=3 up to 5
MMS     108 162 29808
"""