# SageMathCell online https://sagecell.sagemath.org/?q=dfhxlr
#  (3,7) = 200; Moore bound= 382;;
#  #  
#  Communicated by G. Exoo (January 28, 2008 ).  
#  

import networkx as nx

bakhar200 = Graph(r":~?BGd??_KA_[C_kE_{G`KI`[K`kM`{OaKQa[SakUa{WbKYb[[bk]b{_cKac[cckec{?D{@DCADKBDSCDXO_gkIKEDhQ_wmI[GE{HECIEKJESKEXW`gsJKMEhY`wuJ[OF{PFCQFKRFSSFX_ag{KKUFhaaw}K[WG{XGCYGKZGS[GXgbhCLK]GhibxEL[_H{`HCaHKbHScHXochKMKeHhqcxMM[?_KA_[C_kE_{GNsHN[INCJNkKNSLN{MNcNNKOOsPO[QOCROkSOSTO{UOcVOKWPsXP[YPCZPk[PS\P{]Pc^PK_NQUcH~Q[aNaOcXxQkcNqQchzQ{eNAScx|QKgdKid[kdkmd{oeKqe[sekue{wSsxS[ySCzSk{SS|S{}Sc~SL?SQmgIfT\ASaggY`TlCSqigibT|ESAkgydTLGTQuhInU\ITaohYhUlKTqqhijU|MTAshylUN")
exoo196 = Graph(r":~?BC_C?_CD?cC_cH@CG`CL@cK`cPACOaCTAcSacXBCWbC\Bc[bc`CC_cCdCcccchDCgdClDckdcpECoeCtEcsec]bsYbSecsacSmdsidSuesqeSE_sA_SM`sI`SUasQaTAgT?gDEgtCgdIhTGhDMhtKhdQiTOiCyfSwfC}fs{fcZGh\gk^Gx^g{bHH`hKfHXbh[jHhdhknHxfh{rIHhiKvIXji[BFHlfKFFXnf[JFhTfkNFxVf{RGHXgKVGXZg\SO|^O|UOl\OlWP\bP\YPL`PL[M\fM\]MLdML_M|jM|aMlhMlcN\nN\eNLlNLgN|VN|iNlTNlkO\ZO\mOLXOKHBYK`g^PsPCYOagfQSXDYSbgnQs`EYWcgvRSBDI[_wlRsJEI_`wtSS@AYc_gVSspJQ^ehWRk@Jqb_h[SKHKQf`h_SkPKqNahcPkXLQRbhgQK`LqVchkQkhIqZdhSRN~~~~~~~")

bakhar200nx = bakhar200.networkx_graph()
exoo196nx = exoo196.networkx_graph()

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

def count_k_cycles(G, k):
    if k < 3: return 0
    count = 0
    def dfs(start, curr, path, used):
        nonlocal count
        if len(path) == k:
            if G.has_edge(curr,start) and path[1] < path[-1]: count += 1
            return
        for u in G.neighbor_iterator(curr):
            if u > start and u not in used:
                used.add(u); path.append(u)
                dfs(start,u,path,used)
                path.pop(); used.remove(u)
    for v in sorted(G.vertices(sort=False)):
        dfs(v,v,[v],{v})
    return count

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()

def compare_graphs_list(graphs):
    canon = {}
    count =1
    for label, G in graphs:
        s6 = G.canonical_label().sparse6_string()

#        print(f"{label.strip():15} : {s6[:40]}...")

        canon.setdefault(s6, []).append(label.strip())
    print("\n noniso ->",len(canon))
    print("\nGroups:")
    for group in canon.values():
        if len(group) > 1:
            print(count,"Isomorphic :", ", ".join(group))
            count=count+1
        else:
            print(count,"Unique      :", group[0])
            count=count+1


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

print("Degree histogram bakhar200:", nx.degree_histogram(bakhar200nx))  
print("Degree histogram exoo196  :", nx.degree_histogram(exoo196nx))  

              
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()}" )

compare_graphs_list(graphs)


# automorphism group structure
print("\n Automorphism group structure: x means direct product; : means semidirect product.") 
Abakhar200  = bakhar200.automorphism_group()
print('bakhar200 :', Abakhar200.structure_description(), ' |  center order:',Abakhar200.center().order())           

Aexoo196  = exoo196.automorphism_group()
print('exoo196    :', Aexoo196.structure_description(), ' |  center order:',Aexoo196.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 11")
for label, graph in graphs:
    print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 12)))

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

##