app.py

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:
        # Try interpreting as a dictionary (adjacency list)
        graph = eval(graph_input)
        if isinstance(graph, dict):
            return graph
    except:
        pass

    try:
        # Try interpreting as an edge list
        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]]
    
    # Use a circular layout for faster visualization
    pos = nx.circular_layout(nx.Graph(edges))
    
    # Draw the graph
    nx.draw(
        nx.Graph(edges),
        pos,
        with_labels=True,
        node_color='lightblue',
        edge_color='gray',
        node_size=500,
        font_size=10
    )
    
    # Identify the graph type
    graph_type = identify_graph_type(graph)
    
    # Add a label for the graph type below the visualization
    plt.title(f"Graph Type: {graph_type}", fontsize=12, color='darkblue')
    
    return plt.gcf()

def identify_graph_type(graph):
    """Identify the type of graph based on its structure."""
    num_nodes = len(graph)
    num_edges = sum(len(neighbors) for neighbors in graph.values()) // 2

    if num_nodes == 0:
        return "Empty Graph"
    elif num_nodes == 1:
        return "Single Vertex Graph"
    elif num_edges == 0:
        return f"Empty Graph with {num_nodes} vertices"
    elif num_edges == num_nodes - 1:
        return f"Path Graph P{num_nodes}"
    elif num_edges == num_nodes:
        return f"Cycle Graph C{num_nodes}"
    elif num_edges == num_nodes * (num_nodes - 1) // 2:
        return f"Complete Graph K{num_nodes}"
    elif num_edges == 2 * num_nodes - 2:
        return f"Wheel Graph W{num_nodes - 1}"
    else:
        return "Custom Graph (Unknown Type)"

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)

    # Round spectra to 2 decimal places
    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**:  \n"
        f"  - Nodes: **{len(graph1)}**  \n"
        f"  - Edges: **{sum(len(neighbors) for neighbors in graph1.values()) // 2}**\n"
        f"- **Graph 2**:  \n"
        f"  - Nodes: **{len(graph2)}**  \n"
        f"  - Edges: **{sum(len(neighbors) for neighbors in graph2.values()) // 2}**\n\n"
        
        f"**Observation:** Both graphs have the same number of nodes, but Graph 1 has {sum(len(neighbors) for neighbors in graph1.values()) // 2} edges, while Graph 2 has {sum(len(neighbors) for neighbors in graph2.values()) // 2} edges.\n\n"
        
        f"---\n\n"
        
        f"#### **Step 2: Adjacency Spectra**\n"
        f"- **What is an Adjacency Spectrum?**  \n"
        f"  The adjacency spectrum is the set of eigenvalues of the graph's adjacency matrix, which represents connections between vertices.\n\n"
        f"- **Adjacency Spectrum of Graph 1**:  \n"
        f"  ```{adj_spectrum1}```\n"
        f"- **Adjacency Spectrum of Graph 2**:  \n"
        f"  ```{adj_spectrum2}```\n\n"
        f"**Comparison:**  \n"
        f"- Are the adjacency spectra approximately equal? {'✅ Yes' if np.allclose(adj_spectrum1, adj_spectrum2) else '❌ No'}\n"
        f"- **Reason:** The eigenvalues {'match' if np.allclose(adj_spectrum1, adj_spectrum2) else 'differ significantly'} between the two graphs.\n\n"
        
        f"---\n\n"
        
        f"#### **Step 3: Laplacian Spectra**\n"
        f"- **What is a Laplacian Spectrum?**  \n"
        f"  The Laplacian spectrum is the set of eigenvalues of the graph's Laplacian matrix, which combines information about vertex degrees and adjacency.\n\n"
        f"- **Laplacian Spectrum of Graph 1**:  \n"
        f"  ```{lap_spectrum1}```\n"
        f"- **Laplacian Spectrum of Graph 2**:  \n"
        f"  ```{lap_spectrum2}```\n\n"
        f"**Comparison:**  \n"
        f"- Are the Laplacian spectra approximately equal? {'✅ Yes' if np.allclose(lap_spectrum1, lap_spectrum2) else '❌ No'}\n"
        f"- **Reason:** The eigenvalues {'match' if np.allclose(lap_spectrum1, lap_spectrum2) else 'differ significantly'} between the two graphs.\n\n"
        
        f"---\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'} because their adjacency and Laplacian spectra {'match' if np.allclose(adj_spectrum1, adj_spectrum2) and np.allclose(lap_spectrum1, lap_spectrum2) else 'do not match'}.\n\n"
        
        f"---\n\n"
        
        f"### **Explanation**\n"
        f"- **Adjacency Spectrum:** Represents the eigenvalues of the adjacency matrix. If two graphs are isomorphic, their adjacency spectra must match.\n"
        f"- **Laplacian Spectrum:** Represents the eigenvalues of the Laplacian matrix. Similar to adjacency spectra, matching Laplacian spectra is a strong indicator of isomorphism.\n"
        f"- **Result Interpretation:** Since {'both' if np.allclose(adj_spectrum1, adj_spectrum2) and np.allclose(lap_spectrum1, lap_spectrum2) else 'neither'} the adjacency nor the Laplacian spectra match, the graphs are {'structurally identical' if np.allclose(adj_spectrum1, adj_spectrum2) and np.allclose(lap_spectrum1, lap_spectrum2) else 'structurally different'} and cannot be 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 = sorted(np.linalg.eigvals(adj_matrix).real)
    lap_spectrum = sorted(np.linalg.eigvals(laplacian_matrix).real)
    
    algebraic_connectivity = lap_spectrum[1]  # 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), mapping)
    elif question_type == "Matrix Representations and Spectra":
        result = demonstrate_matrix_representations(graph1)
    else:
        result = "Unsupported question type. Please select a valid operation."

    # 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("Select a question type and analyze two graphs!")

    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):
        """Show/hide the mapping input based on the selected 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(process_inputs, inputs=[graph1_input, graph2_input, question_type, mapping_input], outputs=[graph1_output, graph2_output, result_output])

# Launch the app
demo.launch()