This repository contains implementations of various graph algorithms covered during the course. Each lab includes problem descriptions, code implementations, and example test cases.
| Laboratory/Project | Description |
|---|---|
| Lab 1: Warmup | Introduction to graph algorithms |
| Lab 2: Maximum Flows | Ford-Fulkerson and Edmonds-Karp algorithms for maximum flows |
| Lab 3 & 4: Edge Connectivity | Edge connectivity and Stoer-Wagner algorithm |
| Lab 5 & 6: Chordal Graphs | Recognition and solving problems for chordal graphs using LexBFS |
| Lab 7: NetworkX Library, Planarity, Flows, and SAT-2CNF | NetworkX library usage, planarity testing, maximum flows, and SAT-2CNF |
| Project 1: Royal Route | Finding the maximal independent set in a chordal graph |
| Project 2: (Almost) Chess Tournament | Graph game problem and maximal matching |
-
Clone the repository:
git clone https://github.com/OlaszPL/Graph_algorithms_2025.git cd Graph_algorithms_2025 -
Install the required (only for Lab7) dependencies:
pip install -r requirements.txt
-
Navigate to the respective lab or project directory and follow the instructions provided in the README file located in each directory.
This project is licensed under the MIT License - see the LICENSE file for details.
For more information, please refer to the individual README files (in Polish) located within each lab and project directory.