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

31.01.2022

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

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

Определение

Пусть дано множество объектов S {displaystyle S} и отношение транзитивности R = S × S {displaystyle R=S imes S} где ( a , b ) ∈ R {displaystyle (a,b)in R} , моделирующее зависимость «для вычисления a {displaystyle a} нужно сначала вычислить b {displaystyle b} », тогда граф зависимостей — это граф G = ( S , T ) {displaystyle G=(S,T)} где T ⊆ R {displaystyle Tsubseteq R} и R {displaystyle R} является транзитивным замыканием T {displaystyle T} .

Например, некоторый калькулятор поддерживает запись константы в некоторую переменную и сложение двух переменных с записью результата в некоторую третью переменную. Пусть дано несколько выражений, например, A = B + C ; B = 5 + D ; C = 4 ; D = 2 {displaystyle A=B+C;B=5+D;C=4;D=2} . Тогда S = A , B , C , D {displaystyle S={A,B,C,D}} и R = ( A , B ) , ( A , C ) , ( B , D ) {displaystyle R={(A,B),(A,C),(B,D)}} . Можно явно вывести все отношения: A {displaystyle A} зависит B {displaystyle B} и C {displaystyle C} , потому что две переменные можно складывать тогда и только тогда, когда известны значения обеих переменных. Таким образом, B {displaystyle B} и C {displaystyle C} должны быть вычислены перед A {displaystyle A} . Однако, значение D {displaystyle D} известно сразу, потому что это числовая константа.

Обнаружение невозможных вычислений

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

В примере на основе калькулятора, вычислительная система A = B ; B = D + C ; C = D + A ; D = 12 {displaystyle A=B;B=D+C;C=D+A;D=12} содержит циклическую зависимость. B {displaystyle B} должно быть вычислено до A {displaystyle A} , C {displaystyle C} должно быть вычислено до B {displaystyle B} , A {displaystyle A} должно быть вычислено до C {displaystyle C} .

Определение порядка вычислений

Корректный порядок вычислений — это нумерация n : S → N {displaystyle n:S ightarrow N} объектов, которая упорядочивает узлы графа зависимостей так, что имеет место равенство: n ( a ) < n ( b ) ⇒ ( a , b ) ∉ R {displaystyle n(a)<n(b)Rightarrow (a,b) otin R} , где a , b ∈ S {displaystyle a,bin S} . Это означает, что если нумераций определяется, что a {displaystyle a} вычисляется перед b {displaystyle b} , то a {displaystyle a} не может зависеть от b {displaystyle b} . Более того, может существовать более одного корректного порядка вычислений. По сути, корректная нумерация является топологической сортировкой, и любая топологическая сортировка является корректной нумерацией. На самом деле, любой алгоритм, производящий корректную топологическую сортировку, одновременно определяет корректный порядок вычисления.

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

Примеры

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

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

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

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

Имя:*
E-Mail:
Комментарий: