# SageMathCell online  https://sagecell.sagemath.org/?q=rbbemv
#  (6,3) = 119; Moore bound=187
#
'''
 Main properties of the graph
rajiv119   | Ord.: 119 / Size: 357 / Diam.: 3 / Avg.dist: 2.67099 / 6-reg.? True / Girth: 3  /  Alg.conn. 2.17157 
exoo111    | Ord.: 111 / Size: 333 / Diam.: 3 / Avg.dist: 2.61818 / 6-reg.? True / Girth: 5  /  Alg.conn. 2.81985 
 Symmetry properties of the graph
rajiv119   | Aut.group.ord.: 672 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False
exoo111    | Aut.group.ord.: 333 /  Cayley ? False ---  vtx.trans. ? True -- edge.trans. ? True
 Automorphism group structure: x means direct product; : means semidirect product.
rajiv119 : C2 x (PSL(3,2) : C2)  |  center order: 2
exoo111 : C37 : C9  |  center order: 1

rajiv119   distance distrib from vtx. 0: [1, 6, 24, 88]
rajiv119   distance distrib from vtx. 9: [1, 6, 24, 88]
exoo111    distance distrib from vtx. 0: [1, 6, 30, 74]
exoo111    distance distrib from vtx. 9: [1, 6, 30, 74]

Number of k-cycles for k=3 up to 7
rajiv119    63 0 168 812 5376
exoo111     0 0 333 1110 6327

'''
import networkx as nx

rajiv119 =Graph(r":~?@v`o?C@WGC@gCA@WKD@g?@@g?A?wCB@GSF`_m?BGOL__a@AWKI__q?@wCJ`OeCAGWI_ouBBG?J__eEAGSI_OuC@wyNcHEQcxQOHaaPHAUMHA]NGqYRHQeQGqeSHqaTdh]WeXiZeBSvdbWveRKsdRKudrCterGsebCqfHu]fyA`gi@?PIG~OXx?PYDAOxpAPX{~PHt@Ox?iMBiMGrCrbaozNH?dLBUYLc\GSHk|OCDNer\GRCyYNcDDRXKmMRyNHBOvcq_qLg{lMBuXLSXKTxSzOsPWeRh?OtUTKSXHThGnMRuQHrGvdrLFQdyVNB|DVXOoMbqPHbCucQkzNhOhKrUUKcdJXH_wNsHbdbdAPEEWLChJWi?iIsX\VxobHB|VUxokJShTUY?dHcL]WHsfIS@aXhsnKCpbYH{iJclNSxwcHcDcXx{dICHMShwjJS``XYGmKC\WVIGgISTUUiCbHsPOTICkJsdLS^")
exoo111 =Graph(r":~?@n_GA?_GA?a?]F`w]E@wCF_WyMbgSMa?yGdGKSdGoS__{SbwWYa`iY_PiHDPiT_os_cQA_aAAOEqABEwgRHh[ehg{eaaEPEQm\IymDDQmECQ]VFrACGrAobP[k`@sdLGkhLJQRFREBAqKwcaww_baXGrUICac{eBK{aRq^IRePEAx?fb\?`P@?hQw|dpwrPGOcMsQKDcQBKsE\HB\Gaqg~QGC[QGSILsUbIblK___aRGoPMsehJr|NaO{gRwCVNsuEJcLQc@SlSg_\OtALKs\Td`kqTW{bPtMRLslWfACuUGGTISlUga[yUwcZJcxXiAo}VWGOGRLPjRDAVwOHDa[vTGkOFAozTxGUGbC~Uh_[IBTBVHwaJRdFViOgKbtJWGOiJRX@RgknKbhDSWWQLbxHTGsWMcHLTxK]NcXOUhccOchRVGS^IcXUVgodJshXWN")

rajiv119nx = rajiv119.networkx_graph()
exoo111nx =exoo111.networkx_graph()

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


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()} / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} / 6-reg.? {graph.is_regular(k=6)} / Girth: {graph.girth()}  /  Alg.conn. {algebraic_connectivity(graph).n(digits=6)} ")# /  Domin. number: {domination_number(graph)} ")

#print("Degree histogram rajiv119 :", nx.degree_histogram(rajiv119nx))  
#print("Degree histogram exoo111  :", nx.degree_histogram(exoo111nx))  
   
           
           
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()}" )
print("\n") 

    
    # automorphism group structure
print(" Automorphism group structure: x means direct product; : means semidirect product.\n") 
Arajiv119  = rajiv119.automorphism_group()
print('rajiv119 :', Arajiv119.structure_description(), ' |  center order:',Arajiv119.center().order())           
Aexoo111  = exoo111.automorphism_group()
print('exoo111 :', Aexoo111.structure_description(), ' |  center order:',Aexoo111.center().order())           
print("\n") 
    
'''    
print("\n Properties of the graphs as at arXiv\n")
for label, graph in nonisographs:
    print(f"{label} & {graph.average_distance().n(digits=6)}  & {graph.girth()}  &  {algebraic_connectivity(graph).n(digits=6)}   &  {graph.automorphism_group().order()} \\\\ ")
''' 


# 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


for label, graph in graphs:
    print(f"{label} distance distrib from vtx. 0: {distance_distribution(graph, 0)}")
    print(f"{label} distance distrib from vtx. 9: {distance_distribution(graph, 9)}")
    
# Counting k-cycles for each graph
print("\nNumber of k-cycles for k=3 up to 7")
for label, graph in graphs:
    print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 8)))

print("\n")

'''
# from 0 versio Molodtsov 
for name, G in  graphs:
    fname = name.strip() + "_adjlst.txt"
    s = "; ".join(
        "{}-{}".format(v, ",".join(map(str, G.neighbors(v))))
        if G.neighbors(v) else str(v)
        for v in G.vertices(sort=True)
    )
    with open(fname, "w") as f:
        f.write(s)


# from 0
       
for label, _ in  graphs:
    base = label.strip()            
    G = globals()[base + "nx"]      

    with open(f"{base}_edges.txt", "w") as f:
        f.write(",".join(
            f"{{{u},{v}}}"
            for u, v in sorted((min(u, v), max(u, v)) for u, v in G.edges())
        ))

'''
# from 1
        
for label, _ in graphs:
    base = label.strip()   
    G = globals()[base + "nx"] 

    with open(f"{base}_Zedges.txt", "w") as f:
        f.write(",".join(
            f"{{{u+1},{v+1}}}"
            for u, v in sorted((min(u, v), max(u, v)) for u, v in G.edges())
        ))
       
print("\n DONE \n")  

##