MST Visualizer - ISP Network Planner

An interactive web application that demonstrates Minimum Spanning Trees (MST) using Kruskal's algorithm, visualized on a real map of Chișinău, Moldova. The theme simulates an Internet Service Provider finding the cheapest way to connect client buildings to their network hub using actual road routes.

Features

• Interactive Map - Leaflet.js with OpenStreetMap tiles centered on Chișinău
• Real Road Routing - Edges follow actual streets via OSRM (Open Source Routing Machine)
• Draggable Nodes - Reposition any marker by dragging it on the map
• Add Custom Clients - Click anywhere to add new client locations
• Algorithm Visualization - Watch Kruskal's algorithm step-by-step:
  • Green edges = accepted (part of MST)
  • Red edges = rejected (would form a cycle)
• Adjustable Speed - Slow, Medium, or Fast animation
• Distance Labels - Shows cable length in km for each MST edge
• Route Caching - Fetched routes are cached for performance

How It Works

Kruskal's Algorithm

1. Sort all edges by weight (road distance) in ascending order
2. For each edge, check if adding it would form a cycle using Union-Find
3. If no cycle → accept the edge (add to MST)
4. If cycle → reject the edge
5. Repeat until all nodes are connected

Union-Find Data Structure

The backend uses an optimized Union-Find (Disjoint Set) implementation with:

• Path compression - Flattens tree structure during find operations
• Union by rank - Attaches smaller trees under larger ones

Road Routing

Instead of straight-line distances, the app fetches real driving routes from OSRM:

• Routes follow actual Chișinău streets
• One-way directionality is neutralized for undirected cable planning by comparing both travel directions and using the shorter road length
• Distance reflects true road length, not as-the-crow-flies
• More realistic for cable/fiber laying scenarios

Tech Stack

Component	Technology
Backend	Node.js + Express
Frontend	Vanilla HTML/CSS/JS
Map	Leaflet.js 1.9.x
Tiles	OpenStreetMap
Routing	OSRM (Open Source Routing Machine)
Algorithm	Kruskal's MST with Union-Find

Getting Started

Prerequisites

• Node.js 18+ installed
• npm or yarn

Installation

# Clone the repository
git clone https://github.com/LiviuTurcan/MST-Network-Showcase.git
cd MST-Network-Showcase

# Install dependencies
npm install

# Start the server
npm start

The app will be running at http://localhost:3000

Usage

1. Open the app in your browser at http://localhost:3000
2. Add clients by clicking "+ Add Client", then click on the map
3. Reposition nodes by dragging any marker
4. Run the algorithm by clicking "Run Kruskal's"
5. Adjust speed using the slider (Slow/Medium/Fast)
6. Reset to clear all edges and start over

API Reference

POST /api/kruskal

Runs Kruskal's algorithm on the provided graph.

Request Body:

{
  "nodes": [
    { "id": "node1", "lat": 47.0248, "lng": 28.8282 },
    { "id": "node2", "lat": 47.0200, "lng": 28.8300 }
  ],
  "edges": [
    { "from": "node1", "to": "node2", "weight": 0.52 }
  ]
}

Response:

{
  "steps": [
    { "from": "node1", "to": "node2", "weight": 0.52, "accepted": true }
  ],
  "totalWeight": 0.52,
  "mstEdges": [
    { "from": "node1", "to": "node2", "weight": 0.52 }
  ]
}

Project Structure

mst-visualizer/
├── server.js          # Express backend with Kruskal's algorithm
├── package.json       # Dependencies and scripts
├── README.md          # This file
└── public/
    └── index.html     # Frontend (HTML, CSS, JS inline)

Algorithm Complexity

Operation	Time Complexity
Edge sorting	O(E log E)
Union-Find operations	O(α(n)) ≈ O(1) amortized
Overall Kruskal's	O(E log E)

Where E = number of edges, α = inverse Ackermann function

Screenshots