График зависимости - Dependency graph

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

Определение

Учитывая набор объектов ${displaystyle S}$ и переходное отношение ${displaystyle Rsubseteq S imes S}$ с ${displaystyle (a,b)in R}$ моделирование зависимости "а зависит от б" ("а потребности б оценивается первым "), график зависимостей является графиком ${displaystyle G=(S,T)}$ с ${displaystyle Tsubseteq R}$ и Т будучи переходная редукция из р.

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

Признание невозможных оценок

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

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

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

А правильный порядок оценки это нумерация ${displaystyle n:Sightarrow mathbb {N} }$ объектов, которые образуют узлы графа зависимостей, так что выполняется следующее уравнение: ${displaystyle n(a)<n(b)Rightarrow (a,b)otin R}$ с ${displaystyle a,bin S}$. Это означает, что если нумерация упорядочивает два элемента ${displaystyle a}$ и ${displaystyle b}$ так что ${displaystyle a}$ будет оцениваться до ${displaystyle b}$, тогда ${displaystyle a}$ не должен зависеть от ${displaystyle b}$.

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

Предположим еще раз простой калькулятор сверху. Учитывая систему уравнений "А = B+C; B = 5+D; C=4; D= 2; ", правильный порядок оценки будет (D, C, B, А). Тем не мение, (C, D, B, А) также является правильным порядком оценки.

Примеры

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

• Автоматизированное программное обеспечение установщики: Они ходят по графику в поисках программные пакеты которые необходимы, но еще не установлены. Зависимость задается связь пакетов.
• Скрипты сборки программного обеспечения, такие как Unix Делать, Узел npm install, php composer, Twitter установка беседки, или Apache Ant. Им необходимо знать, какие файлы были изменены, поэтому необходимо перекомпилировать только правильные файлы.
• В компилятор технологии и формальный язык выполнение:
  • Планирование инструкций: Графы зависимостей вычисляются для операндов сборка или промежуточные инструкции и используются для определения оптимального порядка выполнения инструкций.
  • Устранение мертвого кода: Если никакая побочная операция не зависит от переменной, эта переменная считается мертвой и может быть удалена.
• Аналитика динамических графиков: GraphBolt^[1] и KickStarter^[2] фиксировать зависимости значений для инкрементальные вычисления при изменении структуры графа.
• Таблица калькуляторы. Им необходимо получить правильный порядок вычислений, аналогичный тому, который приведен в примере, использованном в этой статье.
• Стандарты веб-форм, такие как XForms чтобы знать, какие визуальные элементы обновлять при изменении данных в модели.
• Видеоигры, особенно головоломка и приключенческие видеоигры, которые часто представляют собой граф зависимых отношений между действиями в игре.^[3]

Графики зависимостей - это один из аспектов:

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

Смотрите также

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

Рекомендации

1. Мугилан Мариаппан; Кеваль Вора (2019). «GraphBolt: управляемая зависимостями синхронная обработка потоковых графов». На европейской конференции по компьютерным системам (EuroSys'19). С. 25: 1–25: 16. Дои:10.1145/3302424.3303974.
2. Кеваль Вора; Раджив Гупта; Гуоцин Сюй (2017). «KickStarter: быстрые и точные вычисления потоковых графиков с помощью усеченных приближений». В Международной конференции по архитектурной поддержке языков программирования и операционных систем (ASPLOS'17). С. 237–251. Дои:10.1145/3093337.3037748.
3. Гилберт, Рон. «Диаграммы зависимости головоломки». Сварливый геймер. Получено 11 января 2020.

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