누군가가 방향성 비순환 그래프가 무엇인지 간단한 용어로 설명 할 수 있습니까?

누군가가 방향성 비순환 그래프가 무엇인지 간단한 용어로 설명 할 수 있습니까?

---

누군가가 방향성 비순환 그래프가 무엇인지 간단한 용어로 설명 할 수 있습니까? 위키 백과를 살펴 봤지만 프로그래밍에서 그 용도를 실제로 볼 수는 없습니다.

---

다른 점을 가리키는 선이있는 점

---

그래프 = 가장자리로 서로 연결된 노드로 구성된 구조

Directed = 노드 (가장자리) 사이의 연결은 방향을 갖습니다. A-> B는 B-> A와 동일하지 않습니다.

acyclic = "non-circular"= 가장자리를 따라 노드에서 노드로 이동하면 두 번째로 동일한 노드를 만나지 않습니다.

방향성 비순환 그래프의 좋은 예는 트리입니다. 그러나 모든 유 방향 비순환 그래프가 트리는 아닙니다.

---

DAG (Directed Acyclic Graph)의 의미를 나타내는 많은 답변이 있지만 해당 응용 프로그램에 대한 답변은 없습니다. 여기 아주 간단한 것이 있습니다.

전제 조건 그래프 -엔지니어링 과정에서 모든 학생은 전제 조건과 같은 요구 사항을 따르는 과목을 선택하는 과제에 직면합니다. 이제 알고리즘 [A]에 대한 사전 필수 과정 없이는 인공 지능 [B]에 대한 수업을 수강 할 수 없습니다. 따라서 B는 A에 의존하거나 더 나은 용어로 A는 B로 향하는 우위를 가지고 있습니다. 따라서 노드 B에 도달하려면 노드 A를 방문해야합니다. 전제 조건이있는 모든 주제를 그래프에 추가하면 곧 명확해질 것입니다. , 그것은 방향성 비순환 그래프로 판명 될 것입니다.

주기가 있었다면 코스를 완료하지 못할 것입니다.

학생들이 과정에 등록 할 수 있도록하는 대학의 소프트웨어 시스템은 학생이 현재 과정에 등록하기 전에 필수 과정을 수강했는지 확인하기 위해 과목을 노드로 모델링 할 수 있습니다.

제 교수님이이 비유를 해주셨 고 복잡한 개념을 사용하는 것보다 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 (Directed Acyclic Graph)에는 다른 그래프와 구별되는 다음과 같은 속성이 있습니다.

1. 그들의 가장자리는 방향을 보여줍니다.
2. 그들은주기가 없습니다.

글쎄요, 지금 당장 한 가지 사용을 생각할 수 있습니다. DAG ( Gate-For-Graphs 로 알려짐 -더 많은 기술적 세부 사항 )는 일련의 프로세스 및 리소스 (둘 다 DAG의 노드) 간의 종속성을 설명하므로 교착 상태를 감지하는 데 편리합니다. . 주기가 감지되면 교착 상태가 발생합니다.

---

기본 그래프 용어를 이미 알고 있다고 가정합니다. 그렇지 않으면 그래프 이론 에 대한 기사에서 시작해야합니다 .

Directed 는 모서리 (연결)에 방향이 있다는 사실을 나타냅니다. 다이어그램에서 이러한 방향은 화살표로 표시됩니다. 그 반대는 무 방향 그래프로, 간선이 방향을 지정하지 않습니다.

비순환 이란 임의의 노드 X에서 시작하여 가능한 모든 에지를 통과하는 경우 이미 사용 된 에지로 돌아 가지 않고는 X로 돌아갈 수 없음을 의미합니다.

여러 응용 프로그램 :

• 스프레드 시트; 이것은 DAG 문서에 설명되어 있습니다.
• 개정 제어 : 해당 페이지의 다이어그램을 보면 개정 제어 코드의 진화가 지시되고 (이 다이어그램에서 "다운"으로 이동) 비순환 (백업되지 않음)을 볼 수 있습니다. .
• 가계도 : 지시 (당신은 부모의 자식이지 반대 방향이 아님)와 비순환 적 (조상은 당신의 후손이 될 수 없습니다)입니다.

---

모든 종류의 그래프는 다양한 실제 관계를 모델링하기 위해 프로그래밍에 사용됩니다. 예를 들어 소셜 네트워크는 종종 그래프로 표시됩니다 (이 경우 순환). 마찬가지로, 네트워크 토폴로지, 패밀리 트리, 항공 노선, ...

---

DAG는 모든 것이 같은 방향으로 흐르고 어떤 노드도 자신을 다시 참조 할 수없는 그래프입니다.

조상 나무를 생각하십시오. 실제로 DAG입니다.

모든 DAG에는

• 노드 (데이터를 저장할 장소)
• Directed Edges (동일한 방향을 가리키는)
• 조상 노드 (부모가없는 노드)
• 잎 (자식이없는 노드)

DAG는 나무와 다릅니다. 나무와 같은 구조에서는 두 노드마다 고유 한 경로가 있어야합니다. DAG에서 노드는 두 개의 상위 노드를 가질 수 있습니다.

다음 은 DAG에 대한 좋은 기사 입니다. 도움이 되었기를 바랍니다.

---

From a source code or even three address(TAC) code perspective you can visualize the problem really easily at this page...

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

If you go to the expression tree section, and then page down a bit it shows the "topological sorting" of the tree, and the algorithm for how to evaluate the expression.

So in that case you can use the DAG to evaluate expressions, which is handy since evaluation is normally interpreted and using such a DAG evaluator will make simple intrepreters faster in principal because it is not pushing and popping to a stack and also because it is eliminating common sub-expressions.

The basic algorithm to compute the DAG in non ancient egyptian(ie English) is this:

1) Make your DAG object like so

You need a live list and this list holds all the current live DAG nodes and DAG sub-expressions. A DAG sub expression is a DAG Node, or you can also call it an internal node. What I mean by live DAG Node is that if you assign to a variable X then it becomes live. A common sub-expression that then uses X uses that instance. If X is assigned to again then a NEW DAG NODE is created and added to the live list and the old X is removed so the next sub-expression that uses X will refer to the new instance and thus will not conflict with sub-expressions that merely use the same variable name.

Once you assign to a variable X, then co-incidentally all the DAG sub-expression nodes that are live at the point of assignment become not-live, since the new assignment invalidates the meaning of sub expressions using the old value.

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

So what you do is walk through your tree in your own code, such as a tree of expressions in source code for example. Call the existing nodes XNodes for example.

So for each XNode you need to decide how to add it into the DAG, and there is the possibility that it is already in the DAG.

This is very simple pseudo code. Not intended for 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;
  }
}

So that is one way of looking at it. A basic walk of the tree and just adding in and referring to the Dag nodes as it goes. The root of the dag is whatever DagNode the root of the tree returns for example.

Obviously the example procedure can be broken up into smaller parts or made as sub-classes with virtual functions.

As for sorting the Dag, you go through each DagNode from left to right. In other words follow the DagNodes left hand edge, and then the right hand side edge. The numbers are assigned in reverse. In other words when you reach a DagNode with no children, assign that Node the current sorting number and increment the sorting number, so as the recursion unwinds the numbers get assigned in increasing order.

This example only handles trees with nodes that have zero or two children. Obviously some trees have nodes with more than two children so the logic is still the same. Instead of computing left and right, compute from left to right 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;
}

---

If you know what trees are in programming, then DAGs in programming are similar but they allow a node to have more than one parent. This can be handy when you want to let a node be clumped under more than just a single parent, yet not have the problem of a knotted mess of a general graph with cycles. You can still navigate a DAG easily, but there are multiple ways to get back to the root (because there can be more than one parent). A single DAG could in general have multiple roots but in practice may be better to just stick with one root, like a tree. If you understand single vs. multiple inheritance in OOP, then you know tree vs. DAG. I already answered this here.

---

The name tells you most of what you need to know of its definition: It's a graph where every edge only flows in one direction and once you crawl down an edge your path will never return you to the vertex you just left.

I can't speak to all the uses (Wikipedia helps there), but for me DAGs are extremely useful when determining dependencies between resources. My game engine for instance represents all loaded resources (materials, textures, shaders, plaintext, parsed json etc) as a single DAG. Example:

A material is N GL programs, that each need two shaders, and each shader needs a plaintext shader source. By representing these resources as a DAG, I can easily query the graph for existing resources to avoid duplicate loads. Say you want several materials to use vertex shaders with the same source code. It is wasteful to reload the source and recompile the shaders for every use when you can just establish a new edge to the existing resource. In this way you can also use the graph to determine if anything depends on a resource at all, and if not, delete it and free its memory, in fact this happens pretty much automatically.

By extension, DAGs are useful for expressing data processing pipelines. The acyclic nature means you can safely write contextual processing code that can follow pointers down the edges from a vertex without ever reencountering the same vertex. Visual programming languages like VVVV, Max MSP or Autodesk Maya's node-based interfaces all rely on DAGs.

---

A directed acyclic graph is useful when you want to represent...a directed acyclic graph! The canonical example is a family tree or genealogy.

참고URL : https://stackoverflow.com/questions/2283757/can-someone-explain-in-simple-terms-to-me-what-a-directed-acyclic-graph-is