114

有向非巡回グラフとは何かを簡単に説明してもらえますか？私はウィキペディアを見てきましたが、プログラミングでの使用を実際に見ることはできません。

4

13 に答える 13

177

グラフ=エッジで相互に接続されたノードで構成される構造

有向=ノード（エッジ）間の接続には方向があります：A->BはB->Aと同じではありません

acyclic = "non-circular" =エッジをたどってノードからノードに移動すると、同じノードに2度目に遭遇することはありません。

有向非巡回グラフの良い例はツリーです。ただし、すべての有向非巡回グラフがツリーであるとは限らないことに注意してください。

于 2010-02-17T19:29:41.867 に答える
92

他のドットを指す線のあるドット

于 2012-12-14T11:46:49.293 に答える
51

DAG（有向非巡回グラフ）の意味を示す多くの回答がありますが、そのアプリケーションに関する回答はありません。これは非常に単純なものです-

前提条件のグラフ-エンジニアリングコースでは、すべての学生が前提条件などの要件に従う科目を選択するという課題に直面します。アルゴリズム[A]の前提条件となるコースがないと、人工知能[B]のクラスを受講できないことは明らかです。したがって、BはAに依存します。より適切には、AはBに向けられたエッジを持ちます。したがって、ノードBに到達するには、ノードAにアクセスする必要があります。前提条件を持つすべてのサブジェクトをグラフに追加した後、すぐに明らかになります。 、有向非巡回グラフになります。

サイクルがあった場合、コースを完了することは決してありません：p

学生がコースに登録できるようにする大学のソフトウェアシステムは、現在のコースに登録する前に、学生が前提条件のコースを受講したことを確認するために、科目をノードとしてモデル化できます。

私の教授はこのアナロジーを与えました、そしてそれは私がいくつかの複雑な概念を使うよりもDAGを理解するのを最も助けました！

別のリアルタイムの例->バージョンシステムでDAGを使用する方法のリアルタイムの例

于 2015-11-21T01:58:15.983 に答える
26

プログラミングでの有向非巡回グラフの使用例には、接続性と因果関係を表すものが多かれ少なかれ含まれます。

たとえば、実行時に構成可能な計算パイプラインがあるとします。この一例として、計算A、B、C、D、E、F、およびGが互いに依存していると仮定します。AはCに依存し、CはEとFに依存し、BはDとEに依存し、Dはに依存します。 F.これはDAGとして表すことができます。DAGをメモリに保存したら、次のアルゴリズムを記述できます。

  • 計算が正しい順序で評価されていることを確認してください（トポロジカルソート）
  • 計算を並行して実行できるが、各計算に最大実行時間が含まれている場合は、セット全体の最大実行時間を計算できます。

他の多くのものの中で。

アプリケーションプログラミングの領域外では、適切な自動ビルドツール（make、ant、sconsなど）はDAGを使用して、プログラムのコンポーネントの適切なビルド順序を保証します。

于 2010-02-17T19:43:26.427 に答える
14

いくつかの回答がグラフの使用例（ネットワークモデリングなど）を示しており、「これはプログラミングと何の関係があるのか​​」と質問しました。

そのサブ質問に対する答えは、プログラミングとはほとんど関係がないということです。それは問題解決と関係があります。

リンクリストが特定のクラスの問題に使用されるデータ構造であるように、グラフは特定の関係を表すのに役立ちます。リンクリスト、ツリー、グラフ、およびその他の抽象的な構造は、コードで実装できるという点でプログラミングとのみ関係があります。それらはより高いレベルの抽象化で存在します。それはプログラミングではなく、問題の解決にデータ構造を適用することです。

于 2010-02-17T19:45:39.947 に答える
13

有向非巡回グラフ（DAG）には、他のグラフと区別するための次のプロパティがあります。

  1. それらのエッジは方向を示します。
  2. サイクルはありません。

さて、私は今1つの使用法を考えることができます-DAG（Wait-For-Graphsとして知られています-より技術的な詳細）は、一連のプロセスとリソース（両方ともDAGのノード）間の依存関係を示すため、デッドロックを検出するのに便利です。サイクルが検出されると、デッドロックが発生します。

于 2010-02-17T19:36:38.603 に答える
11

あなたはすでに基本的なグラフ用語を知っていると思います。それ以外の場合は、グラフ理論に関する記事から始める必要があります。

有向とは、エッジ（接続）に方向があるという事実を指します。この図では、これらの方向が矢印で示されています。反対は無向グラフで、そのエッジは方向を指定しません。

非周期的とは、任意のノードXから開始し、考えられるすべてのエッジを通過する場合、すでに使用されているエッジに戻らなければXに戻ることができないことを意味します。

いくつかのアプリケーション：

  • スプレッドシート; これはDAGの記事で説明されています。
  • リビジョン管理：そのページの図を見ると、リビジョン管理されたコードの進化が方向付けられており（この図では「下」になります）、非周期的（「上」に戻ることはありません）であることがわかります。 。
  • 家系図：それは指示され（あなたはあなたの両親の子供であり、その逆ではありません）、非周期的です（あなたの祖先は決してあなたの子孫になることはできません）。
于 2010-02-17T20:04:46.003 に答える
6

DAGは、すべてが同じ方向に流れ、ノードがそれ自体を参照できないグラフです。

祖先の木について考えてみてください。それらは実際にはDAGです。

すべてのDAGには

  • ノード（データを保存する場所）
  • 有向エッジ（同じ方向を指す）
  • 祖先ノード（親のないノード）
  • 葉（子を持たないノード）

DAGはツリーとは異なります。ツリーのような構造では、2つのノードごとに一意のパスが必要です。DAGでは、ノードは2つの親ノードを持つことができます。

これがDAGに関する良い記事です。それがお役に立てば幸いです。

于 2018-04-05T11:05:39.423 に答える
4

あらゆる種類のグラフは、さまざまな異なる実世界の関係をモデル化するためのプログラミングで使用されます。たとえば、ソーシャルネットワークはグラフで表されることがよくあります（この場合は循環的です）。同様に、ネットワークトポロジ、家系図、航空会社のルート、...

于 2010-02-17T19:37:01.883 に答える
2

ソースコードまたは3番地（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;
}

したがって、たとえばソースコードの式のツリーなど、独自のコードでツリーをウォークスルーします。たとえば、既存のノードをXNodeと呼びます。

したがって、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に到達したら、そのノードに現在の並べ替え番号を割り当て、並べ替え番号をインクリメントします。これにより、再帰が巻き戻され、番号が昇順で割り当てられます。

この例では、子が0個または2個あるノードを持つツリーのみを処理します。明らかに、一部のツリーには3つ以上の子を持つノードがあるため、ロジックは同じです。左と右を計算する代わりに、左から右などに計算します。

// 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;
}
于 2013-03-01T17:01:52.497 に答える
1

プログラミングのツリーがわかっている場合、プログラミングのDAGは似ていますが、ノードが複数の親を持つことができます。これは、ノードを1つ以上の親の下にまとめたいが、サイクルを伴う一般的なグラフの結び目の混乱の問題がない場合に便利です。DAGを簡単にナビゲートすることはできますが、ルートに戻るには複数の方法があります（複数の親が存在する可能性があるため）。一般に、単一のDAGは複数のルートを持つことができますが、実際には、ツリーのように1つのルートに固執する方がよい場合があります。OOPでの単一継承と多重継承を理解している場合は、ツリーとDAGを知っています。私はすでにここでこれに答えました。

于 2015-04-07T03:43:02.830 に答える
1

この名前は、その定義について知っておく必要のあることのほとんどを示しています。これは、すべてのエッジが一方向にのみ流れるグラフであり、エッジをクロールすると、パスが左の頂点に戻ることはありません。

私はすべての用途について話すことはできませんが（ウィキペディアはそこで役立ちます）、私にとってDAGはリソース間の依存関係を判断するときに非常に役立ちます。たとえば、私のゲームエンジンは、ロードされたすべてのリソース（マテリアル、テクスチャ、シェーダー、プレーンテキスト、解析されたjsonなど）を単一のDAGとして表します。例：

マテリアルはNGLプログラムであり、それぞれに2つのシェーダーが必要であり、各シェーダーにはプレーンテキストシェーダーソースが必要です。これらのリソースをDAGとして表すことで、グラフに既存のリソースを簡単に照会して、重複する負荷を回避できます。複数のマテリアルで同じソースコードの頂点シェーダーを使用するとします。既存のリソースに新しいエッジを確立できる場合は、ソースをリロードして、使用するたびにシェーダーを再コンパイルするのは無駄です。このようにして、グラフを使用して、リソースに依存しているものがあるかどうかを判断し、依存していない場合は、リソースを削除してメモリを解放することもできます。実際、これはほぼ自動的に行われます。

ひいては、DAGはデータ処理パイプラインを表現するのに役立ちます。非周期的な性質は、同じ頂点に再遭遇することなく、頂点からエッジに沿ってポインタをたどることができるコンテキスト処理コードを安全に記述できることを意味します。VVVV、Max MSP 、Autodesk Mayaのノードベースのインターフェイスなどのビジュアルプログラミング言語は、すべてDAGに依存しています。

于 2017-06-25T20:02:56.047 に答える
-5

有向非巡回グラフは、...有向非巡回グラフを表現したい場合に便利です。正規の例は、家系図または系図です。

于 2010-02-17T19:33:49.047 に答える