🔷 WL-Viz: Weisfeiler-Lehman Graph Visualization

A Python-based web application for creating graphs, visualizing the Weisfeiler-Lehman (WL) algorithm, and testing for graph isomorphisms.

🚀 Try It Online

Launch the app on GitHub Pages

No installation required! The GitHub Pages version is a fully client-side implementation that runs entirely in your browser.

Features

• Interactive Graph Editor: Create and edit graphs with a visual interface
• Node Labels: Support for custom node labels
• Weisfeiler-Lehman Algorithm: Run the WL color refinement algorithm on graphs
• Isomorphism Testing: Test if two graphs are potentially isomorphic
• Node Color Comparison: Check if two nodes always have the same color across all WL iterations
• Visual Animations: Step through WL iterations with animated visualizations
• Color-coded Results: Clear visualization of color classes at each iteration

Installation

1. Clone the repository:

git clone https://github.com/Martin36/wl-viz.git
cd wl-viz

2. Install dependencies:

pip install -r requirements.txt

Usage

1. Start the Flask server:

python app.py

2. Open your browser and navigate to:

http://localhost:5000

Configuration

You can configure the server using environment variables:

# Enable debug mode (default: False)
export FLASK_DEBUG=true

# Set host (default: 127.0.0.1)
export FLASK_HOST=0.0.0.0

# Set port (default: 5000)
export FLASK_PORT=8080

python app.py

3. Use the interface to:
   • Create Graphs: Click "Add Node" or click on the canvas to add nodes
   • Connect Nodes: Click one node, then click another to create an edge
   • Label Nodes: Double-click a node to edit its label
   • Delete Nodes: Right-click a node to delete it
   • Run WL Algorithm: Click "Run WL Algorithm" to see color refinement
   • Compare Nodes: Enter two node IDs to check if they always have the same color
   • Test Isomorphism: Save two graphs and test if they might be isomorphic

How It Works

The Weisfeiler-Lehman algorithm is a graph isomorphism test that works by iteratively refining node colors based on their neighborhood structure:

1. Initialization: Each node starts with a color based on its label
2. Refinement: In each iteration, nodes get new colors based on:
   • Their current color
   • The sorted multiset of their neighbors' colors
3. Convergence: The algorithm stops when colors stabilize or max iterations reached

Graph Isomorphism Testing

The WL test can prove that two graphs are not isomorphic if their color refinement sequences differ. However, identical sequences only suggest potential isomorphism - they don't prove it (some non-isomorphic graphs can have identical WL sequences).

API Endpoints

POST /api/wl/run

Run WL algorithm on a single graph.

Request:

{
  "graph": {
    "nodes": [{"id": 0, "label": "A"}, ...],
    "edges": [{"source": 0, "target": 1}, ...]
  },
  "max_iterations": 10
}

Response:

{
  "success": true,
  "color_history": [...],
  "iterations": 3
}

POST /api/wl/check_nodes

Check if two nodes always have the same color.

Request:

{
  "graph": {...},
  "node1": 0,
  "node2": 1,
  "max_iterations": 10
}

POST /api/wl/isomorphism

Test if two graphs are potentially isomorphic.

Request:

{
  "graph1": {...},
  "graph2": {...},
  "max_iterations": 10
}

Technologies Used

• Backend: Flask (Python) - for the local development version
• Frontend: HTML5, CSS3, JavaScript (ES6+)
• Visualization: Native SVG manipulation
• Graph Library: NetworkX (Python backend) / Client-side implementation (GitHub Pages)
• Deployment: GitHub Pages + GitHub Actions

GitHub Pages Deployment

This project is automatically deployed to GitHub Pages whenever changes are pushed to the main branch. The deployment includes:

• A standalone, single-page HTML application in the docs/ directory
• Client-side implementation of the Weisfeiler-Lehman algorithm in JavaScript
• All functionality available without a backend server

The GitHub Actions workflow handles the deployment automatically. To deploy your own fork:

1. Enable GitHub Pages in your repository settings
2. Set the source to "GitHub Actions"
3. Push changes to the main branch
4. The workflow will automatically build and deploy

The live site will be available at: https://[username].github.io/wl-viz/

• Graph Library: NetworkX

License

MIT License