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

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

Этот граф часто применяется в информатике и цифровой электронике, в частности, по графу зависимостей определяется порядок вычислений или его недостатки, согласованные с данными зависимостями в графе.

Определение

Пусть дано множество объектов ${\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)}$ также является корректным порядком вычислений.

Примеры

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

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

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

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

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

См. также

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

Примечания

1. Например, в утилитах make

Литература

• 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