directed acyclic graphs - que - ¿Puede alguien explicarme en términos simples qué es un gráfico acíclico dirigido?

notacion de grafos

Question

¿Puede alguien 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 la programación.

Answer 1

puntos con líneas que apuntan a otros puntos

Answer 2

Desde un código fuente o incluso una perspectiva de código de tres direcciones (TAC), puede visualizar el problema muy fácilmente 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 baja un poco la página, 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, que es útil ya que la evaluación normalmente se interpreta y el uso de dicho evaluador DAG hará que los interpretes simples sean más rápidos en principal porque no está presionando y apareciendo en una pila y también porque está eliminando subexpresiones comunes.

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

1) Haga su objeto DAG como tal

Necesita una lista en vivo y esta lista contiene todos los nodos DAG activos actuales y las subexpresiones DAG. Una subexpresión DAG es un nodo DAG, o también puede llamarlo un nodo interno. Lo que quiero decir con Live DAG Node es que si asignas una variable X entonces se convierte en vivo. Una sub-expresión común que luego usa X usa esa instancia. Si X se asigna de nuevo, se crea un NUEVO DAG NODE y se agrega a la lista activa 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 sub expresiones que simplemente use el mismo nombre de variable.

Una vez que se asigna a una variable X, coincidentemente, todos los nodos de la sub-expresión DAG que están vivos en el punto de asignación se convierten en no vivos, ya que la nueva asignación invalida el significado de las sub expresiones utilizando 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 haces es recorrer tu árbol en tu propio código, como un árbol de expresiones en el código fuente, por ejemplo. Llame a los nodos XNodes existentes, por ejemplo.

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

Este es un pseudo código muy simple. No es para 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;
  }
}

Entonces esa es una forma de verlo. Una caminata básica del árbol y simplemente agregar y referir a los nodos Dag a medida que avanza. La raíz del dag es DagNode, por ejemplo, la raíz del árbol.

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

En cuanto a ordenar el Dag, revisas cada DagNode de izquierda a derecha. En otras palabras, siga el borde izquierdo de DagNodes y luego el borde lateral derecho. Los números se asignan a la inversa. En otras palabras, cuando llegue a un DagNode sin hijos, asigne ese nodo al número de clasificación actual e incremente el número de clasificación, de modo que la recursión se desenrolle, 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 a la izquierda y a la derecha, calcule 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;
}

Answer 3

El nombre te dice la mayor parte de lo que necesitas saber de su definición: es un gráfico en el que cada borde solo fluye en una dirección y una vez que te arrastras por un borde, tu camino nunca volverá al vértice que acabas de dejar.

No puedo hablar de todos los usos (Wikipedia me ayuda), 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 es N GL programas, que cada uno necesita dos sombreadores, y cada sombreador necesita una fuente de sombreado de texto sin formato. Al representar estos recursos como un DAG, puedo consultar fácilmente el gráfico de los recursos existentes para evitar cargas duplicadas. Digamos que quiere varios materiales para usar sombreadores de vértices con el mismo código fuente. Es un desperdicio volver a cargar el origen y volver a compilar los sombreadores para cada uso cuando puede establecer una nueva ventaja para el recurso existente. De esta forma, también puede usar el gráfico para determinar si algo depende de algún recurso, y si no, elimínelo y libere su memoria; de hecho, esto sucede de manera muy automática.

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

Answer 4

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. Ellos no tienen ciclos.

Bueno, ahora puedo pensar en un uso: 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.

Espero que esto ayude.

aclamaciones

Answer 5

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

Answer 6

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

Por ejemplo, supongamos que tiene una canalización de cálculo configurable en tiempo de ejecución. Como un ejemplo de esto, supongamos que los cálculos A, B, C, D, E, F y G dependen uno del otro: 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 hacer 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 construcción automatizada decente (make, ant, scons, etc.) usará DAG para garantizar el orden de compilación adecuado de los componentes de un programa.

Answer 7

Si sabe qué árboles están en la programación, los DAG en la programación son similares pero permiten que un nodo tenga más de un padre. Esto puede ser útil cuando se quiere dejar que un nodo se agrupe en más de un solo padre, pero no se tiene el problema de un lío anudado de un gráfico general con ciclos. Todavía puede navegar un DAG fácilmente, pero hay varias maneras de volver a la raíz (porque puede haber más de un padre). Un DAG único en general podría tener múltiples raíces, pero en la práctica puede ser mejor simplemente quedarse con una raíz, como un árbol. Si comprende la herencia individual frente a la herencia múltiple en OOP, entonces conoce tree vs. DAG. Ya respondí esto here .

Answer 8

Supongo que ya conoce la terminología gráfica básica; de lo contrario, debe comenzar 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 con flechas. Lo opuesto es un gráfico no dirigido, cuyos bordes no especifican direcciones.

Acyclic significa que, si comienzas desde cualquier nodo arbitrario X y recorres todos los bordes posibles, no puedes 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 observa el diagrama en esa página, verá que la evolución del código controlado por revisión está dirigida (va "abajo", en este diagrama) y acíclica (nunca vuelve a "subir") .
• Árbol genealógico: está dirigido (eres el hijo de tus padres, no al revés) y acíclico (tus antepasados ​​nunca pueden ser tus descendientes).

Answer 9

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.

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

Todos los DAG tienen

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

DAG son diferentes de los árboles. En una estructura similar a un árbol, debe existir 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.

Answer 10

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

Answer 11

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

La respuesta a esa sub-pregunta 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 de enlaces son estructuras de datos utilizadas para ciertas clases de problemas, los gráficos son útiles para representar ciertas 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 implementarlos en el código. Ellos existen en un nivel más alto de abstracción. No se trata de programación, se trata de aplicar estructuras de datos en la solución de problemas.

Answer 12

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 materias que cumplan requisitos tales como prerrequisitos. Ahora está claro que no puede tomar una clase sobre Inteligencia Artificial [B] sin un curso de prerrequisitos sobre Algoritmos [A]. Por lo tanto B depende de A o en mejores términos A tiene un borde dirigido hacia B. Entonces, para alcanzar el Nodo B, debes visitar el Nodo A. Pronto quedará claro que después de agregar todas las materias con sus prerrequisitos a un gráfico , se convertirá en un gráfico acíclico dirigido.

Si hubo un ciclo, entonces nunca completarías un curso: p

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

¡Mi profesor me dio esta analogía y me ayudó a entender el 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

Answer 13

graph = estructura que consiste en nodos, que están conectados entre sí con bordes

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

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

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