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

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

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

Визначення

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

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

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

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

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

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

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

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

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

Ациклічний граф залежностей відповідає сліду слідового моноїда такШаблон:R:

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

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

Моноїдна операція $(S_{12},R_{12})=(S_1,R_1)\bullet (S_2,R_2)$ приймає диз'юнктне об'єднання $S_{12}=S_1\bigsqcup S_2$ множин вершин двох графів, зберігає наявні в кожному графі ребра та малює нові ребра від першого до другого, де це дозволяє відношення залежностіШаблон:R

$R_{12}=R_1\bigsqcup R_2\bigsqcup \{(a,b)\mid a\in S_1\wedge b\in S_2\wedge (\varphi (a),\varphi (b))\in D\}$

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

Приклади

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

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

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

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

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

Див. також

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

Література

• Balmas, Francoise (2001) Displaying dependence graphs: a hierarchical approach, [1] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)

Посилання

• Compiler research project. Граф залежностей Шаблон:Webarchive Шаблон:Ref-ru