This is a repository of our group project for the Engineering Distributed Infrastructure (Inżynieria Rozproszonej Infrastruktury Obliczeniowej / IRIO) elective offered by the Faculty of Mathematics, Informatics and Mechanics at the University of Warsaw (further referred to as "MIM UW") in the 2022/2023 winter semester.
The exact problem description we received can be found here.
In our solution, we incorporated graph partitioning as described in this paper, choosing a single-level K-means clustering strategy.
Our sparse graph of choice was the map of Monaco.
We wrote most of the project in C++ (plus some Python scripts for graph pre-processing, uploading it to a Postgres database and hosting a Flask server), using GRPC as the communication protocol between components and finally deployed on Google Kubernetes Engine.
A high-level diagram of our system:
A detailed description of our system's control flow can be found here.
Copyright of the task's description and resources: MIM UW.