This repository presents an interactive educational tool for understanding and visualizing the Warshall algorithm, a fundamental algorithm in graph theory used for computing the transitive closure of directed graphs. The implementation provides a step-by-step visualization of the algorithm's execution, making it an effective learning resource for computer science students and educators.

The Warshall algorithm, developed by Stephen Warshall in 1962, is an efficient method for finding the transitive closure of a directed graph. This implementation serves as both an educational tool and a practical demonstration of the algorithm's application in graph theory and discrete mathematics.

The Warshall algorithm computes the transitive closure of a directed graph represented by its adjacency matrix. For a graph with n vertices, the algorithm has a time complexity of O(n³) and space complexity of O(n²).

The core principle of the algorithm can be expressed as:

R^k[i][j] = R^(k-1)[i][j] OR (R^(k-1)[i][k] AND R^(k-1)[k][j])

Where:

• R^k represents the reachability matrix after considering vertex k as an intermediate
• R^0 is the initial adjacency matrix
• R^n is the final transitive closure

This project implements the Warshall algorithm using:

• Backend: Flask (Python)
• Frontend: HTML, CSS, JavaScript
• Architecture: Model-View-Controller (MVC) pattern

The implementation includes:

• Dynamic matrix generation with user-defined dimensions
• Step-by-step algorithm execution
• Visual representation of each iteration
• Mathematical notation and explanations

• Create adjacency matrices of arbitrary dimensions
• Execute the Warshall algorithm with step-by-step visualization
• Interactive user interface with educational annotations
• Real-time computation and display of transitive closure
• Responsive design for various devices and screen sizes

• Python 3.6 or higher
• Flask

1. Clone the repository:

   git clone https://github.com/mrVXBoT/warshal.git
   cd warshall

2. Create and activate a virtual environment (recommended):

   python -m venv venv
   
   # On Windows:
   venv\Scripts\activate
   
   # On Linux/macOS:
   source venv/bin/activate

3. Install dependencies:

   pip install -r requirements.txt

4. Run the application:

   python app.py

5. Open your browser and navigate to http://127.0.0.1:5000

1. On the main page, specify the matrix dimensions (number of vertices in the graph)
2. Click "Create Matrix"
3. Fill in the adjacency matrix (1 for edge existence, 0 for no edge)
4. Click "Run Warshall Algorithm"
5. Use the "Previous Step" and "Next Step" buttons to navigate through the algorithm's execution

The implementation follows the formal definition of the Warshall algorithm:

For a graph G with vertices V = {1, 2, ..., n} and adjacency matrix A:

1. Initialize R⁰ = A
2. For k = 1 to n:
   • For i = 1 to n:
     • For j = 1 to n:
       • R^k[i][j] = R^(k-1)[i][j] ∨ (R^(k-1)[i][k] ∧ R^(k-1)[k][j])
3. The final matrix R^n is the transitive closure of G

This tool is particularly useful for:

• Computer Science courses on Algorithms and Data Structures
• Discrete Mathematics courses covering Graph Theory
• Self-study of fundamental graph algorithms
• Classroom demonstrations of algorithm execution

Potential enhancements include:

• Implementation of related algorithms (Floyd-Warshall for shortest paths)
• Graph visualization alongside matrix representation
• Algorithm complexity analysis visualization
• Support for weighted graphs
• Export functionality for results and execution traces

1. Warshall, S. (1962). "A theorem on boolean matrices". Journal of the ACM, 9(1), 11-12.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
3. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.

This project is licensed under the MIT License - see the LICENSE file for details.

If you use this implementation in your research or teaching, please cite:

@software{warshall_algorithm_implementation,
  author = {VX},
  title = {Interactive Educational Implementation of the Warshall Algorithm},
  year = {2025},
  url = {https://github.com/mrVXBoT/warshal.git}
}