# Optimal (5,2)=24 graph
# J.-C. Bermond, C. Delorme and G. Fahri. Large graphs with given degree and diameter III. 
#   Proc. Coll. Cambridge. 1981; Ann. Discrete Math. 13 (1982), 23-32. doi:10.1016/S0304-0208(08)73544-8
# 
# K3xX8   https://sagecell.sagemath.org/?q=yxlege

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

# K3 vertices
K3_nodes = [1, 2, 3]

# X8 vertices
X8_nodes = ['a', 'b', 'c', 'd', 'fa', 'fb', 'fc', 'fd']

# f mapping
f = {
    'a': 'fa', 'b': 'fb', 'c': 'fc', 'd': 'fd',
    'fa': 'a', 'fb': 'b', 'fc': 'c', 'fd': 'd'
}

# Edges of X8
X8_edges = [
    ('a', 'd'), ('a', 'fc'), ('a', 'fd'),
    ('b', 'd'), ('b', 'fa'), ('b', 'fd'),
    ('c', 'd'), ('c', 'fb'), ('c', 'fd'),
    ('fa', 'fc'), ('fa', 'fb'), ('fb', 'fc')
]

# Create X8 and K3
X8 = nx.Graph()
X8.add_nodes_from(X8_nodes)
X8.add_edges_from(X8_edges)

K3 = nx.complete_graph(K3_nodes)

# Initialize the product graph
G = nx.Graph()

# Base layout (rotated)
base_layout = nx.spring_layout(X8, seed=int(35))
for node in base_layout:
    x, y = base_layout[node]
    base_layout[node] = (-x, -y)

# Prepare layout and product vertices
positions = {}
angle_step = 2 * np.pi / len(K3_nodes)
radius = 2.5
product_vertices = []

for i, k_node in enumerate(K3_nodes):
    angle = i * angle_step
    dx, dy = radius * np.cos(angle), radius * np.sin(angle)
    for x8_node in X8_nodes:
        x, y = base_layout[x8_node]
        rotated_x = x * np.cos(angle) - y * np.sin(angle) + dx
        rotated_y = x * np.sin(angle) + y * np.cos(angle) + dy
        product_node = (k_node, x8_node)
        G.add_node(product_node)
        positions[product_node] = (rotated_x, rotated_y)
        product_vertices.append(product_node)

# Add edges
for (x1, x1p) in product_vertices:
    for (x2, x2p) in product_vertices:
        if (x1, x1p) == (x2, x2p):
            continue
        if x1 == x2 and X8.has_edge(x1p, x2p):
            G.add_edge((x1, x1p), (x2, x2p))
        elif K3.has_edge(x1, x2) and f.get(x1p) == x2p:
            G.add_edge((x1, x1p), (x2, x2p))

# Draw nodes
plt.figure(figsize=(8, 8))
nx.draw_networkx_nodes(G, pos=positions, node_size=150, node_color='black')

# Draw edges with appropriate curvature
for u, v in G.edges():
    x1, x1p = u
    x2, x2p = v
    edge_set = {x1, x2}
    is_cross_copy = x1 != x2 and f.get(x1p) == x2p

    if x1 == x2:  # Internal X8 edges
        nx.draw_networkx_edges(G, pos=positions, edgelist=[(u, v)], width=2, edge_color='black')
    elif is_cross_copy:
        if edge_set == {1, 2} or edge_set == {2, 3}:
            curvature = 0.5 # outward
        elif edge_set == {1, 3}:
            curvature = -0.5  # inward
        else:
            curvature = 0.0  # default straight
        nx.draw_networkx_edges(
            G,
            pos=positions,
            edgelist=[(u, v)],
            width=2,
            edge_color='black',
            connectionstyle=f'arc3,rad={curvature}',
            arrows=True
        )
        
plt.title("Graph K3 × X8 with 3 symmetric copies and adjusted curvature")
plt.axis('off')
plt.tight_layout()
plt.savefig("K3_X8_visual.png", dpi=300)
plt.show()

# Save edge data
nx.write_edgelist(G, "K3_X8_edges.txt")
nx.write_adjlist(G, "K3_X8_adjlist.txt")
nx.write_graph6(G, "K3_X8_graph6.txt")

# Print graph properties
print(G)
print('is_connected(G) ? ', nx.is_connected(G))
print('Degree Distribution:', nx.degree_histogram(G))
dmax = len(nx.degree_histogram(G)) - 1
print('avg. deg.:', sum(dict(G.degree).values()) / len(G.nodes), 'max. deg.:', dmax)
diameter = nx.diameter(G, usebounds=True)
print("Diameter:", diameter)
avgdist = "{:.6f}".format(nx.average_shortest_path_length(G))
print("avg. dist.:", avgdist)

# Save relabeled version too
GZ = nx.convert_node_labels_to_integers(G)
nx.write_edgelist(GZ, "K3*X8_Zedges.txt")
nx.write_adjlist(GZ, "K3*X8_Zadjlist.txt")
# nx.write_graph6(GZ, "K3*X8_Zg6.txt")

##