# musaabimran/top-k-shortest-path-problem architecture

> Architecture diagram of the GitHub repository musaabimran/top-k-shortest-path-problem, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-03-30). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/musaabimran/top-k-shortest-path-problem
- Repository: https://github.com/musaabimran/top-k-shortest-path-problem

## Overview

##### Main Components
- Input/Parsing Component:
- Reads the weighted graph from an input file. This is responsible for parsing the file (actual sample options provided include doctorwho.csv, Email-Euron.txt, etc.) and formatting it appropriately.
- Distance Matrix Initialization:
- Prepares the initial distance matrix by setting self-distances to 0 and other missing edges to infinity. The matrix represents the graph internally.
- MPI-Based Module (Inter-Process Communication):
- Each process handles computation on its subset (calculating local shortest paths).
- OpenMP-Based Module (Intra-Process Parallelism):
- Within each MPI process, OpenMP is used to parallelize intensive looping constructs that perform the path computations.
- Result Gathering and Combination:
- Once every process has computed its local solution, MPI is again used to gather and combine these local solutions into the final Top K shortest path result.
- Execution and Control Flow:
- Contains both serial and parallel execution entry points, depending on the build and runtime configuration.

##### Relationships and Interactions
- Data Flow:
- Graph input is parsed and used to initialize the distance matrix.
- The distance matrix data is distributed among MPI processes (each receiving a subset of the matrix or graph).
- Within each MPI process, OpenMP threads operate on specific portions of that matrix to compute shortest paths.
- Once local computations are complete, MPI processes exchange data to combine local results into the final global result.
- Dependencies:
- The MPI module handles inter-process communication while the OpenMP module deals with in-process parallelism.
- The control and synchronization mechanisms ensure correct data propagation and merging.

##### Architectural Patterns and Design Principles
- Hybrid Parallelism Pattern:
- Combined use of MPI and OpenMP demonstrates a layered parallelism approach. MPI handles multi-node or multi-process computation while OpenMP further accelerates this on shared-memory systems.
- Divide and Conquer:
- Pipeline of computation:

##### Technologies and Libraries
- MPI (Message Passing Interface): Used for distributing computation and exchanging data between processes.
- OpenMP: Provides multi-threading within individual processes, essential for the inner-loop performance.
- C++: The core implementation language, represented by the .cpp files.

## Diagram (Mermaid)

```mermaid
flowchart TD
    F["Execution & Control"]:::control
    click F "https://github.com/musaabimran/top-k-shortest-path-problem/blob/main/README.md"
    
    F --> A["Input Parser"]:::input
    click A "https://github.com/musaabimran/top-k-shortest-path-problem/blob/main/code.cpp"
    
    A --> B["Distance Matrix Initializer"]:::init
    click B "https://github.com/musaabimran/top-k-shortest-path-problem/blob/main/code.cpp"
    
    B --> C1["MPI Process 1"]:::mpi
    click C1 "https://github.com/musaabimran/top-k-shortest-path-problem/blob/main/parallal.cpp"
    B --> C2["MPI Process 2"]:::mpi
    click C2 "https://github.com/musaabimran/top-k-shortest-path-problem/blob/main/parallal.cpp"
    
    C1 --> D1["OpenMP Workers 1"]:::openmp
    click D1 "https://github.com/musaabimran/top-k-shortest-path-problem/blob/main/parallal.cpp"
    C2 --> D2["OpenMP Workers 2"]:::openmp
    click D2 "https://github.com/musaabimran/top-k-shortest-path-problem/blob/main/parallal.cpp"
    
    D1 --> E["Result Aggregator"]:::aggregator
    click E "https://github.com/musaabimran/top-k-shortest-path-problem/blob/main/parallal.cpp"
    D2 --> E

    E --> F

    classDef control fill:#d3d3d3,stroke:#333,stroke-width:2px;
    classDef input fill:#ADD8E6,stroke:#333,stroke-width:2px;
    classDef init fill:#87CEFA,stroke:#333,stroke-width:2px;
    classDef mpi fill:#90EE90,stroke:#333,stroke-width:2px;
    classDef openmp fill:#FFFF99,stroke:#333,stroke-width:2px;
    classDef aggregator fill:#FFB6C1,stroke:#333,stroke-width:2px;
```
