что такое ациклический граф
Продвинутые структуры данных. Часть первая: Направленный ациклический граф
Всем привет! Уже на следующей неделе стартуют занятия в новой группе курса «Алгоритмы для разработчиков». В связи с этим, делимся с вами переводом совсем небольшого, но довольно интересного материала.
Я хотел начать эту серию статей со структуры данных, с которой все мы как разработчики, хорошо знакомы, но вполне возможно, что даже не представляем как она устроена.
«Направленный ациклический граф? Никогда об этом не слышал. Не думай, что все обо мне знаешь!», вы можете сказать, но именно этот граф делает возможным контроль версий. Да, Git представляет из себя ациклический граф. В этой статье я поделюсь с вами знаниями о направленных ациклических графах (Directed Acyclic Graphs, DAG), а затем покажу, как написать свой собственный.
Что такое DAG?
Так что это вообще значит? DAG – это однонаправленный граф, где ни один элемент не может считаться дочерним. Многие из нас знакомы со связными списками, деревьями и графами. DAG очень похож на первое и второе в реализации третьего.
Выглядит похоже на дерево, но не совсем
В самом минимальном виде у DAG есть 4 составляющих:
А теперь попишем код. Сначала создадим конструктор с двумя свойствами и назовем его DAG.
Создадим метод для добавления узлов. Видите, что я здесь сделал?
Как это работает? Объект vertex – это место, где происходит вся магия. Мы добавляем узел, объект с поступающими узлами и массив со всеми их именами, переменную типа Boolean, сигнализирующую о том, указывает ли узел на что-то или нет, и его значение. К этому мы перейдем попозже.
Пора отдать должное
Пока я изучал материалы для написания этой статьи, я прочел несколько замечательных сообщений от удивительно умных людей, и в итоге большая часть информации была получена от них. Часть теоретической информации я получил, изучив этот хорошо структурированный пост о DAG и контроле версий. Код, представленный здесь, вдохновлен исходниками emberjs и их авторами. А еще я многое почерпнул из других статей и сообщений о DAG в блогах множества великих людей.
Может ли кто-нибудь объяснить мне простыми словами, Что такое направленный ациклический граф?
может ли кто-нибудь объяснить мне в простых терминах, что такое направленный ациклический граф? Я посмотрел на Википедию, но это не заставляет меня видеть ее использование в программировании.
13 ответов
точки с линиями, указывающими на другие точки
graph = структура, состоящая из узлов, которые соединены друг с другом ребрами
acyclic = «non-circular» = перемещение от узла к узлу, следуя ребрам, вы никогда не встретите один и тот же узел во второй раз.
хорошим примером направленного ациклического графа является дерево. Обратите внимание, однако, что не все направленные ациклические графики деревья.
Если бы был цикл, то вы никогда не закончили бы курс: p
программная система в университете, которая позволяет студентам регистрироваться на курсы, может моделировать предметы как узлы, чтобы убедиться, что студент принял обязательный курс перед регистрацией на текущий курс.
мой профессор дал эту аналогию, и это лучше всего помогло мне понять DAG, а не использовать какую-то сложную концепцию!
пример использования направленного ациклического графа в программировании включает более или менее все, что представляет связность и причинность.
например, предположим, что у вас есть конвейер вычислений, который настраивается во время выполнения. В качестве одного из примеров этого предположим, что вычисления A,B,C,D,E, F и G зависят друг от друга: A зависит от C, C зависит от E и F, B зависит от D и E, А D зависит от F. Это можно представить как DAG. Как только у вас есть DAG в памяти, вы можете написать алгоритмы для:
среди многих других вещей.
за пределами области прикладного программирования, любой достойный автоматизированный инструмент сборки (make, ant, scons и т. д.) будет использовать DAGs для обеспечить правильный порядок построения компонентов программы.
несколько ответов дали примеры использования графиков (например, сетевое моделирование), и вы спросили: «какое это имеет отношение к программированию?».
ответ на этот подвопрос, что он не имеет ничего общего с программированием. Это связано с решением проблем.
Так же, как связанные списки-это структуры данных, используемые для определенных классов проблем, графики полезны для представления определенных отношений. Связанные списки, деревья, графики и другие абстрактные структуры связаны с программированием только тем, что вы можете реализовать их в коде. Они существуют на более высоком уровне абстракции. Речь идет не о программировании, а о применении структур данных при решении задач.
направленные ациклические графы (DAG) имеют следующие свойства, которые отличают их от других графов:
надеюсь, это поможет.
Я предполагаю, что вы уже знаете основную терминологию графа; в противном случае вы должны начать со статьи о теория графов.
направлено относится к тому, что ребра (соединения)имеют направления. На диаграмме эти направления показаны стрелками. Противоположностью является неориентированный граф, ребра которого не указывают направления.
ациклические означает, что если вы начинаете с любого произвольного узла X и проходите через все возможные ребра, вы не можете вернуться к X, не возвращаясь к уже используемому краю.
графики, всех видов, используются в программировании для моделирования различных реальных отношений. Например, социальная сеть часто представлена графом (в данном случае циклическим). Аналогично, сетевые топологии, генеалогические древа, маршруты авиакомпаний.
DAG-это график, где все течет в одном направлении, и ни один узел не может ссылаться на себя.
подумайте о деревьях предков; они на самом деле Даги.
DAG отличаются от деревья. В древовидной структуре между каждыми двумя узлами должен быть уникальный путь. В DAG узел может иметь два родительских узла.
здесь хорошая статья о DAGs. Надеюсь, это поможет.
С точки зрения исходного кода или даже трех адресов(TAC) вы можете легко визуализировать проблему на этой странице.
Если вы перейдете в раздел дерева выражений, а затем немного вниз, он покажет «топологическую сортировку» дерева и алгоритм оценки выражения.
поэтому в этом случае вы можете использовать DAG для оценки выражений, которые удобно, поскольку оценка обычно интерпретируется и использование такого оценщика DAG сделает простые intrepreters быстрее в принципе, потому что он не толкает и не выскакивает в стек, а также потому, что он устраняет общие под-выражения.
основной алгоритм вычисления DAG в не древнеегипетском (то есть английском) заключается в следующем:
1) Сделайте свой объект DAG таким
вам нужен живой список, и этот список содержит все текущие узлы Live DAG и DAG под-выражения. Суб-выражение DAG является узлом DAG, или его можно также назвать внутренним узлом. Что я имею в виду под Live DAG Node, так это то, что если вы назначаете переменной X, то она становится живой. Общее подвыражение, которое затем использует X использует этот экземпляр. Если X назначается снова, то новый узел DAG создается и добавляется в живой список, а старый X удаляется, поэтому следующее под-выражение, которое использует X, будет ссылаться на новый экземпляр и, таким образом, не будет конфликтовать с под-выражениями, которые просто используют то же самое имя переменной.
как только вы назначаете переменной X, то, кстати, все узлы под-выражения DAG, которые живут в точке назначения, становятся не-живыми, так как новое назначение аннулирует значение под-выражений, используя старое значение.
Итак, вы проходите через свое дерево в своем собственном коде, например, дерево выражений в исходном коде. Назвать существующие узлы прямо к примеру.
поэтому для каждого XNode вам нужно чтобы решить, как добавить его в DAG, и есть вероятность, что он уже находится в DAG.
Это очень простой псевдокод. Не предназначен для компиляции.
Так что это один из способов взглянуть на это. Базовая прогулка по дереву и просто добавление и ссылка на узлы Dag по мере его прохождения. Корень dag-это любой DagNode, который возвращает корень дерева, например.
пример процедуры могут быть разбиты на более мелкие части или сделано как подклассы с виртуальными функциями.
что касается сортировки Dag, вы проходите через каждый DagNode слева направо. Другими словами следуйте DagNodes левой, а затем правой боковой грани. Номера назначаются в обратном порядке. Другими словами, когда вы достигаете DagNode без дочерних узлов, назначьте этому узлу текущий номер сортировки и увеличьте номер сортировки, так как рекурсия разматывает числа, назначенные в порядке увеличения.
в этом примере обрабатывает только деревья с узлами, имеющими ноль или два дочерних элемента. Очевидно, что некоторые деревья имеют узлы с более чем двумя дочерними элементами, поэтому логика все та же. Вместо того, чтобы вычислять слева и справа, вычисляйте слева направо и т. д.
Если вы знаете, какие деревья в программировании, то DAG в программировании похожи, но они позволяют узлу иметь более одного родителя. Это может быть удобно, когда вы хотите, чтобы узел был сгруппирован под более чем одним родителем, но не имел проблемы узловатой путаницы общего графика с циклами. Вы все еще можете легко перемещаться по DAG, но есть несколько способов вернуться к корню (потому что может быть более одного родителя). Один DAG может иметь несколько корней но на практике может быть лучше просто придерживаться одного корня, как дерево. Если вы понимаете одно-и множественное наследование в ООП, то вы знаете дерево против DAG. Я уже ответил на это здесь.
имя говорит вам большую часть того, что вам нужно знать о его определении: это график, где каждое ребро течет только в одном направлении, и как только вы ползете по краю, ваш путь никогда не вернет вас в вершину, которую вы только что покинули.
Я не могу говорить со всеми видами использования (Википедия помогает там), но для меня DAG чрезвычайно полезны при определении зависимостей между ресурсами. Например, мой игровой движок представляет все загруженные ресурсы (материалы, текстуры, шейдеры, открытый текст, анализ json и т. д.) Как один DAG. Пример:
материал-это N GL-программ, для каждой из которых требуется два шейдера, и каждому шейдеру нужен источник шейдера с открытым текстом. Представляя эти ресурсы как DAG, я могу легко запросить график для существующих ресурсов, чтобы избежать повторяющихся нагрузок. Скажем, вы хотите, чтобы несколько материалов использовали вершинные шейдеры с одним исходным кодом. Бесполезно перезагружать источник и перекомпилировать шейдеры для каждого использования, когда вы можете просто установить новое ребро к существующему ресурс. Таким образом, вы также можете использовать график, чтобы определить, зависит ли что-либо от ресурса вообще, а если нет, удалите его и освободите его память, на самом деле это происходит почти автоматически.
по расширению, DAG полезны для выражения конвейеров обработки данных. Ациклическая природа означает, что вы можете безопасно писать код контекстной обработки, который может следовать указателям вниз по ребрам от вершины, никогда не перестраивая одну и ту же вершину. Визуальные языки программирования, такие как ПППП, Макс MSP или интерфейсы Autodesk Maya на основе узлов все полагаются на DAG.