A high-performance, robust, menu-driven network cabling optimization system implemented in pure C++20 using only standard library features.
netopt models computer networks as undirected, weighted graphs and computes optimal Minimum Spanning Trees (MST) and Spanning Forests using Kruskal's algorithm, Prim's algorithm with an indexed 4-ary min-heap, and Prim's dense array
-
Deterministic Total Ordering: Strict composite ordering
(cost, edge_id)guarantees 100% IDENTICAL edge sets across Prim (Heap), Prim (Dense), and Kruskal on all graph topologies. -
Cache-Conscious Data Structures:
- Compressed Sparse Row (CSR) adjacency representations (
offsets_size$V+1$ ,arcs_size$2E$ ). - Indexed 4-ary Min-Heap with in-place
$O(\log_4 V)$ decreaseKeyand half the depth of binary heaps. - Disjoint Set Union (DSU) with iterative path halving and union-by-size (
$O(\alpha(V))$ amortized).
- Compressed Sparse Row (CSR) adjacency representations (
-
Three Advanced Engineering Modules:
-
Algorithm Replay Visualizer: Writes frame-by-frame DOT traces and generates self-contained interactive HTML sliders (
tools/animate.py). -
Failure-Resilience & Sensitivity Engine: Identifies critical network bridges (Single Points of Failure), calculates non-tree cable cost tolerances via
$O(\log V)$ binary lifting, and computes the second-best MST. -
Self-Verifying Engine & Benchmark Lab: Validates 4 mathematical MST optimality invariants and sweeps graph scales (
$V = 10^2 \dots 10^5$ ) with log-log scaling fits (tools/plot_benchmarks.py).
-
Algorithm Replay Visualizer: Writes frame-by-frame DOT traces and generates self-contained interactive HTML sliders (
- Resilient Multi-Diagnostic Parser: Full RFC 4180 tokenizer supporting quotes, UTF-8 BOM, CRLF, and comprehensive line-numbered error reports.
-
Atomic File Persistence: Saves files using
<filename>.tmpbefore atomicstd::filesystem::renameto prevent partial writes.
netopt/
├── CMakeLists.txt # Root build configuration with sanitizer options
├── README.md # Project documentation and build guide
├── core/ # Core types, immutable CSR Graph, Builder, DSU, 4-Ary Heap
│ ├── types.hpp
│ ├── graph.hpp
│ ├── graph_builder.hpp
│ ├── dsu.hpp
│ └── indexed_heap.hpp
├── algo/ # Strategy implementations of MST algorithms
│ ├── mst_algorithm.hpp
│ ├── mst_algorithm.cpp
│ ├── kruskal.cpp
│ ├── prim.cpp
│ └── prim_dense.cpp
├── io/ # Robust CSV parser, validator, and atomic repository
│ ├── csv_tokenizer.hpp / .cpp
│ ├── row_validator.hpp / .cpp
│ ├── graph_repository.hpp / .cpp
│ └── diagnostics.hpp
├── analysis/ # Verification, sensitivity, and empirical benchmarks
│ ├── verifier.hpp / .cpp
│ ├── sensitivity.hpp / .cpp
│ └── benchmark.hpp / .cpp
├── export/ # Graphviz DOT exporter and event frame sink
│ ├── dot_exporter.hpp / .cpp
│ └── dot_frame_sink.hpp / .cpp
├── ui/ # Robust interactive console menu
│ └── menu.hpp / .cpp
├── main.cpp # Application entry point (interactive & headless)
├── tools/ # Python animation and benchmark plotting utilities
│ ├── animate.py
│ ├── plot_benchmarks.py
│ └── make_report_assets.py
├── tests/ # Unit, property, and 1,000+ randomized cross-validation tests
│ ├── doctest.h
│ ├── test_main.cpp
│ ├── test_core.cpp
│ ├── test_parser.cpp
│ ├── test_dsu.cpp
│ ├── test_heap.cpp
│ ├── test_kruskal.cpp
│ ├── test_prim.cpp
│ ├── test_verifier.cpp
│ ├── test_sensitivity.cpp
│ └── test_crossval.cpp
├── data/ # Sample network fixtures
│ ├── sample_small_*
│ ├── sample_disconnected_*
│ ├── sample_invalid_*
│ └── sample_large_*
└── docs/ # Technical documentation
├── ARCHITECTURE.md
├── DECISIONS.md
├── PSEUDOCODE.md
├── COMPLEXITY.md
├── TEST_CASES.md
├── USER_GUIDE.md
└── results/ # Generated assets (transcripts, DOT, SVG charts, replay HTML)
- C++20 compliant compiler: GCC 11+, Clang 14+, or MSVC 2019+
- CMake 3.20+
- Ninja or Make
# Using Ninja and GCC/Clang:
cmake -B build -G "Ninja" -DCMAKE_BUILD_TYPE=Release
cmake --build build
# Using Visual Studio (MSVC):
cmake -B build -G "Visual Studio 17 2022" -A x64
cmake --build build --config Releasecmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j$(nproc)cmake -B build_san -DENABLE_SANITIZERS=ON -DCMAKE_BUILD_TYPE=Debug
cmake --build build_san./build/netopt./build/netopt data/sample_small_vertices.csv data/sample_small_edges.csvExecute the 7,650-assertion test suite via ctest:
ctest --test-dir build --output-on-failurepython tools/make_report_assets.pyThis generates all transcripts, SVG plots, DOT diagrams, replay frames, and self-contained interactive replay HTML sliders (docs/results/replay.html and docs/results/compare.html).
tools/animate.py converts frame-by-frame DOT traces into 100% self-contained, interactive HTML players with responsive inline SVG graphics (or base64-encoded PNGs). The generated HTML files work on any machine by direct double-click—no web server, no CDN, and no external files required.
# Single Algorithm Replay:
python tools/animate.py --frames <dir> --out replay.html [--format svg|png] [--title "..."]
# Side-by-Side Algorithm Comparison (e.g. Prim vs Kruskal):
python tools/animate.py --left <prim_dir> --right <kruskal_dir> --out compare.html
# Display Command-Line Help:
python tools/animate.py --helpThe system automatically detects dot in PATH or standard installation directories. To install Graphviz:
- Windows:
winget install Graphviz.Graphviz - macOS:
brew install graphviz - Linux (Ubuntu/Debian):
sudo apt install graphviz
If Graphviz is not installed:
tools/animate.pyexits cleanly with code0.- The HTML player is still generated with full interactive controls (Prev, Next, Play/Pause, range slider, keyboard navigation).
- A prominent yellow alert banner is displayed at the top explaining how to install Graphviz.
- The frame viewport displays syntax-highlighted DOT source code in place of rendered graphics.
- Prev / Next Buttons & Slider: Step frame-by-frame or scrub through execution.
- Play / Pause: Auto-play algorithm progression at 1 frame per second.
- Running Cost Badge: Displays cumulative tree cost updated at each step.
- Side-by-Side Mode: Shows synchronized Prim vs Kruskal execution with automated MST cost match verification (
5,300vs5,300). - Keyboard Shortcuts:
←(Left Arrow): Previous step→(Right Arrow): Next stepSpace: Toggle Play / PauseHome: Jump to first frameEnd: Jump to final frame
If this implementation of Kruskal, Prim (4-ary heap), and CSR graphs in C++20 helped your understanding or coursework, please consider giving this repository a star (⭐)!
- 🎓 UniGrade Pro — Modern academic grade tracking, GPA/CGPA computation, and attendance predictor (Live App).
- 👗 Fitting Room AI — Personal AI stylist & smart digitized wardrobe with body shape calibration (React, Vite, Supabase).
- 🌾 Kisan Mandi Connect — Indian agritech logistics solver using Dijkstra & 0/1 Knapsack DP in Core Java.
- 💼 Portfolio — Developer portfolio (Live Site).