Quelqu'un peut-il m'expliquer en termes simples ce qu'est un graphe acyclique dirigé?

Quelqu'un peut-il m'expliquer en termes simples ce qu'est un graphe acyclique dirigé? J'ai regardé sur Wikipédia mais cela ne me fait pas vraiment voir son utilisation en programmation.

points avec des lignes pointant vers d'autres points

graph = structure composée de nœuds, qui sont connectés les uns aux autres avec des arêtes

dirigé = les connexions entre les nœuds (arêtes) ont une direction: A -> B n'est pas la même chose que B -> A

acyclic = "non-circular" = se déplaçant de nœud en nœud en suivant les arêtes, vous ne rencontrerez jamais le même nœud pour la deuxième fois.

Un bon exemple de graphe acyclique dirigé est un arbre. Notez cependant que tous les graphes acycliques dirigés ne sont pas des arbres.

Je vois beaucoup de réponses indiquant la signification du DAG (Directed Acyclic Graph) mais aucune réponse sur ses applications. En voici une très simple -

Graphique des pré-requis - Au cours d'un cours d'ingénierie, chaque étudiant est confronté à la tâche de choisir des matières qui répondent à des exigences telles que des pré-requis. Il est maintenant clair que vous ne pouvez pas suivre un cours sur l'intelligence artificielle [B] sans un cours préalable sur les algorithmes [A]. Par conséquent, B dépend de A ou, mieux, A a un bord dirigé vers B.Ainsi, pour atteindre le nœud B, vous devez visiter le nœud A. Il sera bientôt clair qu'après avoir ajouté tous les sujets avec ses pré-requis dans un graphique , il se révélera être un graphe acyclique dirigé.

S'il y avait un cycle, vous ne termineriez jamais un cours: p

Un système logiciel dans l'université qui permet aux étudiants de s'inscrire à des cours peut modéliser les sujets comme des nœuds pour s'assurer que l'étudiant a suivi un cours préalable avant de s'inscrire au cours actuel.

Mon professeur a donné cette analogie et cela m'a mieux aidé à comprendre DAG plutôt que d'utiliser un concept compliqué!

Un autre exemple en temps réel -> Exemple en temps réel de la façon dont les DAG peuvent être utilisés dans le système de version

Les exemples d'utilisations d'un graphe acyclique dirigé en programmation incluent plus ou moins tout ce qui représente la connectivité et la causalité.

Par exemple, supposons que vous ayez un pipeline de calcul configurable au moment de l'exécution. À titre d'exemple, supposons que les calculs A, B, C, D, E, F et G dépendent l'un de l'autre: A dépend de C, C dépend de E et F, B dépend de D et E, et D dépend de F. Cela peut être représenté comme un DAG. Une fois que vous avez le DAG en mémoire, vous pouvez écrire des algorithmes dans:

• s'assurer que les calculs sont évalués dans le bon ordre ( tri topologique )
• si les calculs peuvent être effectués en parallèle mais que chaque calcul a un temps d'exécution maximum, vous pouvez calculer le temps d'exécution maximum de l'ensemble entier

entre autres choses.

En dehors du domaine de la programmation d'application, tout outil de construction automatisé décent (make, fourmi, scons, etc.) utilisera des DAG pour garantir le bon ordre de construction des composants d'un programme.

Plusieurs réponses ont donné des exemples d'utilisation de graphes (par exemple, la modélisation de réseau) et vous avez demandé "qu'est-ce que cela a à voir avec la programmation?".

La réponse à cette sous-question est qu'elle n'a rien à voir avec la programmation. Cela a à voir avec la résolution de problèmes.

Tout comme les listes chaînées sont des structures de données utilisées pour certaines classes de problèmes, les graphiques sont utiles pour représenter certaines relations. Les listes liées, les arbres, les graphiques et autres structures abstraites n'ont qu'un lien avec la programmation dans la mesure où vous pouvez les implémenter dans le code. Ils existent à un niveau d'abstraction supérieur. Il ne s'agit pas de programmation, il s'agit d'appliquer des structures de données à la solution de problèmes.

Les graphes acycliques dirigés (DAG) ont les propriétés suivantes qui les distinguent des autres graphes:

1. Leurs bords indiquent la direction.
2. Ils n'ont pas de cycles.

Eh bien, je peux penser à une utilisation pour le moment - DAG (connu sous le nom de Wait-For-Graphs - plus de détails techniques ) est pratique pour détecter les blocages car ils illustrent les dépendances entre un ensemble de processus et de ressources (les deux sont des nœuds dans le DAG) . Un blocage se produirait lorsqu'un cycle est détecté.

Je suppose que vous connaissez déjà la terminologie de base des graphes; sinon, vous devriez commencer par l'article sur la théorie des graphes .

Dirigé fait référence au fait que les arêtes (connexions) ont des directions. Dans le diagramme, ces directions sont indiquées par les flèches. Le contraire est un graphe non orienté, dont les arêtes ne spécifient pas de directions.

Acyclique signifie que, si vous partez d'un nœud X arbitraire et parcourez toutes les arêtes possibles, vous ne pouvez pas revenir à X sans revenir sur une arête déjà utilisée.

Plusieurs applications:

• Feuilles de calcul; ceci est expliqué dans l' article du DAG .
• Contrôle de révision : si vous regardez le schéma de cette page, vous verrez que l'évolution du code contrôlé par révision est dirigée (elle descend "vers le bas", dans ce schéma) et acyclique (elle ne remonte jamais "vers le haut") .
• Arbre généalogique: il est orienté (vous êtes l'enfant de vos parents, pas l'inverse) et acyclique (vos ancêtres ne peuvent jamais être votre descendant).

Un DAG est un graphe où tout s'écoule dans la même direction et aucun nœud ne peut se référer à lui-même.

Pensez aux arbres d'ascendance; ce sont en fait des DAG.

Tous les DAG ont

• Nœuds (emplacements pour stocker des données)
• Bords dirigés (qui pointent dans la même direction)
• Un nœud ancestral (un nœud sans parents)
• Feuilles (nœuds qui n'ont pas d'enfants)

Les DAG sont différents des arbres. Dans une structure arborescente, il doit y avoir un chemin unique entre tous les deux nœuds. Dans les DAG, un nœud peut avoir deux nœuds parents.

Voici un bon article sur les DAG . J'espère que cela aide.

Les graphiques, de toutes sortes, sont utilisés dans la programmation pour modéliser différentes relations du monde réel. Par exemple, un réseau social est souvent représenté par un graphe (cyclique dans ce cas). De même, topologies de réseau, arbres généalogiques, routes aériennes, ...

Du point de vue du code source ou même du code à trois adresses (TAC), vous pouvez visualiser le problème très facilement sur cette page ...

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

Si vous allez dans la section de l'arborescence d'expression et que vous descendez un peu la page, cela montre le "tri topologique" de l'arborescence et l'algorithme pour évaluer l'expression.

Donc, dans ce cas, vous pouvez utiliser le DAG pour évaluer des expressions, ce qui est pratique car l'évaluation est normalement interprétée et l'utilisation d'un tel évaluateur de DAG rendra les simples interprètes plus rapides en principe car il ne pousse pas et ne saute pas vers une pile et aussi parce qu'il élimine sous-expressions courantes.

L'algorithme de base pour calculer le DAG en égyptien non ancien (c'est-à-dire en anglais) est le suivant:

1) Faites de votre objet DAG comme ça

Vous avez besoin d'une liste en direct et cette liste contient tous les nœuds DAG et sous-expressions DAG actuels. Une sous-expression DAG est un nœud DAG, ou vous pouvez également l'appeler un nœud interne. Ce que je veux dire par live DAG Node, c'est que si vous assignez à une variable X, il devient live. Une sous-expression commune qui utilise ensuite X utilise cette instance. Si X est à nouveau attribué, un NOUVEAU NŒUD DAG est créé et ajouté à la liste en direct et l'ancien X est supprimé de sorte que la sous-expression suivante qui utilise X fera référence à la nouvelle instance et ne sera donc pas en conflit avec les sous-expressions qui utilisez simplement le même nom de variable.

Une fois que vous affectez à une variable X, tous les nœuds de sous-expression DAG qui sont actifs au point d'attribution deviennent co-accessoirement non actifs, car la nouvelle affectation invalide la signification des sous-expressions utilisant l'ancienne valeur.

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

Donc ce que vous faites est de parcourir votre arbre dans votre propre code, comme un arbre d'expressions dans le code source par exemple. Appelez les nœuds existants XNodes par exemple.

Donc, pour chaque XNode, vous devez décider comment l'ajouter dans le DAG, et il est possible qu'il soit déjà dans le DAG.

C'est un pseudo-code très simple. Non destiné à la compilation.

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

C'est donc une façon de voir les choses. Une promenade de base de l'arbre et juste ajouter et faire référence aux nœuds Dag au fur et à mesure. La racine du dag est le DagNode que la racine de l'arbre renvoie par exemple.

Évidemment, la procédure d'exemple peut être divisée en parties plus petites ou transformée en sous-classes avec des fonctions virtuelles.

En ce qui concerne le tri du Dag, vous parcourez chaque DagNode de gauche à droite. En d'autres termes, suivez le bord gauche de DagNodes, puis le bord droit. Les numéros sont attribués à l'envers. En d'autres termes, lorsque vous atteignez un DagNode sans enfant, attribuez à ce nœud le numéro de tri actuel et incrémentez le numéro de tri, de sorte que lorsque la récursivité se déroule, les numéros sont attribués dans un ordre croissant.

Cet exemple ne traite que les arbres avec des nœuds qui ont zéro ou deux enfants. De toute évidence, certains arbres ont des nœuds avec plus de deux enfants, donc la logique est toujours la même. Au lieu de calculer gauche et droite, calculez de gauche à droite 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 vous savez quels arbres sont en programmation, alors les DAG en programmation sont similaires mais ils permettent à un nœud d'avoir plus d'un parent. Cela peut être pratique lorsque vous souhaitez laisser un nœud être regroupé sous plus qu'un simple parent, sans toutefois avoir le problème d'un désordre noué d'un graphe général avec des cycles. Vous pouvez toujours naviguer facilement dans un DAG, mais il existe plusieurs façons de revenir à la racine (car il peut y avoir plus d'un parent). Un seul DAG peut en général avoir plusieurs racines, mais dans la pratique, il peut être préférable de s'en tenir à une seule racine, comme un arbre. Si vous comprenez l'héritage unique et multiple en POO, alors vous connaissez arbre vs DAG. J'ai déjà répondu à cela ici .

Le nom vous dit l'essentiel de ce que vous devez savoir sur sa définition: c'est un graphique où chaque arête ne coule que dans une direction et une fois que vous rampez sur une arête, votre chemin ne vous ramènera jamais au sommet que vous venez de quitter.

Je ne peux pas parler de toutes les utilisations (Wikipedia y aide), mais pour moi, les DAG sont extrêmement utiles pour déterminer les dépendances entre les ressources. Mon moteur de jeu, par exemple, représente toutes les ressources chargées (matériaux, textures, shaders, texte en clair, json analysé, etc.) sous la forme d'un seul DAG. Exemple:

Un matériau est constitué de programmes N GL, qui nécessitent chacun deux shaders, et chaque shader a besoin d'une source de shader en texte clair. En représentant ces ressources sous forme de DAG, je peux facilement interroger le graphique sur les ressources existantes pour éviter les charges en double. Supposons que vous souhaitiez que plusieurs matériaux utilisent des nuanceurs de vertex avec le même code source. Il est inutile de recharger la source et de recompiler les shaders pour chaque utilisation lorsque vous pouvez simplement établir une nouvelle limite à la ressource existante. De cette façon, vous pouvez également utiliser le graphique pour déterminer si quelque chose dépend d'une ressource, et sinon, le supprimer et libérer sa mémoire, en fait cela se produit presque automatiquement.

Par extension, les DAG sont utiles pour exprimer des pipelines de traitement de données. La nature acyclique signifie que vous pouvez écrire en toute sécurité un code de traitement contextuel qui peut suivre des pointeurs sur les arêtes d'un sommet sans jamais rencontrer le même sommet. Les langages de programmation visuelle tels que VVVV , Max MSP ou les interfaces basées sur les nœuds d'Autodesk Maya reposent tous sur des DAG.

Un graphe acyclique dirigé est utile lorsque vous voulez représenter ... un graphe acyclique dirigé! L'exemple canonique est un arbre généalogique ou une généalogie.