app.py

import subprocess
import sys

# Function to install missing libraries
def install_package(package):
    try:
        __import__(package)
    except ImportError:
        subprocess.check_call([sys.executable, "-m", "pip", "install", package])

# Manually install all required packages
install_package("gradio")
install_package("numpy")
install_package("matplotlib")
install_package("networkx")
install_package("scipy")
install_package("astor")  # In case 'ast' needs explicit installation

# Now import all libraries after ensuring installation
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

# Your existing code continues from here...

# 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 with share=True to make it publicly accessible
demo.launch(share=True)