Граф зависимостей
Граф зависи́мостей — ориентированный граф, отображающий соотношение множества элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней.
Этот граф часто применяется в информатике и цифровой электронике, в частности, по графу зависимостей определяется порядок вычислений или его недостатки, согласованные с данными зависимостями в графе.
Определение
Пусть дано множество объектов [math]\displaystyle{ S }[/math] и отношение транзитивности [math]\displaystyle{ R = S \times S }[/math] где [math]\displaystyle{ (a,b) \in R }[/math], моделирующее зависимость «для вычисления [math]\displaystyle{ a }[/math] нужно сначала вычислить [math]\displaystyle{ b }[/math]», тогда граф зависимостей — это граф [math]\displaystyle{ G = (S, T) }[/math] где [math]\displaystyle{ T \subseteq R }[/math] и [math]\displaystyle{ R }[/math] является транзитивным замыканием [math]\displaystyle{ T }[/math].
Например, некоторый калькулятор поддерживает запись константы в некоторую переменную и сложение двух переменных с записью результата в некоторую третью переменную. Пусть дано несколько выражений, например, [math]\displaystyle{ A = B + C; B = 5 + D; C = 4; D = 2 }[/math]. Тогда [math]\displaystyle{ S={A,B,C,D} }[/math] и [math]\displaystyle{ R={(A,B),(A,C),(B,D)} }[/math]. Можно явно вывести все отношения: [math]\displaystyle{ A }[/math] зависит [math]\displaystyle{ B }[/math] и [math]\displaystyle{ C }[/math], потому что две переменные можно складывать тогда и только тогда, когда известны значения обеих переменных. Таким образом, [math]\displaystyle{ B }[/math] и [math]\displaystyle{ C }[/math] должны быть вычислены перед [math]\displaystyle{ A }[/math]. Однако, значение [math]\displaystyle{ D }[/math] известно сразу, потому что это числовая константа.
Обнаружение невозможных вычислений
Циклические зависимости в графе зависимостей приводят к ситуации, в которой нет доступного порядка вычислений, потому что ни один из объектов цикла не может считаться первым. Если циклических зависимостей нет, то мы имеем направленный ациклический граф, и порядок вычислений может быть определен с помощью топологической сортировки. Большинство алгоритмов топологической сортировки способны обнаруживать циклы на входе, однако, желательно обнаруживать циклы отдельно от топологической сортировки.
В примере на основе калькулятора, вычислительная система [math]\displaystyle{ A=B; B=D+C; C=D+A; D=12 }[/math] содержит циклическую зависимость. [math]\displaystyle{ B }[/math] должно быть вычислено до [math]\displaystyle{ A }[/math], [math]\displaystyle{ C }[/math] должно быть вычислено до [math]\displaystyle{ B }[/math], [math]\displaystyle{ A }[/math] должно быть вычислено до [math]\displaystyle{ C }[/math].
Определение порядка вычислений
Корректный порядок вычислений — это нумерация [math]\displaystyle{ n : S \rightarrow N }[/math] объектов, которая упорядочивает узлы графа зависимостей так, что имеет место равенство: [math]\displaystyle{ n(a) \lt n(b) \Rightarrow (a, b) \notin R }[/math], где [math]\displaystyle{ a, b \in S }[/math]. Это означает, что если нумераций определяется, что [math]\displaystyle{ a }[/math] вычисляется перед [math]\displaystyle{ b }[/math], то [math]\displaystyle{ a }[/math] не может зависеть от [math]\displaystyle{ b }[/math]. Более того, может существовать более одного корректного порядка вычислений. По сути, корректная нумерация является топологической сортировкой, и любая топологическая сортировка является корректной нумерацией. На самом деле, любой алгоритм, производящий корректную топологическую сортировку, одновременно определяет корректный порядок вычисления.
Для системы (в примере с калькулятором) [math]\displaystyle{ A = B+C; B = 5+D; C=4; D=2 }[/math] корректный порядок: [math]\displaystyle{ (D, C, B, A) }[/math], однако, [math]\displaystyle{ (C, D, B, A) }[/math] также является корректным порядком вычислений.
Примеры
Граф зависимостей используется в:
- Автоматизированной установке программного обеспечения.[1] Происходит движение по графу в поисках пакетов программ, которые нужны, но ещё не установлены. Зависимости определяются связанностью пакетов.
- В компиляторах и формальных языках:
- Планирование инструкций. Граф зависимостей вычисляется для операндов ассемблера или промежуточных инструкций и используется для определения оптимального порядка инструкций.
- Удаление мёртвого кода.
Графы зависимости это один из вопросов:
- Теории ограничений. Исходные данные перерабатываются в результирующие в ходе нескольких зависимых этапов.
- Планирования. Набор взаимосвязанных теоретических проблем в области компьютерных наук.
См. также
Примечания
Литература
- 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