Застосування патернiв проектування в сучасному C++ для реалiзацiї операторiв на графах
Loading...
Date
2026
Authors
Нагорний, Юрiй
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Квалiфiкацiйну роботу присвячено проблемi пiдвищення обчислювальної ефективностi структурних графових операторiв шляхом їх iнтеграцiї у подiє-орiєнтовану архiтектуру спiльного обходу засобами сучасного стандарту C++20. Встановлено архiтектурнi обмеження класичних узагальнених бiблiотек (на прикладi BGL) та сформульовано математичнi критерiї сумiсностi операторiв iз механiзмом спiльного обходу. Розроблено оригiнальний алгоритм побудови реберного графа та адаптовано iтеративний алгоритм розпiзнавання реберних графiв ILIGRA до виконання за один прохiд пошуку в ширину (BFS). Спроєктовано прототип графової бiблiотеки iз застосуванням статичних патернiв Вiдвiдувач та Компонувальник на базi концептiв (Concepts) iз нульовими накладними витратами. Обчислювальнi експерименти довели, що застосування спiльного обходу забезпечує до 16% приросту продуктивностi завдяки мiнiмiзацiї промахiв кешу процесора, а декомпозицiя алгоритмiв на подiї Вiдвiдувача скорочує час виконання масивних структур до 27% за рахунок агресивного вбудовування функцiй (inlining) компiлятором.
Description
This qualification paper is devoted to the problem of improving the computational efficiency of structural graph operators by integrating them into an eventdriven joint traversal architecture using modern C++20 standard tools. The architectural limitations of classic generic libraries (using BGL as an example) are established, and the mathematical criteria for the compatibility of operators with the joint traversal mechanism are formulated. An original algorithm for line graph construction is developed, and the iterative line graph recognition algorithm ILIGRA is adapted for execution in a single pass of the breadth-first search (BFS). A prototype of a graph library is designed utilizing static Visitor and Composite design patterns based on Concepts with zero-overhead abstractions. Computational experiments have proven that the application of joint traversal provides up to a 16% performance increase by minimizing CPU cache misses. Furthermore, the decomposition of algorithms into Visitor events reduces the execution time for massive structures by up to 27% due to aggressive function inlining by the compiler.
Keywords
теорiя графiв, реберний граф, алгоритм ILIGRA, патерни проєктування, C++20, спiльний обхiд, патерн Вiдвiдувач, бакалаврська робота, graph theory, line graph, ILIGRA algorithm, design patterns, C++20, joint traversal, Visitor pattern