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

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

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

Визначення ред.

Нехай дано множину об'єктів $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\rightarrow 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)$ також є коректним порядком обчислень.

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

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

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

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

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

$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\}$

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

Приклади ред.

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

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

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

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

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

Див. також ред.

Примітки ред.

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

Джерела ред.

↑ ^а ^б Mazurkiewicz, Antoni (1995). Introduction to Trace Theory. У Rozenberg, G.; Diekert, V. (ред.). The Book of Traces (англ.). Singapore: World Scientific. ISBN 981-02-2058-8. {{cite book}}: |access-date= вимагає |url= (довідка)

Література ред.

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

Посилання ред.

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

[2] Наприклад, в утилітах make

[IntroToTraceTheory-1] а ^б Mazurkiewicz, Antoni (1995). Introduction to Trace Theory. У Rozenberg, G.; Diekert, V. (ред.). The Book of Traces (англ.). Singapore: World Scientific. ISBN 981-02-2058-8. {{cite book}}: |access-date= вимагає |url= (довідка)

[1]

[a]