Untitled

import networkx as nx
import matplotlib.pyplot as plt

def create_bipartite_graph(n: int):
    G = nx.Graph()
    layer1 = set(range(n))
    layer2 = set(range(n, 2 * n))
    G.add_nodes_from(layer1, bipartite=0)
    G.add_nodes_from(layer2, bipartite=1)
    G.add_edges_from(nx.complete_bipartite_graph(layer1, layer2).edges())
    return G

def create_isomorphic_circular_graph(n: int):
    if n < 3:
        raise ValueError("this algorithm is for n >= 3.")
    
    G = nx.Graph()
    num_vertices = 2 * n
    G.add_nodes_from(range(num_vertices))

    for i in range(num_vertices):
        if n % 2 == 0:
            num_pairs = n // 2
            for j in range(num_pairs):
                skip = 2 * j + 1
                G.add_edge(i, (i + n - skip) % num_vertices)
                G.add_edge(i, (i + n + skip) % num_vertices)
        
        else:
            G.add_edge(i, (i + n) % num_vertices)
            num_pairs = (n - 1) // 2
            for j in range(num_pairs):
                skip = 2 * (j + 1)
                G.add_edge(i, (i + n - skip) % num_vertices)
                G.add_edge(i, (i + n + skip) % num_vertices)
            
    return G

def run_comparison(n: int):
    G_bipartite = create_bipartite_graph(n)
    G_circular = create_isomorphic_circular_graph(n)

    are_isomorphic = nx.is_isomorphic(G_bipartite, G_circular)
    print(f"\nare the two graphs isomorphic? {are_isomorphic}\n")
    
    plt.figure(figsize=(14, 7))
    
    plt.subplot(1, 2, 1)
    layer1_nodes = {node for node, data in G_bipartite.nodes(data=True) if data["bipartite"] == 0}
    pos_bip = nx.bipartite_layout(G_bipartite, nodes=layer1_nodes)
    nx.draw(G_bipartite, pos_bip, with_labels=True, node_color='skyblue', node_size=800)

    plt.subplot(1, 2, 2)
    pos_circ = nx.circular_layout(G_circular)
    node_colors = ['lightcoral' if node % 2 == 0 else 'gold' for node in G_circular.nodes()]
    nx.draw(G_circular, pos_circ, with_labels=True, node_color=node_colors, node_size=800)
    
    plt.show()

if __name__ == "__main__":
    run_comparison(n=4)
    run_comparison(n=7)