| import gradio as gr |
| import numpy as np |
| import matplotlib.pyplot as plt |
| import networkx as nx |
|
|
| |
| 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 |
|
|
| |
| 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]) |
|
|
| |
| demo.launch() |
