Граф залежностей — орієнтований граф, що відображає співвідношення множини елементів деякої сукупності відповідно до вибраних транзитивних відношень над нею.
Такі графи часто застосовують в інформатиці та цифровій електроніці, зокрема, за графом залежностей визначають порядок обчислень або невідповідність порядку залежностям, заданим графом.
Визначення
Нехай дано множину об'єктів і відношення транзитивності де , що моделює залежність «для обчислення потрібно спочатку обчислити », тоді граф залежностей — це граф де і є транзитивним замиканням .
Наприклад, деякий калькулятор підтримує запис константи в деяку змінну і додавання двох змінних із записом результату в деяку третю змінну. Нехай дано кілька виразів, наприклад, . Тоді і . Можна явно вивести всі відношення: залежить від і , тому що дві змінні можна додати тоді й лише тоді, коли відомі значення обох змінних. Таким чином, і слід обчислити перед . Однак, значення відоме зразу, тому що це числова константа.
Виявлення неможливих обчислень Циклічні залежності в графі залежностей призводять до ситуації, в якій немає доступного порядку обчислень, тому що жоден з об'єктів циклу не можна вважати першим. Якщо циклічних залежностей немає, то ми маємо спрямований ациклічний граф, і порядок обчислень можна визначити за допомогою топологічного сортування. Більшість алгоритмів топологічного сортування здатні виявляти цикли на вході, однак, бажано виявляти цикли окремо від топологічного сортування, щоб забезпечити належне їх опрацювання.
У прикладі на основі калькулятора, система виразів містить циклічну залежність. слід обчислити перед , слід обчислити перед , слід обчислити перед .
Визначення порядку обчислень Коректний порядок обчислень — це нумерація об'єктів, яка впорядковує вузли графа залежностей так, що виконується рівність: , де . Це означає, що якщо нумерацією визначено, що обчислюється перед , то не може залежати від . Більш того, може існувати більше ніж один коректний порядок обчислень. По суті, коректна нумерація є топологічним сортуванням, і будь-яке топологічне сортування є коректною нумерацією. Насправді, будь-який алгоритм, що виконує коректне топологічне сортування, одночасно визначає коректний порядок обчислень.
Для системи (в прикладі з калькулятором) коректний порядок: , однак, також є коректним порядком обчислень.
Моноїдна структура Ациклічний граф залежностей відповідає сліду слідового моноїда так:
Функція позначає кожну вершину символом з алфавіту Ребро або існує тоді й лише тоді, коли перебуває у відношенні залежності . Два графи вважаються рівними, за умови відповідності їхніх міток та ребер.
Тоді рядок, що складається з міток вершин, упорядкованих правильним порядком оцінки, відповідає рядку сліду.
Моноїдна операція приймає диз'юнктне об'єднання множин вершин двох графів, зберігає наявні в кожному графі ребра та малює нові ребра від першого до другого, де це дозволяє відношення залежності
Тотожністю є порожній граф.
Приклади Граф залежностей використовують у:
Автоматизованому встановленні програмного забезпечення. Рухом по графу знаходять пакунки програм, які потрібні, але ще не встановлені. Залежності визначаються зв'язками між пакунками. В компілятор і формальних мовах:
Планування інструкцій. Граф залежностей обчислюється для операндів асемблера або проміжних інструкцій і використовується для визначення оптимального порядку інструкцій. Видалення мертвого коду: якщо жодна побічна операція не залежить від змінної, ця змінна вважається мертвою і її можна видалити.
Графи залежностей це одне з питань:
Теорії обмежень: початкові дані перероблюються в кінцеві в ході декількох залежних етапів. Теорії розкладів — набір взаємопов'язаних теоретичних проблем у галузі комп'ютерних наук.
Див. також Топологічне сортування Залежність даних
Примітки
Джерела
Література Balmas, Francoise (2001) Displaying dependence graphs: a hierarchical approach, wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)
Посилання Compiler research project. Граф залежностей