How muhaibshamsher/mst-kruskal-and-prims works
Project Type and Purpose
• This is a full-stack, computationally intensive web application that uses WebAssembly to run high-performance MST algorithms (Prim’s and Kruskal’s) written in C++.
File Structure
• There are two main sections in the file tree:
• The “Algorithms” directory holds the C++ source files (kruskal.cpp, prims.cpp), related header files in the “Project” directory (kruskal.h, prims.h), and supplementary files like graph.txt and images which likely illustrate the algorithm process or graph data.
• The “Project” directory contains web-specific assets: main.cpp (possibly with application’s entry point for WebAssembly integration), HTML (output.html), JavaScript (output.js and script.js), CSS (style.css), and the compiled WebAssembly module (output.wasm).
• Supporting files like Project PPT and Project Report provide documentation and further context.
README for Architectural Insights
• The README clarifies that the application bridges browser-based visualization (via HTML/JS/CSS) with performance-critical calculations executed through WebAssembly.
• It explains the use of two MST algorithms (Prim’s and Kruskal’s) to generate the pipeline network while comparing their performance.
• WebAssembly is central to providing cross-browser compatibility and real-time performance on complex computations.
Main Components and Their Relationships
a. Components:
• Web Frontend: HTML page (output.html), CSS (style.css), and JavaScript files (script.js, output.js) responsible for user interaction, input handling, and visualizing the pipeline network.
• WASM Integration: The WebAssembly module (output.wasm) containing the compiled C++ algorithms (from Algorithms/kruskal.cpp and Algorithms/prims.cpp, with corresponding headers in Project) is the core computational engine.
• MST Algorithms: Both Prim’s and Kruskal’s algorithms are embodied in the C++ code. They run in the WASM environment and compute the minimum spanning tree.
• Data Inputs: Graph data (potentially stored in Algorithms/graph.txt) which represents the 2D coordinates for houses and is the basis for MST calculation.
• Additional assets: Documentation, images for visualization, and supplementary files (PPT, report) that outline design and performance comparisons.
b. Relationships and Data Flow:
• The user interacts with the web interface (HTML/CSS/JS) which triggers events (via script.js) that lead to calls to the WebAssembly module.
• Data (graph data) may be loaded into the browser environment and passed as input to the underlying MST algorithm functions via JS-WASM calls.
• The WebAssembly module executes the MST algorithms in C++ (leveraging both Prim’s and Kruskal’s approaches), then returns the computed MST (both in cost and structure) back to the JavaScript layer.
• The JavaScript layer handles the results, compares performance and cost metrics, and updates the web interface (possibly re-rendering the visualization using DOM manipulation or canvas) to show the optimized pipeline network.
• Separation of concerns:
• Integration using WebAssembly: Emphasize that performance-intensive tasks are offloaded to the WASM module.
• Mention that two MST algorithms are deployed concurrently or compared, indicating modularity in how algorithm implementations can be interchanged or benchmarked.
• Cross-browser compatibility and performance optimization goals provided by leveraging WebAssembly.
Final Recommendations
• Clear labels for each major component.
• Decision points such as selecting the optimal MST based on cost and performance.