File size: 4,521 Bytes
4db4eb5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
import gradio as gr
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
# Helper Functions
def parse_graph_input(graph_input):
"""Parse user input to create an adjacency list."""
try:
graph = eval(graph_input)
if isinstance(graph, dict):
return graph
except:
pass
try:
edges = eval(graph_input)
if not isinstance(edges, list):
raise ValueError("Invalid graph input. Please use an adjacency list or edge list.")
graph = {}
for u, v in edges:
graph.setdefault(u, []).append(v)
graph.setdefault(v, []).append(u)
return graph
except:
raise ValueError("Invalid graph input. Please use a valid adjacency list or edge list.")
def visualize_graph(graph):
"""Generate a visualization of the graph using a circular layout."""
plt.figure()
nodes = list(graph.keys())
edges = [(u, v) for u in graph for v in graph[u]]
pos = nx.circular_layout(nx.Graph(edges))
nx.draw(
nx.Graph(edges),
pos,
with_labels=True,
node_color='lightblue',
edge_color='gray',
node_size=500,
font_size=10
)
return plt.gcf()
def spectral_isomorphism_test(graph1, graph2):
"""Perform spectral isomorphism test with step-by-step explanation."""
adj_spectrum1 = sorted(np.linalg.eigvals(nx.adjacency_matrix(nx.Graph(graph1)).todense()).real)
adj_spectrum2 = sorted(np.linalg.eigvals(nx.adjacency_matrix(nx.Graph(graph2)).todense()).real)
lap_spectrum1 = sorted(np.linalg.eigvals(nx.laplacian_matrix(nx.Graph(graph1)).todense()).real)
lap_spectrum2 = sorted(np.linalg.eigvals(nx.laplacian_matrix(nx.Graph(graph2)).todense()).real)
adj_spectrum1 = [round(float(x), 2) for x in adj_spectrum1]
adj_spectrum2 = [round(float(x), 2) for x in adj_spectrum2]
lap_spectrum1 = [round(float(x), 2) for x in lap_spectrum1]
lap_spectrum2 = [round(float(x), 2) for x in lap_spectrum2]
output = (
f"### **Spectral Isomorphism Test Results**\n\n"
f"#### **Step 1: Node and Edge Counts**\n"
f"- **Graph 1**: Nodes: {len(graph1)}, Edges: {sum(len(neighbors) for neighbors in graph1.values()) // 2}\n"
f"- **Graph 2**: Nodes: {len(graph2)}, Edges: {sum(len(neighbors) for neighbors in graph2.values()) // 2}\n\n"
f"#### **Step 2: Adjacency Spectra**\n"
f"- Graph 1: {adj_spectrum1}\n"
f"- Graph 2: {adj_spectrum2}\n"
f"- Are the adjacency spectra approximately equal? {'✅ Yes' if np.allclose(adj_spectrum1, adj_spectrum2) else '❌ No'}\n\n"
f"#### **Step 3: Laplacian Spectra**\n"
f"- Graph 1: {lap_spectrum1}\n"
f"- Graph 2: {lap_spectrum2}\n"
f"- Are the Laplacian spectra approximately equal? {'✅ Yes' if np.allclose(lap_spectrum1, lap_spectrum2) else '❌ No'}\n\n"
f"#### **Final Result**\n"
f"- Outcome: {'✅ PASS' if np.allclose(adj_spectrum1, adj_spectrum2) and np.allclose(lap_spectrum1, lap_spectrum2) else '❌ FAIL'}\n"
f"- Conclusion: The graphs are {'isomorphic' if np.allclose(adj_spectrum1, adj_spectrum2) and np.allclose(lap_spectrum1, lap_spectrum2) else 'NOT isomorphic'}.\n"
)
return output
def process_inputs(graph1_input, graph2_input):
"""Process user inputs and perform the spectral isomorphism test."""
graph1 = parse_graph_input(graph1_input)
graph2 = parse_graph_input(graph2_input)
result = spectral_isomorphism_test(graph1, graph2)
graph1_plot = visualize_graph(graph1)
graph2_plot = visualize_graph(graph2)
return graph1_plot, graph2_plot, result
# Gradio Interface
with gr.Blocks(title="Graph Theory Project") as demo:
gr.Markdown("# Graph Theory Project")
gr.Markdown("Analyze two graphs using spectral isomorphism tests!")
with gr.Row():
graph1_input = gr.Textbox(label="Graph 1 Input (e.g., '{0: [1], 1: [0, 2], 2: [1]}' or edge list)")
graph2_input = gr.Textbox(label="Graph 2 Input (e.g., '{0: [1], 1: [0, 2], 2: [1]}' or edge list)")
with gr.Row():
graph1_output = gr.Plot(label="Graph 1 Visualization")
graph2_output = gr.Plot(label="Graph 2 Visualization")
result_output = gr.Textbox(label="Results", lines=20)
submit_button = gr.Button("Run")
submit_button.click(process_inputs, inputs=[graph1_input, graph2_input], outputs=[graph1_output, graph2_output, result_output])
# Launch the app
demo.launch() |