МЕТОД ЗМЕНШЕННЯ ГРАФА ВИДИМОСТІ ДЛЯ ОРТОГОНАЛЬНОЇ ВІЗУАЛІЗАЦІЇ РЕБЕР ГРАФА

Анотація

Метод зменшення графа видимості за допомогою графової нейронної мережі для ортогонального зображення ребер графа. У статті розглядається актуальна задача прискорення побудови ортогонального зображення ребер графа, яка є важливою складовою автоматичного зображення графів у технічних діаграмах, таких як UML-діаграми, схеми бізнес-процесів та електричні схеми. Існуючі провідні методи ортогонального зображення ребер базуються на побудові повного ортогонального графа видимості з наступним пошуком оптимального шляху, що призводить до квадратичної залежності кількості ребер графа видимості від кількості вершин діаграми та обмежує можливість інтерактивної роботи з великими графами. Проведений аналіз останніх досліджень та публікацій показав, що графові нейронні мережі вже успішно застосовуються для зменшення часу роботи методів на графах у суміжних галузях, зокрема для зменшення простору пошуку в задачах комбінаторної оптимізації, навчання оцінювальних функцій для методів пошуку найкоротшого шляху та розрідження графів перед розв'язанням задачі комівояжера, проте ці підходи досі не були застосовані до задачі ортогонального зображення ребер, де специфічна геометрична структура графа видимості та багатокритеріальна функція вартості шляху вимагають спеціалізованого підходу. Метою роботи є розробка методу зменшення ортогонального графа видимості за допомогою графової нейронної мережі, який дозволив би зменшити кількість ребер графа видимості перед виконанням пошуку оптимального шляху, зберігаючи при цьому якість зображення ребер, порівнянну з результатами існуючих методів. Запропонований метод складається з чотирьох послідовних етапів: побудова графа-кандидата без перевірки фактичної видимості між вершинами, класифікація ребер попередньо навченою графовою нейронною мережею, відсіювання ребер з низькою ймовірністю входження до шуканого шляху та пошук шляху на зменшеному графі. Принциповою відмінністю від існуючих підходів є те, що розрідження виконується на етапі побудови графа видимості, а не на етапі пошуку шляху, що дозволяє зменшити час обробки на обох етапах. Описано процес формування навчального набору даних та навчання нейронної мережі, де результат роботи існуючого методу використовується як еталон для розпізнавання ребер, що є частиною шуканих шляхів. Резервний механізм гарантує, що у випадку невдалого розрідження результат роботи запропонованого методу ніколи не буде гіршим за результат існуючих методів.