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

редактировать

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

Содержание

1 Определение
2 Распознавание невозможных оценок
3 Получение порядка оценки
4 Примеры
5 См. Также
6 Ссылки

Определение

Для данного набора объектов $S {\ displaystyle S}$ $S$ и транзитивное отношение $R ⊆ S × S {\ displaystyle R \ substeq S \ times S}$ $R \ substeq S \ times S$ с $(a, b) ∈ R {\ displaystyle (a, b) \ in R}$ $(a, б) \ в R$ моделирование зависимости «a зависит от b» («a сначала нужно оценить b»), граф зависимостей - это граф $G = (S, T) {\ displaystyle G = (S, T)}$ $G = (S, T)$ с $T ⊆ R {\ displaystyle T \ substeq R}$ $T \ substeq R$ и T является переходным сокращением R.

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

Распознавание невозможных оценок

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

Предположим, простой калькулятор из прошлого. Система уравнений «A = B; B = D + C; C = D + A; D = 12;» содержит циклическую зависимость, образованную A, B и C, так как B должен быть оценен до A, C должен быть оценен до B, а A должен быть оценен до C.

Получение порядка оценки

A правильный порядок оценки - это нумерация $n: S → N {\ displaystyle n: S \ rightarrow \ mathbb {N}}$ $n: S \ rightarrow {\ mathbb {N}}$ объектов, образующих узлы зависимости. график так, чтобы выполнялось следующее уравнение: $n (a) < n ( b) ⇒ ( a, b) ∉ R {\displaystyle n(a)$ $n (a) <n (b) \ Rightarrow (a, b) \ notin R$ с $a, b ∈ S {\ displaystyle a, b \ in S}$ $a, b \ в S$ . Это означает, что если нумерация упорядочивает два элемента $a {\ displaystyle a}$ $a$ и $b {\ displaystyle b}$ $b$ так, чтобы $a {\ displaystyle a }$ $a$ будет оцениваться до $b {\ displaystyle b}$ $b$ , тогда $a {\ displaystyle a}$ $a$ не должен зависеть от $b {\ displaystyle b}$ $b$ .

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

Снова представьте себе простой калькулятор сверху. Учитывая систему уравнений «A = B + C; B = 5 + D; C = 4; D = 2;», правильным порядком оценки будет (D, C, B, A). Однако (C, D, B, A) также является правильным порядком оценки.

Примеры

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

автоматическом программном обеспечении установщиках : они просматривают граф в поисках пакетов программного обеспечения, которые необходимы, но еще не установлен. Зависимость задается связью пакетов.
Скрипты сборки программного обеспечения, такие как Unix Make, Node npm install, php composer, Twitter bower install или Apache Ant. Им необходимо знать, какие файлы были изменены, поэтому необходимо перекомпилировать только правильные файлы.
В технологии компилятора и реализации формального языка :
- Планирование инструкций : Графы зависимостей вычисляются для операндов сборки или промежуточных инструкций и используются для определения оптимального порядка для инструкций.
- Устранение мертвого кода : Если никакая побочная операция не зависит от переменная, эта переменная считается неработающей и может быть удалена.
Аналитика динамического графика: GraphBolt и KickStarter захватывают зависимости значений для инкрементных вычислений при изменении структуры графика.
Электронные таблицы калькуляторы. Им необходимо получить правильный порядок вычислений, аналогичный тому, который приведен в примере, использованном в этой статье.
Стандарты веб-форм, такие как XForms, чтобы знать, какие визуальные элементы обновлять, если данные в модели
Видеоигры, особенно головоломки и приключенческие видеоигры, которые часто представляют собой граф зависимых отношений между внутриигровыми действиями.

Зависимость графики являются одним из аспектов:

Типы производственных предприятий : сырье перерабатывается в продукты через несколько зависимых стадий.
Планирование рабочих мест : собрание связанных теоретических проблем в области информатики.

См. Также

Ссылки

Balmas, Francoise (2001) Отображение графиков зависимости: иерархический подход, [1] wcre, стр. 261, Восьмая рабочая конференция по обратному инжинирингу (WCRE'01)