app.py

import gradio as gr
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from scipy.sparse.linalg import eigsh
from scipy.sparse import csgraph
import ast

# Helper Functions
def parse_graph_input(graph_input):
    """Parse user input to create an adjacency list."""
    try:
        # Try interpreting as a dictionary (adjacency list)
        graph = ast.literal_eval(graph_input)
        if isinstance(graph, dict):
            return graph
    except:
        pass

    try:
        # Try interpreting as an edge list
        edges = ast.literal_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."""
    if len(graph) > 50:  # Skip visualization for large graphs
        return None
    
    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 calculate_spectrum(matrix, k=6, which='LM'):
    """Calculate the largest k eigenvalues of a sparse matrix."""
    eigenvalues, _ = eigsh(matrix, k=k, which=which)
    return sorted(eigenvalues.real)

def spectral_isomorphism_test(graph1, graph2):
    """Perform spectral isomorphism test with step-by-step explanation."""
    adj_matrix1 = nx.adjacency_matrix(nx.Graph(graph1))
    adj_matrix2 = nx.adjacency_matrix(nx.Graph(graph2))
    lap_matrix1 = nx.laplacian_matrix(nx.Graph(graph1))
    lap_matrix2 = nx.laplacian_matrix(nx.Graph(graph2))

    adj_spectrum1 = calculate_spectrum(adj_matrix1, k=min(6, len(graph1) - 1))
    adj_spectrum2 = calculate_spectrum(adj_matrix2, k=min(6, len(graph2) - 1))
    lap_spectrum1 = calculate_spectrum(lap_matrix1, k=min(6, len(graph1) - 1), which='SM')
    lap_spectrum2 = calculate_spectrum(lap_matrix2, k=min(6, len(graph2) - 1), which='SM')

    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 check_graph_homomorphism(graph1, graph2, mapping):
    """Check if a mapping defines a graph homomorphism."""
    result = []
    for u, v in graph1.edges():
        mapped_u, mapped_v = mapping.get(u), mapping.get(v)
        if mapped_u is None or mapped_v is None:
            result.append(f"Mapping is incomplete. Missing vertex {u} or {v}.")
            continue
        if (mapped_u, mapped_v) not in graph2.edges() and (mapped_v, mapped_u) not in graph2.edges():
            result.append(f"Edge ({u}, {v}) in Graph 1 maps to ({mapped_u}, {mapped_v}) in Graph 2. Edge does NOT exist in Graph 2.")
        else:
            result.append(f"Edge ({u}, {v}) in Graph 1 maps to ({mapped_u}, {mapped_v}) in Graph 2. Edge exists in Graph 2.")
    
    is_homomorphism = all(("exists" in line) for line in result)
    final_result = (
        f"**Final Result:** {'✅ Mapping IS a Graph Homomorphism.' if is_homomorphism else '❌ Mapping IS NOT a Graph Homomorphism.'}\n"
        f"Explanation: A graph homomorphism must preserve all adjacencies. If any edge fails to map correctly, the mapping is invalid."
    )
    return "\n".join(result) + "\n\n" + final_result

def demonstrate_matrix_representations(graph):
    """Display adjacency matrix, Laplacian matrix, and spectra."""
    adj_matrix = nx.adjacency_matrix(nx.Graph(graph)).todense()
    laplacian_matrix = nx.laplacian_matrix(nx.Graph(graph)).todense()
    degree_matrix = np.diag([len(graph[v]) for v in graph])
    
    adj_spectrum = calculate_spectrum(nx.adjacency_matrix(nx.Graph(graph)), k=min(6, len(graph) - 1))
    lap_spectrum = calculate_spectrum(nx.laplacian_matrix(nx.Graph(graph)), k=min(6, len(graph) - 1), which='SM')
    
    algebraic_connectivity = lap_spectrum[1] if len(lap_spectrum) > 1 else 0  # Second smallest eigenvalue
    
    output = (
        f"### **Matrix Representations and Spectra**\n\n"
        
        f"#### **Adjacency Matrix**\n"
        f"```\n{adj_matrix}\n```\n\n"
        
        f"#### **Laplacian Matrix**\n"
        f"```\n{laplacian_matrix}\n```\n\n"
        
        f"#### **Degree Matrix**\n"
        f"```\n{degree_matrix}\n```\n\n"
        
        f"#### **Adjacency Spectrum**\n"
        f"```{[round(x, 2) for x in adj_spectrum]}```\n\n"
        
        f"#### **Laplacian Spectrum**\n"
        f"```{[round(x, 2) for x in lap_spectrum]}```\n\n"
        
        f"#### **Algebraic Connectivity**\n"
        f"The second smallest eigenvalue (Algebraic Connectivity): {round(algebraic_connectivity, 2)}\n\n"
        
        f"**Explanation:** These matrices and spectra provide insights into the graph's structure. Algebraic connectivity measures robustness."
    )
    return output

def process_inputs(graph1_input, graph2_input, question_type, mapping=None):
    """Process user inputs and perform the selected operation."""
    # Parse graphs
    graph1 = parse_graph_input(graph1_input)
    graph2 = parse_graph_input(graph2_input)

    # Determine operation based on question type
    if question_type == "Spectral Isomorphism Test":
        result = spectral_isomorphism_test(graph1, graph2)
    elif question_type == "Graph Homomorphism Check":
        if mapping is None:
            result = "Error: Mapping is required for Graph Homomorphism Check."
        else:
            result = check_graph_homomorphism(nx.Graph(graph1), nx.Graph(graph2), eval(mapping))
    elif question_type == "Matrix Representations and Spectra":
        result = demonstrate_matrix_representations(graph1)
    else:
        result = "Unsupported question type."

    # Visualize graphs
    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 graphs using algebraic methods!")

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

    question_type = gr.Dropdown(
        choices=["Spectral Isomorphism Test", "Graph Homomorphism Check", "Matrix Representations and Spectra"],
        label="Select Question Type"
    )

    mapping_input = gr.Textbox(label="Mapping (for Graph Homomorphism Check, e.g., '{0: 0, 1: 1, 2: 2}')", visible=False)

    def toggle_mapping_visibility(question_type):
        return {"visible": question_type == "Graph Homomorphism Check"}

    question_type.change(toggle_mapping_visibility, inputs=question_type, outputs=mapping_input)

    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(
        lambda g1, g2, qt, m: process_inputs(g1, g2, qt, m),
        inputs=[graph1_input, graph2_input, question_type, mapping_input],
        outputs=[graph1_output, graph2_output, result_output]
    )

# Launch the app
demo.launch()