Может ли кто-нибудь объяснить мне простым языком, что такое ориентированный ациклический граф?

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

точки с линиями, указывающими на другие точки

граф = структура, состоящая из узлов, которые соединены друг с другом ребрами

направлено = соединения между узлами (ребрами) имеют направление: A -> B не то же самое, что B -> A

acyclic = "non-round" = перемещаясь от узла к узлу по ребрам, вы никогда не встретите один и тот же узел во второй раз.

Хорошим примером ориентированного ациклического графа является дерево. Обратите внимание, однако, что не все ориентированные ациклические графы являются деревьями.

Я вижу много ответов, указывающих на значение DAG (направленный ациклический граф), но нет ответов на его приложения. Вот очень простой -

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

Если бы был цикл, вы бы никогда не прошли курс: p

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

Мой профессор привел эту аналогию, и она лучше всего помогла мне понять DAG, а не использовать какую-то сложную концепцию!

Другой пример в реальном времени -> Пример в реальном времени того, как DAG можно использовать в системе версий

Примеры использования ориентированного ациклического графа в программировании включают в себя более или менее все, что представляет связность и причинность.

Например, предположим, что у вас есть конвейер вычислений, который можно настраивать во время выполнения. В качестве одного из примеров предположим, что вычисления A, B, C, D, E, F и G зависят друг от друга: A зависит от C, C зависит от E и F, B зависит от D и E, а D зависит от F. Это может быть представлено как DAG. Если у вас есть DAG в памяти, вы можете записывать алгоритмы в:

• убедитесь, что вычисления выполняются в правильном порядке ( топологическая сортировка )
• если вычисления могут выполняться параллельно, но каждое вычисление имеет максимальное время выполнения, вы можете вычислить максимальное время выполнения всего набора

среди прочего.

Вне области программирования приложений любой достойный инструмент автоматизированной сборки (make, ant, scons и т. Д.) Будет использовать DAG для обеспечения правильного порядка сборки компонентов программы.

В нескольких ответах приведены примеры использования графиков (например, сетевое моделирование), и вы спросили: «Какое отношение это имеет к программированию?».

Ответ на этот подвопрос заключается в том, что он не имеет ничего общего с программированием. Это связано с решением проблем.

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

Направленные ациклические графы (DAG) обладают следующими свойствами, которые отличают их от других графов:

1. Их края показывают направление.
2. У них нет циклов.

Что ж, сейчас я могу придумать одно использование - DAG (известный как Wait-For-Graphs - дополнительные технические подробности ) удобны при обнаружении взаимоблокировок, поскольку они иллюстрируют зависимости между набором процессов и ресурсов (оба являются узлами в DAG) . Тупик может произойти при обнаружении цикла.

Я полагаю, вы уже знаете основную терминологию графов; в противном случае вам следует начать со статьи по теории графов .

Режиссер относится к тому факту, что края (соединения) имеют направления. На схеме эти направления показаны стрелками. Противоположным является неориентированный граф, ребра которого не указывают направления.

Ациклический означает, что если вы начнете с любого произвольного узла X и пройдете через все возможные ребра, вы не сможете вернуться к X, не вернувшись на уже использованное ребро.

Несколько приложений:

• Таблицы; это объясняется в DAG статье .
• Контроль версий: если вы посмотрите на диаграмму на этой странице, вы увидите, что эволюция кода с контролем версий является направленным (на этой диаграмме он идет «вниз») и ациклическим (он никогда не возвращается «вверх») .
• Генеалогическое древо: направленное (вы ребенок своих родителей, а не наоборот) и ациклическое (ваши предки никогда не могут быть вашим потомком).

DAG - это граф, в котором все движется в одном направлении, и ни один узел не может ссылаться на себя.

Подумайте о деревьях предков; на самом деле они являются группами DAG.

Все группы DAG имеют

• Узлы (места для хранения данных)
• Направленные края (точки в одном направлении)
• Родовой узел (узел без родителей)
• Листья (узлы, у которых нет детей)

Группы DAG отличаются от деревьев. В древовидной структуре должен быть уникальный путь между каждыми двумя узлами. В группах DAG узел может иметь два родительских узла.

Вот хорошая статья о DAG . Надеюсь, это поможет.

Все виды графиков используются в программировании для моделирования различных отношений в реальном мире. Например, социальная сеть часто представлена ​​графом (в данном случае циклическим). Точно так же топологии сетей, родословные, маршруты авиакомпаний, ...

С точки зрения исходного кода или даже трехадресного кода (TAC) вы можете очень легко визуализировать проблему на этой странице ...

http://cgm.cs.mcgill.ca/~hagha/topic30/topic30.html#Exptree

Если вы перейдете к разделу дерева выражений, а затем немного потянете вниз, он покажет «топологическую сортировку» дерева и алгоритм оценки выражения.

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

Базовый алгоритм вычисления DAG на не древнем египетском (т.е. английском) языке таков:

1) Сделайте свой объект DAG таким

Вам нужен активный список, и этот список содержит все текущие активные узлы DAG и подвыражения DAG. Подвыражение DAG - это узел DAG, или его также можно назвать внутренним узлом. Под живым узлом DAG я подразумеваю то, что если вы присваиваете переменную X, она становится активной. Обычное подвыражение, которое затем использует X, использует этот экземпляр. Если X назначается снова, то создается НОВЫЙ УЗЕЛ DAG, который добавляется в текущий список, а старый X удаляется, поэтому следующее подвыражение, использующее X, будет ссылаться на новый экземпляр и, таким образом, не будет конфликтовать с подвыражениями, которые просто используйте то же имя переменной.

После того, как вы назначаете переменную X, случайно все узлы подвыражений DAG, которые активны в точке назначения, становятся неактивными, поскольку новое присвоение делает недействительным значение подвыражений с использованием старого значения.

class Dag {
  TList LiveList;
  DagNode Root;
}

// In your DagNode you need a way to refer to the original things that
// the DAG is computed from. In this case I just assume an integer index
// into the list of variables and also an integer index for the opertor for
// Nodes that refer to operators. Obviously you can create sub-classes for
// different kinds of Dag Nodes.
class DagNode {
  int Variable;
  int Operator;// You can also use a class
  DagNode Left;
  DagNode Right;
  DagNodeList Parents;
}

Итак, что вы делаете, это просматриваете свое дерево в собственном коде, например, в дереве выражений в исходном коде. Назовите существующие узлы, например, XNodes.

Итак, для каждого XNode вам нужно решить, как добавить его в DAG, и есть вероятность, что он уже находится в DAG.

Это очень простой псевдокод. Не предназначен для компиляции.

DagNode XNode::GetDagNode(Dag dag) {
  if (XNode.IsAssignment) {
    // The assignment is a special case. A common sub expression is not
    // formed by the assignment since it creates a new value.

    // Evaluate the right hand side like normal
    XNode.RightXNode.GetDagNode();  


    // And now take the variable being assigned to out of the current live list
    dag.RemoveDagNodeForVariable(XNode.VariableBeingAssigned);

    // Also remove all DAG sub expressions using the variable - since the new value
    // makes them redundant
    dag.RemoveDagExpressionsUsingVariable(XNode.VariableBeingAssigned);

    // Then make a new variable in the live list in the dag, so that references to
    // the variable later on will see the new dag node instead.
    dag.AddDagNodeForVariable(XNode.VariableBeingAssigned);

  }
  else if (XNode.IsVariable) {
    // A variable node has no child nodes, so you can just proces it directly
    DagNode n = dag.GetDagNodeForVariable(XNode.Variable));
    if (n) XNode.DagNode = n;
    else {
      XNode.DagNode = dag.CreateDagNodeForVariable(XNode.Variable);
    }
    return XNode.DagNode;
  }
  else if (XNode.IsOperator) {
    DagNode leftDagNode = XNode.LeftXNode.GetDagNode(dag);
    DagNode rightDagNode = XNode.RightXNode.GetDagNode(dag);


    // Here you can observe how supplying the operator id and both operands that it
    // looks in the Dags live list to check if this expression is already there. If
    // it is then it returns it and that is how a common sub-expression is formed.
    // This is called an internal node.
    XNode.DagNode = 
      dag.GetOrCreateDagNodeForOperator(XNode.Operator,leftDagNode,RightDagNode) );

    return XNode.DagNode;
  }
}

Так что это один из способов взглянуть на это. Базовый обход дерева и простое добавление и обращение к узлам Dag по мере его продвижения. Корнем dag является то, что, например, DagNode возвращает корень дерева.

Очевидно, процедура примера может быть разбита на более мелкие части или сделана как подклассы с виртуальными функциями.

Что касается сортировки Dag, вы просматриваете каждый DagNode слева направо. Другими словами, следуйте за левым краем DagNodes, а затем за правым краем. Номера присваиваются в обратном порядке. Другими словами, когда вы достигнете DagNode без дочерних узлов, присвойте этому узлу текущий номер сортировки и увеличьте номер сортировки, чтобы рекурсия раскрутила номера, назначенные в порядке возрастания.

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

// Most basic DAG topological ordering example.
void DagNode::OrderDAG(int* counter) {
  if (this->AlreadyCounted) return;

  // Count from left to right
  for x = 0 to this->Children.Count-1
    this->Children[x].OrderDag(counter)

  // And finally number the DAG Node here after all
  // the children have been numbered
  this->DAGOrder = *counter;

  // Increment the counter so the caller gets a higher number
  *counter = *counter + 1;

  // Mark as processed so will count again
  this->AlreadyCounted = TRUE;
}

Если вы знаете, какие деревья используются в программировании, то группы DAG в программировании похожи, но позволяют узлу иметь более одного родителя. Это может быть удобно, если вы хотите, чтобы узел был сгруппирован не только под одним родителем, но при этом не возникает проблем, связанных с беспорядком в общем графике с циклами. Вы по-прежнему можете легко перемещаться по DAG, но есть несколько способов вернуться к корню (потому что может быть более одного родителя). Один DAG обычно может иметь несколько корней, но на практике может быть лучше просто придерживаться одного корня, например дерева. Если вы разбираетесь в одиночном и множественном наследовании в ООП, то вы знаете, что дерево и DAG. Я уже ответил на это здесь .

Название сообщает вам большую часть того, что вам нужно знать о его определении: это граф, каждое ребро которого течет только в одном направлении, и как только вы сползете вниз по ребру, ваш путь никогда не вернет вас в вершину, которую вы только что оставили.

Я не могу говорить обо всех случаях использования (в этом помогает Википедия), но для меня DAG чрезвычайно полезны при определении зависимостей между ресурсами. Мой игровой движок, например, представляет все загруженные ресурсы (материалы, текстуры, шейдеры, открытый текст, проанализированный json и т. Д.) Как один DAG. Пример:

Материал - это N GL программ, для каждой из которых требуется два шейдера, а для каждого шейдера требуется исходный текст шейдера. Представляя эти ресурсы в виде группы доступности базы данных, я могу легко запрашивать у графика существующие ресурсы, чтобы избежать дублирующих нагрузок. Допустим, вы хотите, чтобы в нескольких материалах использовались вершинные шейдеры с одним и тем же исходным кодом. Бесполезно перезагружать исходный код и перекомпилировать шейдеры для каждого использования, если вы можете просто создать новое преимущество для существующего ресурса. Таким образом, вы также можете использовать график, чтобы определить, зависит ли что-либо от ресурса вообще, а если нет, удалите его и освободите его память, на самом деле это происходит в значительной степени автоматически.

В более широком смысле, группы DAG полезны для выражения конвейеров обработки данных. Ациклический характер означает, что вы можете безопасно написать код контекстной обработки, который может следовать за указателями вниз по ребрам от вершины, никогда не встречаясь повторно с той же вершиной. Все языки визуального программирования, такие как VVVV , Max MSP или интерфейсы на основе узлов Autodesk Maya, полагаются на группы DAG.

Направленный ациклический граф полезен, когда вы хотите представить ... ориентированный ациклический граф! Канонический пример - генеалогическое древо или генеалогия.