Граф зависимостей

Граф зависимостей — ориентированный граф, отображающий соотношение элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней. Широко применяется в информатике и цифровой электронике, в частности, по графу зависимостей определяется порядок вычислений или его недостатки, согласованные с данными зависимостями в графе.

Определение

Пусть дано множество объектов $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$. Это означает, что если нумераций определяется, что а вычисляется перед $b$, то а не может зависеть от $b$. Более того, может существовать более одного корректного порядка вычислений. По сути, корректная нумерация является топологической сортировкой, и любая топологическая сортировка является корректной нумерацией. На самом деле, любой алгоритм, производящий корректную топологическую сортировку, одновременно определяет корректный порядок вычисления.

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

Примеры

Граф зависимостей используется в:

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

• Планирование инструкций. Граф зависимостей вычисляется для операндов ассемблера или промежуточных инструкций и используется для определения оптимального порядка инструкций.
• Удаление мёртвого кода.

Графы зависимости это один из вопросов:

• Теории ограничений. Исходные данные перерабатываются в результирующие в ходе нескольких зависимых этапов.
• Планирования. Набор взаимосвязанных теоретических проблем в области компьютерных наук.

См. также

• Топологическая сортировка
• Зависимость данных

Литература

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

Сылки

• Compiler research project. Граф зависимостей