¿Alguien puede explicarme en términos simples qué es un gráfico acíclico dirigido?

¿Alguien puede explicarme en términos simples qué es un gráfico acíclico dirigido? He buscado en Wikipedia pero realmente no me hace ver su uso en programación.

puntos con líneas que apuntan a otros puntos

grafo = estructura que consta de nodos, que están conectados entre sí con bordes

dirigido = las conexiones entre los nodos (bordes) tienen una dirección: A -> B no es lo mismo que B -> A

acyclic = "no circular" = moviéndose de un nodo a otro siguiendo los bordes, nunca encontrará el mismo nodo por segunda vez.

Un buen ejemplo de un gráfico acíclico dirigido es un árbol. Sin embargo, tenga en cuenta que no todos los gráficos acíclicos dirigidos son árboles.

Veo muchas respuestas que indican el significado de DAG (gráfico acíclico dirigido) pero no respuestas sobre sus aplicaciones. Aquí hay uno muy simple:

Gráfico de requisitos previos : durante un curso de ingeniería, cada estudiante se enfrenta a la tarea de elegir asignaturas que siguen requisitos, como los requisitos previos. Ahora está claro que no se puede tomar una clase de Inteligencia Artificial [B] sin un curso previo de Algoritmos [A]. Por lo tanto, B depende de A o, en mejores términos, A tiene una ventaja dirigida a B. Entonces, para llegar al Nodo B, debe visitar el Nodo A. Pronto estará claro que después de agregar todos los sujetos con sus prerrequisitos en un gráfico , resultará ser un gráfico acíclico dirigido.

Si hubiera un ciclo, nunca completarías un curso: p

Un sistema de software en la universidad que permite a los estudiantes inscribirse en los cursos puede modelar las materias como nodos para asegurarse de que el estudiante haya tomado un curso de prerrequisito antes de inscribirse en el curso actual.

¡Mi profesor dio esta analogía y me ha ayudado mejor a entender DAG en lugar de usar un concepto complicado!

Otro ejemplo en tiempo real -> Ejemplo en tiempo real de cómo se pueden usar los DAG en el sistema de versiones

Los ejemplos de usos de un gráfico acíclico dirigido en programación incluyen más o menos cualquier cosa que represente conectividad y causalidad.

Por ejemplo, suponga que tiene una canalización de cálculo que se puede configurar en tiempo de ejecución. Como ejemplo de esto, suponga que los cálculos A, B, C, D, E, F y G dependen entre sí: A depende de C, C depende de E y F, B depende de D y E, y D depende de F. Esto se puede representar como un DAG. Una vez que tenga el DAG en la memoria, puede escribir algoritmos para:

• asegúrese de que los cálculos se evalúen en el orden correcto ( clasificación topológica )
• Si los cálculos se pueden realizar en paralelo pero cada cálculo tiene un tiempo máximo de ejecución, puede calcular el tiempo máximo de ejecución de todo el conjunto.

entre muchas otras cosas.

Fuera del ámbito de la programación de aplicaciones, cualquier herramienta de compilación automatizada decente (make, ant, scons, etc.) utilizará DAG para garantizar el orden de compilación adecuado de los componentes de un programa.

Varias respuestas han dado ejemplos del uso de gráficos (por ejemplo, modelado de redes) y ha preguntado "¿qué tiene esto que ver con la programación?".

La respuesta a esa subpregunta es que no tiene mucho que ver con la programación. Tiene que ver con la resolución de problemas.

Al igual que las listas enlazadas son estructuras de datos que se utilizan para determinadas clases de problemas, los gráficos son útiles para representar determinadas relaciones. Las listas vinculadas, los árboles, los gráficos y otras estructuras abstractas solo tienen una conexión con la programación, ya que puede implementarlas en el código. Existen en un nivel superior de abstracción. No se trata de programar, se trata de aplicar estructuras de datos en la solución de problemas.

Los gráficos acíclicos dirigidos (DAG) tienen las siguientes propiedades que los distinguen de otros gráficos:

1. Sus bordes muestran la dirección.
2. No tienen ciclos.

Bueno, puedo pensar en un uso en este momento: DAG (conocido como Wait-For-Graphs , más detalles técnicos ) son útiles para detectar interbloqueos, ya que ilustran las dependencias entre un conjunto de procesos y recursos (ambos son nodos en el DAG) . El punto muerto se produciría cuando se detecta un ciclo.

Supongo que ya conoce la terminología básica de gráficos; de lo contrario, debería empezar por el artículo sobre teoría de grafos .

Dirigido se refiere al hecho de que los bordes (conexiones) tienen direcciones. En el diagrama, estas direcciones se muestran mediante flechas. Lo contrario es un gráfico no dirigido, cuyos bordes no especifican direcciones.

Acíclico significa que, si comienza desde cualquier nodo X arbitrario y recorre todos los bordes posibles, no puede volver a X sin volver a un borde ya utilizado.

Varias aplicaciones:

• Hojas de cálculo; esto se explica en el artículo de DAG .
• Control de revisión : si echas un vistazo al diagrama en esa página, verás que la evolución del código controlado por revisión es dirigida (va "hacia abajo", en este diagrama) y acíclica (nunca vuelve "hacia arriba") .
• Árbol genealógico: está dirigido (eres hijo de tus padres, no al revés) y acíclico (tus antepasados ​​nunca pueden ser tus descendientes).

Un DAG es un gráfico en el que todo fluye en la misma dirección y ningún nodo puede hacer referencia a sí mismo.

Piense en árboles de ascendencia; en realidad son DAG.

Todos los DAG tienen

• Nodos (lugares para almacenar datos)
• Bordes dirigidos (que apuntan en la misma dirección)
• Un nodo ancestral (un nodo sin padres)
• Hojas (nodos que no tienen hijos)

Los DAG son diferentes a los árboles. En una estructura en forma de árbol, debe haber una ruta única entre cada dos nodos. En los DAG, un nodo puede tener dos nodos principales.

Aquí hay un buen artículo sobre los DAG . Espero que eso ayude.

Los gráficos, de todo tipo, se utilizan en la programación para modelar varias relaciones diferentes del mundo real. Por ejemplo, una red social a menudo se representa mediante un gráfico (cíclico en este caso). Asimismo, topologías de red, árboles genealógicos, rutas aéreas, ...

Desde la perspectiva del código fuente o incluso del código de tres direcciones (TAC), puede visualizar el problema con mucha facilidad en esta página ...

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

Si va a la sección del árbol de expresiones y luego avanza un poco la página, se muestra la "clasificación topológica" del árbol y el algoritmo de cómo evaluar la expresión.

Entonces, en ese caso, puede usar el DAG para evaluar expresiones, lo cual es útil ya que la evaluación normalmente se interpreta y el uso de dicho evaluador DAG hará que los intérpretes simples sean más rápidos en principio porque no está empujando y saliendo a una pila y también porque está eliminando sub-expresiones comunes.

El algoritmo básico para calcular el DAG en egipcio no antiguo (es decir, inglés) es este:

1) Haga su objeto DAG así

Necesita una lista en vivo y esta lista contiene todos los nodos y sub-expresiones de DAG en vivo actuales. Una subexpresión DAG es un nodo DAG, o también puede llamarlo nodo interno. Lo que quiero decir con Nodo DAG en vivo es que si asigna a una variable X, se convierte en vivo. Una subexpresión común que luego usa X usa esa instancia. Si se vuelve a asignar X, se crea un NUEVO NODO DAG y se agrega a la lista en vivo y se elimina la X anterior, por lo que la siguiente subexpresión que usa X se referirá a la nueva instancia y, por lo tanto, no entrará en conflicto con las subexpresiones que simplemente use el mismo nombre de variable.

Una vez que asigna a una variable X, casualmente todos los nodos de subexpresión DAG que están activos en el punto de asignación se vuelven inactivos, ya que la nueva asignación invalida el significado de las subexpresiones que utilizan el valor anterior.

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;
}

Entonces, lo que hace es recorrer su árbol en su propio código, como un árbol de expresiones en el código fuente, por ejemplo. Llame a los nodos existentes XNodes, por ejemplo.

Entonces, para cada XNode, debe decidir cómo agregarlo al DAG, y existe la posibilidad de que ya esté en el DAG.

Este es un pseudocódigo muy simple. No destinado a la compilación.

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;
  }
}

Así que esa es una forma de verlo. Una caminata básica del árbol y simplemente agregando y refiriéndose a los nodos Dag a medida que avanza. La raíz del dag es cualquier DagNode que devuelva la raíz del árbol, por ejemplo.

Obviamente, el procedimiento de ejemplo puede dividirse en partes más pequeñas o crearse como subclases con funciones virtuales.

En cuanto a clasificar el Dag, recorre cada DagNode de izquierda a derecha. En otras palabras, siga el borde izquierdo de DagNodes y luego el borde derecho. Los números se asignan al revés. En otras palabras, cuando llegue a un DagNode sin hijos, asigne a ese Nodo el número de clasificación actual e incremente el número de clasificación, de modo que a medida que la recursividad se deshaga, los números se asignan en orden creciente.

Este ejemplo solo maneja árboles con nodos que tienen cero o dos hijos. Obviamente, algunos árboles tienen nodos con más de dos hijos, por lo que la lógica sigue siendo la misma. En lugar de calcular de izquierda a derecha, calcula de izquierda a derecha, etc.

// 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;
}

Si sabe qué árboles hay en programación, entonces los DAG en programación son similares pero permiten que un nodo tenga más de un padre. Esto puede ser útil cuando desea permitir que un nodo se agrupe debajo de más de un solo padre, pero no tiene el problema de un lío anudado de un gráfico general con ciclos. Aún puede navegar por un DAG fácilmente, pero hay varias formas de volver a la raíz (porque puede haber más de un padre). En general, un solo DAG podría tener múltiples raíces, pero en la práctica puede ser mejor quedarse solo con una raíz, como un árbol. Si comprende la herencia única frente a la herencia múltiple en OOP, entonces conoce el árbol frente a DAG. Ya respondí esto aquí .

El nombre le dice la mayor parte de lo que necesita saber sobre su definición: es un gráfico en el que cada borde solo fluye en una dirección y una vez que se arrastra por un borde, su camino nunca lo regresará al vértice que acaba de dejar.

No puedo hablar de todos los usos (Wikipedia ayuda allí), pero para mí, los DAG son extremadamente útiles para determinar las dependencias entre los recursos. Mi motor de juego, por ejemplo, representa todos los recursos cargados (materiales, texturas, sombreadores, texto plano, json analizado, etc.) como un solo DAG. Ejemplo:

Un material son los programas N GL, cada uno de los cuales necesita dos sombreadores, y cada sombreador necesita una fuente de sombreado de texto plano. Al representar estos recursos como un DAG, puedo consultar fácilmente en el gráfico los recursos existentes para evitar cargas duplicadas. Supongamos que desea que varios materiales usen sombreadores de vértices con el mismo código fuente. Es un desperdicio volver a cargar la fuente y volver a compilar los sombreadores para cada uso cuando simplemente puede establecer una nueva ventaja para el recurso existente. De esta manera, también puede usar el gráfico para determinar si algo depende de un recurso, y si no, eliminarlo y liberar su memoria, de hecho, esto sucede de manera casi automática.

Por extensión, los DAG son útiles para expresar canales de procesamiento de datos. La naturaleza acíclica significa que puede escribir de forma segura código de procesamiento contextual que puede seguir los punteros por los bordes desde un vértice sin volver a encontrarse con el mismo vértice. Los lenguajes de programación visual como VVVV , Max MSP o las interfaces basadas en nodos de Autodesk Maya dependen de los DAG.

Un gráfico acíclico dirigido es útil cuando desea representar ... ¡un gráfico acíclico dirigido! El ejemplo canónico es un árbol genealógico o una genealogía.