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

Направленный граф, представляющий зависимости

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

Определение

A зависит от B и C ; B зависит от D

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

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

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

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

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

Вывод порядка оценки

Правильный порядок оценки — это нумерация объектов, образующих узлы графа зависимостей, так что выполняется следующее уравнение: с . Это означает, что если нумерация упорядочивает два элемента и так, что будет оценено до , то не должно зависеть от . ${\displaystyle n:S\rightarrow \mathbb {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}$ ${\displaystyle b}$

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

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

Моноидная структура

Ациклический граф зависимостей соответствует трассе моноида трассы следующим образом: ^{[1] : 12}

• Функция помечает каждую вершину символом из алфавита ${\displaystyle \phi :S\to \Sigma }$ ${\displaystyle \Sigma }$
• Ребро существует тогда и только тогда, когда находится в отношении зависимости . ${\displaystyle a\to b}$ ${\displaystyle b\to a}$ ${\displaystyle (\phi (a),\phi (b))}$ ${\displaystyle D}$
• Два графа считаются равными, если их метки и ребра совпадают.

Тогда строка, состоящая из меток вершин, упорядоченных в правильном порядке оценки, соответствует строке трассы.

Моноидальная операция берет несвязное объединение множеств вершин двух графов, сохраняет существующие ребра в каждом графе и рисует новые ребра от первого ко второму, где это позволяет отношение зависимости, ^{[1] : 14} ${\displaystyle (S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})}$ ${\displaystyle S_{12}=S_{1}\sqcup S_{2}}$

${\displaystyle R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b))\in D\}}$

Идентичность — пустой граф.

Примеры

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

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

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

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

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

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

Ссылки

1. Mazurkiewicz, Antoni (1995). "Введение в теорию следов" (PDF) . В Rozenberg, G.; Diekert, V. (ред.). Книга следов . Singapore: World Scientific. ISBN 981-02-2058-8. Получено 18 апреля 2021 г. .
2. Мугилан Мариаппан; Кевал Вора (2019). «GraphBolt: синхронная обработка потоковых графов на основе зависимостей». На Европейской конференции по компьютерным системам (EuroSys'19) . стр. 25:1–25:16. doi :10.1145/3302424.3303974.
3. Кевал Вора; Раджив Гупта; Гоцин Сюй (2017). «KickStarter: быстрые и точные вычисления на потоковых графах с помощью урезанных аппроксимаций». В Международной конференции по архитектурной поддержке языков программирования и операционных систем (ASPLOS'17) . стр. 237–251. doi : 10.1145/3093337.3037748 .
4. Гилберт, Рон. «Схемы зависимости головоломок». Grumpy Gamer . Получено 11 января 2020 г.

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