MST Algorithm Comparison

Interactive Python project for comparing Prim's Algorithm and Kruskal's Algorithm on the Minimum Spanning Tree (MST) problem. The project includes reusable MST implementations, a command-line benchmark runner, report chart generation, and a Streamlit dashboard for random or custom graphs.

Features

• Prim's Algorithm using a priority queue.
• Kruskal's Algorithm using Union-Find with path compression and union by rank.
• Connected random weighted graph generation across sparse, medium, and dense settings.
• Validation for vertex labels, duplicate edges, self-loops, positive weights, and connectivity.
• CLI benchmark table output.
• Streamlit dashboard for running experiments and uploading/editing custom edge lists.
• Reproducible chart generation for reports.

Project Structure

.
├── app/
│   ├── algorithms.py     # Prim, Kruskal, and Union-Find
│   ├── experiments.py    # Timing and correctness checks
│   ├── graph.py          # Graph generation and CSV parsing
│   ├── validation.py     # Input and connectivity validation
│   └── formatting.py     # CLI table formatting
├── docs/
│   ├── figures/          # Generated benchmark figures
│   ├── images/           # README/report images
│   └── report.md         # Project report
├── make_charts.py        # Regenerate report charts
├── mst_comparison.py     # CLI benchmark entrypoint
├── mst_dashboard.py      # Streamlit dashboard
└── edges.csv             # Example custom edge-list input

Setup

Use Python 3.11+.

python -m venv .venv
source .venv/bin/activate
python -m pip install -r requirements.txt

If you are using the course conda environment:

conda activate venv
python -m pip install -r requirements.txt

Run the Dashboard

python -m streamlit run mst_dashboard.py

Open the local URL printed by Streamlit. The sidebar lets you switch between:

• Random experiments: generate connected graphs and compare average runtimes.
• Custom graph: upload a CSV or edit an edge list manually, then inspect the MST result.

Run CLI Benchmarks

python mst_comparison.py
python mst_comparison.py --sizes 50 100 250
python mst_comparison.py --densities sparse medium dense
python mst_comparison.py --trials 5
python mst_comparison.py --seed 42

Example output:

Vertices | Edges | Density | Prim Avg ms | Kruskal Avg ms | MST Weight | MST Edges
---------+-------+---------+-------------+----------------+------------+----------
50       | 100   | sparse  | ...         | ...            | ...        | 49

Custom Graph CSV Format

Custom graph uploads use an undirected weighted edge list with these columns:

source,target,weight
0,1,4
1,2,3
0,2,5

Rules:

• Vertex labels are integers from 0 to V - 1.
• Weights must be positive integers.
• Self-loops and duplicate undirected edges are rejected.
• The graph must be connected.

Regenerate Figures

python make_charts.py

This writes deterministic benchmark images into docs/figures/.

Benchmark Figures

Development Checks

Basic syntax check:

python -m py_compile mst_dashboard.py mst_comparison.py make_charts.py app/*.py

Notes for GitHub

• Keep README.md at the repository root so GitHub renders it on the project page.
• Commit source files, README.md, docs/, edges.csv, and the images used in the report/README.
• Do not commit __pycache__/, virtual environments, or local Streamlit secrets; these are covered by .gitignore.
• Re-run python make_charts.py before final submission if algorithm or experiment settings change.