Граф залежностей

Граф залежностей — орієнтований граф, що відображає співвідношення множини елементів деякої сукупності відповідно до вибраних транзитивних відношень над нею.

Такі графи часто застосовують в інформатиці та цифровій електроніці, зокрема, за графом залежностей визначають порядок обчислень або невідповідність порядку залежностям, заданим графом.

Визначення

Нехай дано множину об'єктів ${\displaystyle S}$ і відношення транзитивності ${\displaystyle R=S\times S}$ де ${\displaystyle (a,b)\in R}$, що моделює залежність «для обчислення ${\displaystyle a}$ потрібно спочатку обчислити ${\displaystyle b}$», тоді граф залежностей — це граф ${\displaystyle G=(S,T)}$ де ${\displaystyle T\subseteq R}$ і ${\displaystyle R}$ є транзитивним замиканням ${\displaystyle T}$.

Наприклад, деякий калькулятор підтримує запис константи в деяку змінну і додавання двох змінних із записом результату в деяку третю змінну. Нехай дано кілька виразів, наприклад, ${\displaystyle A=B+C;B=5+D;C=4;D=2}$. Тоді ${\displaystyle S={A,B,C,D}}$ і ${\displaystyle R={(A,B),(A,C),(B,D)}}$. Можна явно вивести всі відношення: ${\displaystyle A}$ залежить від ${\displaystyle B}$ і ${\displaystyle C}$, тому що дві змінні можна додати тоді й лише тоді, коли відомі значення обох змінних. Таким чином, ${\displaystyle B}$ і ${\displaystyle C}$ слід обчислити перед ${\displaystyle A}$. Однак, значення ${\displaystyle D}$ відоме зразу, тому що це числова константа.

Виявлення неможливих обчислень

в графі залежностей призводять до ситуації, в якій немає доступного порядку обчислень, тому що жоден з об'єктів циклу не можна вважати першим. Якщо циклічних залежностей немає, то ми маємо спрямований ациклічний граф, і порядок обчислень можна визначити за допомогою топологічного сортування. Більшість алгоритмів топологічного сортування здатні виявляти цикли на вході, однак, бажано виявляти цикли окремо від топологічного сортування, щоб забезпечити належне їх опрацювання.

У прикладі на основі калькулятора, система виразів ${\displaystyle A=B;B=D+C;C=D+A;D=12}$ містить циклічну залежність. ${\displaystyle B}$ слід обчислити перед ${\displaystyle A}$, ${\displaystyle C}$ слід обчислити перед ${\displaystyle B}$, ${\displaystyle A}$ слід обчислити перед ${\displaystyle C}$.

Визначення порядку обчислень

Коректний порядок обчислень — це нумерація ${\displaystyle n:S\rightarrow N}$ об'єктів, яка впорядковує вузли графа залежностей так, що виконується рівність: ${\displaystyle n(a)<n(b)\Rightarrow (a,b)\notin R}$, де ${\displaystyle a,b\in S}$. Це означає, що якщо нумерацією визначено, що ${\displaystyle a}$ обчислюється перед ${\displaystyle b}$, то ${\displaystyle a}$ не може залежати від ${\displaystyle b}$. Більш того, може існувати більше ніж один коректний порядок обчислень. По суті, коректна нумерація є топологічним сортуванням, і будь-яке топологічне сортування є коректною нумерацією. Насправді, будь-який алгоритм, що виконує коректне топологічне сортування, одночасно визначає коректний порядок обчислень.

Для системи (в прикладі з калькулятором) ${\displaystyle A=B+C;B=5+D;C=4;D=2}$ коректний порядок: ${\displaystyle (D,C,B,A)}$, однак, ${\displaystyle (C,D,B,A)}$ також є коректним порядком обчислень.

Моноїдна структура

Ациклічний граф залежностей відповідає сліду (слідового моноїда) так^:12:

• Функція ${\displaystyle \phi :S\to \Sigma }$ позначає кожну вершину символом з алфавіту ${\displaystyle \Sigma }$
• Ребро ${\displaystyle a\to b}$ або ${\displaystyle b\to a}$ існує тоді й лише тоді, коли ${\displaystyle (\phi (a),\phi (b))}$ перебуває у відношенні залежності ${\displaystyle D}$.
• Два графи вважаються рівними, за умови відповідності їхніх міток та ребер.

Тоді рядок, що складається з міток вершин, упорядкованих правильним порядком оцінки, відповідає рядку сліду.

Моноїдна операція ${\displaystyle (S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})}$ приймає диз'юнктне об'єднання ${\displaystyle S_{12}=S_{1}\sqcup S_{2}}$ множин вершин двох графів, зберігає наявні в кожному графі ребра та малює нові ребра від першого до другого, де це дозволяє відношення залежності^:14

${\displaystyle R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b))\in D\}}$

Тотожністю є порожній граф.

Приклади

Граф залежностей використовують у:

• Автоматизованому встановленні програмного забезпечення. Рухом по графу знаходять пакунки програм, які потрібні, але ще не встановлені. Залежності визначаються зв'язками між пакунками.
• В компілятор і формальних мовах:

• Планування інструкцій. Граф залежностей обчислюється для операндів асемблера або проміжних інструкцій і використовується для визначення оптимального порядку інструкцій.
• Видалення мертвого коду: якщо жодна побічна операція не залежить від змінної, ця змінна вважається мертвою і її можна видалити.

Графи залежностей це одне з питань:

• Теорії обмежень: початкові дані перероблюються в кінцеві в ході декількох залежних етапів.
• Теорії розкладів — набір взаємопов'язаних теоретичних проблем у галузі комп'ютерних наук.

Див. також

• Топологічне сортування
• Залежність даних

Примітки

1. Наприклад, в утилітах make

Джерела

1. Mazurkiewicz, Antoni (1995). Introduction to Trace Theory. У Rozenberg, G.; Diekert, V. (ред.). The Book of Traces (англ.). Singapore: World Scientific. ISBN . {{}}: |access-date= вимагає |url= ()

Література

• Balmas, Francoise (2001) , [1] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)

Посилання

• Compiler research project. Граф залежностей [ 4 березня 2016 у Wayback Machine.] (рос.)