# SageMathCell online  https://sagecell.sagemath.org/?q=mbivsc
#
#
# 

import networkx as nx


dhar201=Graph(r":~?BH_O??KE?kB_cI?cI`gH_[??GA?WC?gE@?H@_L@sA_SA@{AASD_OPAcA@[J@{JbOAAsA?wO_GF`oZ`?JAkEA[DASHB[CAG_CKI@gY`oVB{KA_bbCC@GUBkBA?]_G`_wLBWe`oTaWVDCGAOdD[KBsEAG[CSYCWk_gfDSH@OXCC?Bgn_WUC_q__OA_^Ds@`_ZCgn_?FA_TCwk`oRBwjE{QD?pE{A?WSB?`E[GAGcDOsFKHBO`Eg{`gaDgw_oXBgm_WWComEcIAoVBorF[DA?_E@?_GI@WuEwwFGyF_|Fo~G@@GSZCGcDgu_oLAg_DWu_OXCorGCMAO]DOu`GSD?nEsPAweDopEsPCwoFGz`?\E?uHKBBG_CwtEpC`_WCOkEpE__UCgsEpD`GRCwmGPH_GzH{VBGZCWjG@GICE@OTC?eDO}H`O_OWCgqFxK__FAObE?~HpO`o_D_wG`O`_PD?qF`O_?DBO\Dg|HhO_?KCojFhS`gXC_nFPDI@R`?WBopExEICUBwjEg}GxO_?OCOsFHJI@P_GhDOjD_lDonE?pEOrE_tIkHBWaDG|GXC`_TBw`DH?I`]`WLAW]DGkGHKI{?@OQC_hHPLISE?wdDGyHX[KCMAG\DHAHpY`?RCGeD_~GHDc?hFxGIH^awXDG}IXWJXb__WCwhF@EGxUKkDA_UCohFHHHxX`?OCWhF`TLC@HSGA_ZE_yHhNJ@e_gTEgwH@gL[CAWaEGuG@PKCQAwfDwvH`SLK\EW{GhZLkB?wIAG^DhHIxdKsMBOeEO}GPUKPcLsEBggD_|HpQK[?BG]CGoGPFIXXJpo`gWCWmFHCGp[Kxq`WKAo_DP@HXTJH^`GOC_jFxYKHt_G~Kc?BW_EOvHHZK@qM{TBosFh[KhmM{G@ORCokFW~Gh]MHv`gQA_\Eh?HXSIp`L`v_WaDooFpKJPgMpv_gJAGpGHCI`WM`v_wKBOcDowHXXKXlM{I@obDw|GxNJxjM{CBGgDOxH@IIXVKptM{HBwyGpMIhhM@v_oLAofD?jF`LIHaMXva?VCglGPQKxnM{@DkE@WZBw`E@@GhUKxjNcK@weE?yG`IJXdLxx`_RBg]E_}H@QLHrNkQC?mFW{KpsOSGCwlG@IJH^MPw_?UAwgDg~G`UL@lNyCa_VBOaDO~Gx[La@PKF@G]EOxHhNI`gLyB`oXCgpFhHIXTKHlNID_gIB?`D?jGpJJX]Lp}`gUD_vJ@YKHdM@za?aConF@MIx_Mp~OqG_GsIqCOiFPAHPYKPiMPyO_gZBomFpIHpPKHpOICagVBgqFPLIx^M`{OcB?wRDw|HXWJHfMiBOaOQSEAO`CWhE_wHHYJpnOACOsPCwoFH`LQ?OqHQSHAGdD`?GxZKPuN`|OcGBO_EWxG`KIPdLX}OaV__eEgvIhrOQCPqR_wJBGaDX@HxRLHqNY@OaE`oSB?cE?{GpGI`_L`wOc?AGVCWtFPKIHbK`tNQKQKI@_OCwiEHDJ`cKpoNQCR[@A`iLXkLhmLxoMHqMXsMhuPKC@OZBggD`XL@iNIGQ{B@?TCWpFxLJXhLPsNAS_?RCgiF`EHpNKhiNaMQ[H@WQColGHGJ`bLPwNqDRI__gcE_vGxVKXcKxiNQYRcCBO[DWyFXHKxkMpwO{EBO]Dx?G`TIxeLPzPa\SIc`_jGPKIpWK@iOIJQi^`?XBwqF@JIHRLP|QCFAwWC?tFhDGpIJPaLP~OyIQsMAo`COmFPQJ`]LQBPyZS{LA?gEW}HHSJxaLQAPiWS[@B_\Bo^C?aCWcCgeCwgJ@j__TC_rGPCHxaMI?PyPSCHAg[E?vHXQKplOIGPQb`ORA_[EPCIpYKXkOQEPYSTSKAO[EW|GxPL@qNH{RifTc@Aw[CGpFHMIp]MXzQAWSCLAG[E_~HPTK@jLyBPqURIn__DBO[DWyHHfMpwOyd_?[Dp?GhGIxhLq?OiVTIm_gXB_kF`KIX[JxnNyNQQaSaq_oWB_lFpEHxtNIZRa^UCF@?UB_nGPGJX`K`sNQFPiRSsJ@oOB_tGHLJHdMH|PITSIlc_pFW}HXdMP~OIKQqXSqr_WJCgrHPOIX]K`kPAqVC?@WWBgnGp\Ly@RAiTan_?F@oYBwpEpGJP^MIBPAYRyp_oOEOuFXFHPWLHlNqNQYtVK@@wOAGQAWSAgUB?XBOZVCA@OmH@TJ@YKPnNaHSYoVkAC_pFpJIXdMP~PaXSqr_gFAWbEWuIpeMpxPIXTIkUyy`g^DOtFXAHhbLpxOaISyqVsEA?qEWuGxWLHlNqNQYUUkBBG`Ch@I@kNQGQqqVQ{VzA`_XCWlEwzHpaLaBPiVSIjVKBBOgDGvGhNKHnNiJRI^SylUkHB?^EWyHpTLHoMyJQQeTi|V{B@WSChII@]KaGQqcVQ~WJAWcLBwiF@AHhbLpxOaISafVI}W^")
abas200=Graph(r":~?BG_C?_C?_C?_?@?k??S??c??[?_?E_?@_C?@[?@s@`GP`wP_GP_WP`?Pa?P_gPAOU_oPA[MAGT`?P__PA{AAGQ`OP_OKAGZ`WPBs@BcHAg``?XCKNB_`_o_CKOBo``WYBg`_ODBo`COe`oQCGb_WZCGd_w^CGf_WWCGa`_RCK@CKIAo`Dk@BWe`oXDGo`GZDwoa?QCwo___C_o_Go_g\COoEGs__RCWeECA?WVDgoE[GBOkDoo`wVDOoEKJAoWDWo`OKB_oFKEAgcCgoF[@@gT_OQDO{FsCBwnEw}_gFBGbF?}_oZDG}_gLB_qFp@a?VCWsFW}F{NA?\C_kFG}GCIAgeDw}`WUC?jEW}`_RCguFpA`oWD?yF_}`GSDgpFpF`?HBofEg}HK@`_RCgvHXK_w[E_{G@K`wUBOnEo~HcHBOiF@@GhK_oZDpCHcOBweDHIHcD@oZC_rGpFH`LIKJAgbDgyH`M_oIBojFXAH`O_OQDG|GXKH{CBGgEHHHcGC?aFHBH`Qa?WDguH@KHkBAwfD_qH@KI{@BhK_WLAO\ColFXMIKLAW]COkEXM`gUBofEGyIKLBW[HhX`gNA_nEhOJcLA?SCWtI@]`gZDPUIx\`OLB?XBO^C_sISLAOdFHSIh^_oLAwjEovF@N`?LA_gFhYK[H@g_DG{IXd_WSCwsGXCHPJIp__OSC_qFxLKKEA_cFH@GxXKSMA_jEPHHpWKkF@?NA?SAgdEXVKCKA_eH@NKcD@GSCWtGhOJxj__IAWSDGiFXEJ@\LSA?_SBgkFPAIXSIhfLkJA_aEovF?{G@PKsEB_kEhBHPJIH``OVCOtFPFH@UKXm`_VBgfEhEJ@aL{JAOcEhEIxdMKF@wOBWaEhAHpNKKCAodEh@IPcMCD@?YCWtG`OJhlMkBAggDGiEh?JHfLPs_OWBG^C?jEg~JH_`oRDgtFxRI`TJPeM{BBomEpEIPaLHv__WDowHHZKhnMsOAWmEPBIhXM@t`GXDozHXNKXlNKD@WVD?hDonFHAHh_NcKAogDGiDosGxMI@eM`}`o^DoyFh?Ix^L@tNkNBwmF`@HPYKxkNCFBg_DovFxUJxkMXzN{IAgeDpSKPiLXyNcIAOgDonEXGJ@`O[AAgmDwpIH\Ls@Gp}_OQCwvGxYKXcLPuOyGa?UBGjF`DIpaMHvNyG`GVC_|HPMJhlNQ?PCDC?lFPAJ@[LHwNyAPAHPSBBw_CWdEXHHx[Lp}PCJ@_WBw_D_pGpOIp`OaG_HCK@eKyG_oZD@DI`dL@zOqG`?[E_uG@TJpkNHzNiGP[JBG\DOrFxZKXjMQ?PAH`w]DGwHXQJxpOIDPCMAo\COzGHLJ`hMYBPAO__YDWxFxGIHVJ`hMYGQ[GBWlHPZK`rMh}`_YCg{GPXJX\L@vOyO`G^COxG`ZJpaLPzOAL_gVCgzG@RJPZKH~OiRQqV`_]CWcEPGIXSJPZK@|PSMBOiEwyGXZMHyOqJ`OTDGkExZKhhL`qOIKRCNAWgEPCIHZK`jMxxPqUa?_Dw|GHJJXeKxuOyT_oUCosGPEJPZJxmOYZ_WRB_jEHFJX^LhwNaORsFBoiFHIIPdMhxOySRSFAwcEHHIhcLHpMaFPiZ_wYDgwHXLKPbM@}Ri^_wG@GNAObDWyGpXKpqNaNQ{F@?HAWUCpGI@fL@qOQDQQa_wXD_nFhCJ@^M@sOqRRA`_w_DGqGhPJP]LhnNQOQqb_GVGSGAwcEHJHp[KhiMyEPqZTCNB?eDPBJ@lNYFQYWSIg`GWCgqGPPI`bL`pMaOSAg`WUBwjEXBI`\LHxNyTRyg`o_DwsF@?IxaK`lMP|QacTCDAWTCw{Fg~IP]Lp|NqgTIl`O\CWuF_|GxVKIAPY\SYgTSMB_uEw{FhHI@_NaHQqeSygTcBBGaFHEIXcL@uNQ@Rag_HDKpfSig_OYD?zHPNJxnMQCPQLRQg__]Dg|G@UJH]LXwOYQSQgUKKAOkE_yGHLJpjMiDQI]TAr`O\CgpGXCGhIHheMpwNiDPyk`W[FXGIPaLqEOyNQI[SYp__ZD`FIP_NyNQAZSQmTysUkAAWlE_xHHUKINRI^SA`T[MBoeD_~GHNJhiMaAPyUTYv_oWBGYCwrG@MKxhMX{PyUTQr`_TCOqEXTJxlMyAPyQSyhVKBAocEwwGPVJ@]LXtOaJPyV_gOBwiEpJI`cLxqOYNRqqVkKBolFXBG`DIxfL`mMp{PIZUSCB_fEXAHxeNQDPaLPqSRi`USB?_TDWsHh`OAEOyIQqiUQy_oQCOpFx?J@_NqXRQ^SAbUSEBgnEOyHHQJhiNACQYpUQvWKJBGYCoqGxUJ`hMX|QIVSqqVsI@WZCx@HHPJH^LhvPY[UQxWSA@o[CgwGpGHp]LXtNyWUQw_gNB?bExIIhaL@sOYTRqqVbE")


dhar201nx = dhar201.networkx_graph()
abas200nx = abas200.networkx_graph()

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


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 graphs:
    print(f"{label} | Ord.: {graph.order()} / Size: {graph.size()} / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} / 16-reg.? {graph.is_regular(k=16)} /  Girth: {graph.girth()} ") # /  Alg.conn. {algebraic_connectivity(graph).n(digits=6)} ")# /   Domin. number: {graph.dominating_set(value_only=True)} ")

print("\n")


print("Degree histogram dhar201:  " , nx.degree_histogram(dhar201nx)  )  
print("Degree histogram abas200:  " , nx.degree_histogram(abas200nx)  )  



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



# automorphism group structure
print("\n Automorphism group structure: x means direct product; : means semidirect product.") 
Adhar201  = dhar201.automorphism_group()
print('dhar201  :', Adhar201.structure_description(), ' |  center order:',Adhar201.center().order())           
Aabas200  = abas200.automorphism_group()
print('abas200  :', Aabas200.structure_description(), ' |  center order:',Aabas200.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()} & {graph.is_edge_transitive()} \\\\ ")
'''
    
# Check isomorphisms
# print(f"Are isomorphic G5 and G6? {G5.is_isomorphic(G6)}")

# check_all_isomorphisms(nonisographs)

print("\n")

'''

print("\n")
print("\nChecking throught the spectrum that P13dp and Dah188 are NON-isomorphic\n ")
for label, graph in nonisographs:
    spec = [ev.n(digits=4) for ev in graph.spectrum()[:10]]
    print(f"{label} spectrum (first 10): {spec}")
'''


# Counting k-cycles for each graph
print("\nNumber of k-cycles for k=3 up to 4")
for label, graph in nonisographs:
    print(f"{label} ","  |  ".join(str(count_k_cycles(graph, k)) for k in range(3, 5)))

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


        
       
print("\n DONE \n")        
##
##