Graph Tasks

Solutions for graph algorithm tasks.

Implemented Tasks

• task1.1 - graph implementation and RPO numbering with cycle detection.
• task1.2 - Dijkstra's shortest path algorithm.
• task1.3 - maximum flow using Dinic's algorithm.
• task1.4 - Tarjan's algorithm for strongly connected components.

The shared graph implementation is placed in common.

Build

cmake -S . -B build
cmake --build build

After the build, executables are available in the build directory:

build/task1_1
build/task1_2
build/task1_3
build/task1_4

Run

Example:

./build/task1_2 < tests/task1.2/01.in

Tests

Tests are stored in the tests directory as .in / .out pairs.

Run all tests:

python3 tests/tasks_tester.py

Requirements

• C++23
• CMake 3.20+
• g++ or a compatible compiler
• python3 for running tests