# SageMathCell online https://sagecell.sagemath.org/?q=naufdu
#  (6,4) = 390; Moore bound= 937;
# 

'''
 Main properties of the graph
rajiv441  | Ord.: 441 / Size: 1323 / Diam.: 4 / Avg.dist: 3.55974 / 6-reg.? True /  Girth: 3 /  Alg.conn. 1.83591 
loz390    | Ord.: 390 / Size: 1170 / Diam.: 4 / Avg.dist: 3.44473 / 6-reg.? True /  Girth: 6 /  Alg.conn. 2.26352 

 Symmetry properties of the graph
rajiv441  | Aut.group.ord.: 12096 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False
loz390    | Aut.group.ord.: 195 /  Cayley ? False ---  vtx.trans. ? False -- edge.trans. ? False
Degree histogram rajiv441  : [0, 0, 0, 0, 0, 0, 441]
Degree histogram loz390    : [0, 0, 0, 0, 0, 0, 390]

 Automorphism group structure
 C_n is the cyclic group of order n;  x means direct product; : means semidirect product.

rajiv441  : PSU(3,3) : C2  |  center order: 1
loz390    : C5 x (C13 : C3)  |  center order: 5

rajiv441  distance distrib from vtx. 0: [1, 6, 30, 135, 269]
loz390    distance distrib from vtx. 0: [1, 6, 30, 136, 217]

Number of k-cycles for k=3 up to 6
rajiv441   63 | 189 | 0 | 1071
loz390     0 | 0 | 0 | 780

'''

import networkx as nx

rajiv441 = Graph(r":~?Exb{C_bakKGkBYG?l_sLw\BUG?`b_MgM@AHon_OEG`BqHOx`cIgB@aJ_n`KHGY@y@odbCNgZ@}A?q_WHWmBiA_r_cHgFBID?sa[LgGAYA?r`WKGJAaA_gaGJwhAuB_pacMwiAmBoS_CLwjAy?_O_oKWRBMCO{_sDGgByD?x`GGgA?yDO|`KJGNBq??b`sKgOAI@Oc_wKwPAqC?x_sBwHBQCO|`oMgUBUDOt_gKGYBeE_zbWMGZB]F?b_K@GrB]FOc_OIggBa@O]`[MwUBe@_^`[LwaBuDOy`_GwhBQC_q`cHG@BUGo}a?HgD@iH?saCKGE@m?Ol_GGW]AY?___KNG^BAAon`kNWO@IF_}`_FG?@IFos`cFWD@MJ?l_W@wCBeF____AWiBu?on_cLgpBUA_J`cMGNByAol_oMw[BQB?j_OEWeBuBOm_oIg?BACORaSJW?BY?O_aSJGJAe@On_[MgLAm?of_SJgJAIA_U_?Iw^AEHot_oBgEBy@oG`GFWzBqA?I_wCwWB]AOS`{HG[AeDOUa[KW@@uAOf`[MG?AqE?r`[Ew@?uEOg`[LgABi@?d`?DGU@iDO[_GMGFAyK_{`[EgKAeBoP_KGWqBmCOT`kGgeAi@_p`wGwNAa\`vI_iZ?KCrrPNqorCMCwb{NugA`K[qHeE_xBdN}daVLwvr~OAfq`IKhJfM_zRnOIY`jE{[CAOMlQuKsrhJCo`qHOUgacNK|SDOYjanMkzIIGonQ~OaQ@IG[aSGOeqbJKorhxFgiqkOmbaNHcecJOqT@UIwkJQLK}bzOycQQHofSMO}TpWLWtxQDKjaoPEqRJMszcPPIV`^LcuhYDkkQrPQTPULWtsSPU]p{LovYsJWwbbP]TpXJCksVPaU@XLcui@GKsBPPiWPaJ_mSYPmVP]J_mYeI[rBLPumq{KWps\PyYPjLGtIyJo{BpQAna~K?oc_QEZ@mFk^XACOxBdQMoRAKcqcbQQPPEE{[HcESsbSQY]@yL_uceQ][`rNO|XfE_]p|QelqwNc}chQi^@|MgzHtFWhQeQqPPEEgYskQu^q?N[}HwFcpBDQ}ZPmNO|SnRAO@@I_iYVH_tRVRIZppIShcqRMR`OIkjHhEguBYRU[`sKOpStRY[@pMgzHfE_Z@mRaUp[LovSwRe[psN[}ISHSzbnRm_aBL{wCzRq^`~L{wH\D{sBPRybQMMgys}R}bQNN?{j`MKxrhSEcAQMOxd@SIcqTI_ihGCgQpKSQuBXMSxdCSUdaWIkjXJCsnQ~S]lqxM_yTFSaR`NHceiDGW{BqSi_QAMgytISmSPQHofYCGSxBeSuhQfNW}DLSy^a?MwzyGGciAiTAmazLkvDOTE\PvLStyJGoiqlTMO`BLwvtRTQiQiNc}y^I?karTYR`NGwbtUT]jAlLkvYaIKrrOTeSPQHCcdXTiOpCK[qHEC[gqcTqeQZJGkt[TuP`FH{gXGCc{rtT}fA]K{sD^UAW@aKorYOHC|bwUIZppFS\daUMeaZNc}yGGccqTUUO@@FW\tdUYfQ]LkvYJGodaWUaR`OFc]dgUeorDKWqHQDKT@UUmR@LMkzDjUqeQZH{gHVDcU`ZUynQ}NW|tmU}QPIKsrhYDowbbVEsrSLwwDpVIVP]ECWiIGkyBhVQZ@lNc}dsVUW@`KWpxbES{BpV]cqSLkvDvVaWpcK?ohJCsaaKVikQqNW|tyVmX`fKcqhbEOna~VuNp@K{sT|Vy[`sF_]YnJ?pbGWANp?MCwe?WEOpCI?gYnJ?orDWMW@`JknEBWQRpOKorhSDSzRmWYX`fKCoeEW]QPIJSlhND?qbJWeW@aIWhuHWiVP^GC_w~CCoB@WqfA]IGguKWulAtLwwHcESYPjW}SPRNg}uNXATPUD[UHtF[dqWXI{RqNK|EQXMU@XDwVxhEg]@yXU`qGMSxeTXYUp[Fk^I\HwjAlXacqSJgmuWXe^`~GG_ysJSsrSXmO`BHWduZXqU`[JOliCGWxrhXyNp?KKpE]X}`qGL_uYCGScAQYEO`CEWYE`YIaaJJ[mYCGWwRbYQPPFMszucYUR@LIwjxoFC^@|Y]_QAGsbefYa^a?HOdXDC[xrgYiT@TKcquiYmtRUNK|IDGWbQNYuWpdJgnElYyZPmFG[xGCcgacZAtRUNC{eoZE[psF{_IOHChQfZMkQqJsnerZQSPRLGsyYHkiQiZYZ@lJ[mEuZ^")

loz390 = Graph(r":~?EE_A?G?_A?G?_E?W@_E?WA_I?gA_I?wB_M?wB_Q@GC_Q@GD_U@WD_U@gE_Y@gEaWAOd_kHWd`CHWd_sF?daYHgeaYHwfa]H?faaIGgaGIGgaeIWhaeEoi_{IgXAiIgiamDOjamP_nCUGpD`KJPDbcPXDb?NpD`[PhE_oG@EcOPhFc]Pw[C]QHGcaA`H_[BpH`wQWVCeNPI_kQgwCiQhIcmD@JbkQwFbgT@bdSWxBEMWw]CoVPbaOXHc`sXGLBCXWuEUXWGE?XWFAy@ou_[OHeeYDoZEYNpedkXwbE]XwKE]Jpf`ON@geaAXVEc^hjFyW`}`S^h?Es]@}cO^x~`?OP~dG_GoCw_I?ao^Q?bWNQ@gE_X\GEAPU_cE@^_cShvGITQA_wKQAgIN@YGM_wlgWeG]HaFpoGOeGzHaDP^G[eHsHeeXKEoeWR@sdqXhiS`ZHiHAYf_eh_HmD_rDwewlEiJOsFiJPshGfHjHqEA[bGRa[aCfXYFCfWUDQNaNIWkX?JEUQpbk]a]JEG`|JILPNFckgUEsaGUGuD_yCCjxSGUC@SGuSPSHQkw\COkwaFO\qr`SkyjJQLAscsZAs__CaEJQ[QPJUGPAJULPhdoiAuKaVrGfGqHXHOmRG`odrHd?ZqTKeLQc`cLQFIAFOtD[VbF`obQQKiqh@E?qgYBkqg^EeYPtIyobJ`CJAfKmZaGKmSRJhCibKcGWRKd?`HyLy]qzKsviOLyD@qIwrr]d?nwwD?fawcCS@oFcvW_L}NqcIkvx]FsvwYB[UR^b{jr__g[qIIswG}GQ`AJKQuB``KMQvMEC@tMEGaHI?wYiJowgMFKhiRLWybric{w{H?pBbNMA@\K[|GmGogRBNQGprJcsHrLQD@]FKbqT`GVAe`ggqeLiB`xH]B`\J{ogMB[Spqmw|WVBKart`ofqwNUM`WKw|WcJo|gqGolikMo|sE_gEQ|OYUahLg}cE`GJ@wLt@xUIGmbZO]bBgcKbBNMQBo{FcbAgIuFOqF_tBWbGdQnbGSpuHAC?PFklk@OaC?uC{gsGaOPCH`GRQaKuJ_wL\DhpJs{SKPYgb}eGgbbNeApYHSgazKMDP@CsyBmcsjRFcs\aMIeC`iJwsRobKMQRKvCsV_{KpQE{oCVcOWCW`CZa}MiGpUMtHIPL\?sXQQCQDLKxSA`wnbyOuBA}PAJppIsnbULmRpWIoygWA?ZbBLuMp]Ew~c@ewbadJuEC`QUApNFOabQQUW@|QYMQHLK|xBEg~Sq`ciblQdKg^BcxbzPQKRRPuB@?LLBCYdScRBLKzBodc]QHP@CwL@OLAHLmaQdKCtwsQ|KwnE{bQ`M\Kx|H\LHWH{xcIaGWaDR}MA{NtLc~bCVrePdIHjIgureNp?hqHSfs\QEK?{DCfroh{oRTMuEpPRpOHTGghAyN|OIVI|OX[EooSJ`{KQMMmBRSQlJgLEGYcRRycq_MdHxRD[fckSiirnNH?sKSiUqkJ?pBN__ErqPTJWGB?yCz_gMBWPTITM_gYsYSYArXMPFdL`KUsTRDPHoFWmSyT]]qGLTFtW`KE`lP@QwsD[ccpSeG@BDX?SpiomC?RUN`AD{ZS{TUDqdI_wtZTuGomMxGsuTuE?yF\Gs}b[MaFPtShREgltATMGPPF?is}bWmr@NhXGNKSsCPTpXW`ECaqgLaFo`C?RCna{zrxQyNQRHWjaxUM\BhMpETfUeF_oGTGTHUeO`tG{odHgwbrNSTRd`bwRadN`WhAFogqzMybR{O@ITodT@CLRlYDpfokBQMpCwZFk^ASHyE_mGXIIQLcvBpNhZw_J|Fc_VL\X[EC]aFS\\X`HWoBUOESbTLXBDUUudbEM[~C`SqLpUI\LtKVQpbqO|GC{f[pRELgwtJ_o\aDKxSWkCo~dEVt^yoLo~sQQ|SycPDCcuTT]Z[OTFCjS\UgkBt@SbRdRwXKH@CDPdU^")

rajiv441nx = rajiv441.networkx_graph()
loz390nx =loz390.networkx_graph()

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


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 check_all_isomorphisms(graph_list):
    n = len(graph_list)
    print("\n Isomorphism check of all pairs (a dot means the pair ARE isomorphic):")
    for i in range(n):
        label_i, G_i = graph_list[i]
        for j in range(i + 1, n):
            label_j, G_j = graph_list[j]
            if G_i.is_isomorphic(G_j):
#               print(".", end="")
                print(f"{label_i} IS isomorphic to {label_j}")
            else:
                print(f"{label_i} NOT isomorphic to {label_j}")
                
def non_isomorphic(graph_list):
    reps = []
    labels = []

    for label, G in graph_list:
        if not any(G.is_isomorphic(H) for _, H in reps):
            reps.append((label, G))
            labels.append(label.strip())   # remove extra spaces if you want    
    return labels

def isomorphic(graph_list):
    labels = []

    for i, (label, G) in enumerate(graph_list):
        if any(i != j and G.is_isomorphic(H) for j, (_, H) in enumerate(graph_list)):
            labels.append(label.strip())

    return labels

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("\n START \n")

#noniso = non_isomorphic(graphs)
#print(len(noniso), " non-isomorphic -> ",noniso)

#iso=isomorphic(graphs)
#print(len(iso), " isomorphic -> ",iso,"\n")


compare_graphs_list(graphs)


nonisographs = graphs



# Print properties for each graph in the list
print("\n Main properties of the graph\n")
for label, graph in nonisographs:
    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: {graph.dominating_set(value_only=True)} ")

print("\n Symmetry properties of the graph\n")
for label, graph in nonisographs:
    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("Degree histogram rajiv441  :", nx.degree_histogram(rajiv441nx) )  
print("Degree histogram loz390    :", nx.degree_histogram(loz390nx) )  
    
'''    
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()} \\\\ ")
''' 
    
# Check isomorphisms
# print(f"Are isomorphic G5 and G6? {G5.is_isomorphic(G6)}")

#check_all_isomorphisms(nonisographs)

print("\n")


# automorphism group structure
print(" Automorphism group structure")
print(' C_n is the cyclic group of order n;  x means direct product; : means semidirect product.\n')

Arajiv441  = rajiv441.automorphism_group()
Aloz390  = loz390.automorphism_group()
print('rajiv441  :', Arajiv441.structure_description(), ' |  center order:',Arajiv441.center().order())
print('loz390    :', Aloz390.structure_description(), ' |  center order:',Aloz390.center().order())

print("\n")



# 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 nonisographs:
    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 6")
for label, graph in nonisographs:
    print(f"{label} "," | ".join(str(count_k_cycles(graph, k)) for k in range(3, 7)))




'''
# from 0 versio Molodtsov?

for name, G in nonisographs:
    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 nonisographs:
    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 nonisographs:
    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")        
##
##