Alguém pode me explicar em termos simples o que é um gráfico acíclico direcionado?

Alguém pode me explicar em termos simples o que é um gráfico acíclico direcionado? Eu olhei na Wikipedia, mas realmente não me faz ver seu uso na programação.

pontos com linhas apontando para outros pontos

gráfico = estrutura consistindo de nós, que estão conectados entre si por arestas

direcionado = as conexões entre os nós (arestas) têm uma direção: A -> B não é o mesmo que B -> A

acíclico = "não circular" = movendo-se de um nó para outro seguindo as bordas, você nunca encontrará o mesmo nó pela segunda vez.

Um bom exemplo de gráfico acíclico direcionado é uma árvore. Observe, entretanto, que nem todos os gráficos acíclicos direcionados são árvores.

Vejo muitas respostas indicando o significado de DAG (Directed Acyclic Graph), mas nenhuma resposta sobre seus aplicativos. Aqui está um muito simples -

Gráfico de pré-requisitos - Durante um curso de engenharia, cada aluno se depara com a tarefa de escolher disciplinas que atendam a requisitos, como pré-requisitos. Agora está claro que você não pode fazer uma aula de Inteligência Artificial [B] sem um curso pré-requisito em Algoritmos [A]. Portanto, B depende de A ou, em termos melhores, A tem uma aresta direcionada para B. Portanto, para chegar ao Nó B, você deve visitar o Nó A. Logo ficará claro que após adicionar todos os assuntos com seus pré-requisitos em um gráfico , acabará sendo um gráfico acíclico dirigido.

Se houvesse um ciclo, você nunca completaria um curso: p

Um sistema de software na universidade que permite que os alunos se inscrevam em cursos pode modelar disciplinas como nós para ter certeza de que o aluno fez um curso de pré-requisito antes de se inscrever no curso atual.

Meu professor deu esta analogia e ela me ajudou melhor a entender o DAG do que usar algum conceito complicado!

Outro exemplo em tempo real -> Exemplo em tempo real de como os DAGs podem ser usados ​​no sistema de versão

Os exemplos de uso de um gráfico acíclico direcionado em programação incluem mais ou menos qualquer coisa que represente conectividade e causalidade.

Por exemplo, suponha que você tenha um pipeline de computação configurável em tempo de execução. Como um exemplo disso, suponha que os cálculos A, B, C, D, E, F e G dependam uns dos outros: A depende de C, C depende de E e F, B depende de D e E, e D depende de F. Isso pode ser representado como um DAG. Depois de ter o DAG na memória, você pode escrever algoritmos para:

• certifique-se de que os cálculos são avaliados na ordem correta ( classificação topológica )
• se os cálculos podem ser feitos em paralelo, mas cada cálculo tem um tempo máximo de execução, você pode calcular o tempo máximo de execução de todo o conjunto

entre muitas outras coisas.

Fora do domínio da programação de aplicativos, qualquer ferramenta de construção automatizada decente (make, ant, scons, etc.) usará DAGs para garantir a ordem de construção adequada dos componentes de um programa.

Várias respostas deram exemplos do uso de gráficos (por exemplo, modelagem de rede) e você perguntou "o que isso tem a ver com programação?".

A resposta a essa subquestão é que não tem muito a ver com programação. Tem a ver com resolução de problemas.

Assim como as listas vinculadas são estruturas de dados usadas para certas classes de problemas, os gráficos são úteis para representar certos relacionamentos. Listas vinculadas, árvores, gráficos e outras estruturas abstratas têm apenas uma conexão com a programação na medida em que você pode implementá-las no código. Eles existem em um nível superior de abstração. Não se trata de programação, trata-se de aplicar estruturas de dados na solução de problemas.

Os gráficos acíclicos direcionados (DAG) têm as seguintes propriedades que os distinguem de outros gráficos:

1. Suas bordas mostram a direção.
2. Eles não têm ciclos.

Bem, posso pensar em um uso agora - DAG (conhecido como Wait-For-Graphs - mais detalhes técnicos ) são úteis na detecção de deadlocks, pois ilustram as dependências entre um conjunto de processos e recursos (ambos são nós no DAG) . O deadlock aconteceria quando um ciclo fosse detectado.

Presumo que você já conheça a terminologia básica de grafos; caso contrário, você deve começar pelo artigo sobre a teoria dos grafos .

Direcionado refere-se ao fato de que as arestas (conexões) têm direções. No diagrama, essas direções são mostradas pelas setas. O oposto é um gráfico não direcionado, cujas arestas não especificam direções.

Acíclico significa que, se você começar de qualquer nó arbitrário X e percorrer todas as arestas possíveis, não poderá retornar a X sem voltar para uma aresta já usada.

Vários aplicativos:

• Planilhas; isso é explicado no artigo do DAG .
• Controle de revisão : se você der uma olhada no diagrama daquela página, verá que a evolução do código controlado por revisão é direcionada (ele vai "para baixo", neste diagrama) e acíclica (nunca volta "para cima") .
• Árvore genealógica: é direcionada (você é filho de seus pais, não o contrário) e acíclica (seus ancestrais nunca podem ser seus descendentes).

Um DAG é um gráfico onde tudo flui na mesma direção e nenhum nó pode fazer referência a si mesmo.

Pense em árvores ancestrais; eles são na verdade DAGs.

Todos os DAGs têm

• Nós (locais para armazenar dados)
• Bordas direcionadas (que apontam na mesma direção)
• Um nó ancestral (um nó sem pais)
• Folhas (nós que não têm filhos)

DAGs são diferentes de árvores. Em uma estrutura semelhante a uma árvore, deve haver um caminho exclusivo entre cada dois nós. Em DAGs, um nó pode ter dois nós pais.

Aqui está um bom artigo sobre DAGs . Espero que ajude.

Gráficos, de todos os tipos, são usados ​​na programação para modelar vários relacionamentos diferentes do mundo real. Por exemplo, uma rede social é frequentemente representada por um gráfico (cíclico neste caso). Da mesma forma, topologias de rede, árvores genealógicas, rotas aéreas, ...

De uma perspectiva de código-fonte ou mesmo de código de três endereços (TAC), você pode visualizar o problema realmente facilmente nesta página ...

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

Se você for para a seção da árvore de expressão e, em seguida, descer um pouco a página, ela mostrará a "classificação topológica" da árvore e o algoritmo de como avaliar a expressão.

Então, nesse caso, você pode usar o DAG para avaliar expressões, o que é útil, pois a avaliação é normalmente interpretada e usar um avaliador DAG tornará os intrepretadores simples mais rápidos em princípio porque não está empurrando e saltando para uma pilha e também porque está eliminando subexpressões comuns.

O algoritmo básico para calcular o DAG em egípcio não antigo (ou seja, inglês) é este:

1) Faça seu objeto DAG assim

Você precisa de uma lista ativa e esta lista contém todos os nós e subexpressões DAG atuais ao vivo. Uma subexpressão DAG é um nó DAG, ou você também pode chamá-lo de nó interno. O que quero dizer com nó DAG ativo é que, se você atribuir a uma variável X, ela se tornará ativa. Uma subexpressão comum que então usa X usa essa instância. Se X for atribuído novamente, um NOVO DAG NODE é criado e adicionado à lista ativa e o X antigo é removido, de modo que a próxima subexpressão que usa X se referirá à nova instância e, portanto, não entrará em conflito com subexpressões que simplesmente use o mesmo nome de variável.

Depois de atribuir a uma variável X, então, por coincidência, todos os nós de subexpressão DAG que estão ativos no ponto de atribuição tornam-se inativos, pois a nova atribuição invalida o significado das subexpressões usando o valor antigo.

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

Então, o que você faz é percorrer sua árvore em seu próprio código, como uma árvore de expressões no código-fonte, por exemplo. Chame os nós existentes de XNodes, por exemplo.

Portanto, para cada XNode, você precisa decidir como adicioná-lo ao DAG, e há a possibilidade de que já esteja no DAG.

Este é um pseudocódigo muito simples. Não se destina à compilação.

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

Então essa é uma maneira de ver as coisas. Uma caminhada básica na árvore e apenas adicionar e referir-se aos nós Dag conforme avança. A raiz do dag é qualquer DagNode que a raiz da árvore retorna, por exemplo.

Obviamente, o procedimento de exemplo pode ser dividido em partes menores ou feito como subclasses com funções virtuais.

Quanto à classificação do Dag, você passa por cada DagNode da esquerda para a direita. Em outras palavras, siga a borda esquerda do DagNodes e, a seguir, a borda direita. Os números são atribuídos ao contrário. Em outras palavras, quando você atinge um DagNode sem filhos, atribua a esse Node o número de classificação atual e aumente o número de classificação, de modo que à medida que a recursão se desenrola, os números são atribuídos em ordem crescente.

Este exemplo trata apenas de árvores com nós que têm zero ou dois filhos. Obviamente, algumas árvores têm nós com mais de dois filhos, então a lógica ainda é a mesma. Em vez de calcular à esquerda e à direita, calcule da esquerda para a direita 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;
}

Se você sabe o que são árvores na programação, então os DAGs na programação são semelhantes, mas permitem que um nó tenha mais de um pai. Isso pode ser útil quando você deseja permitir que um nó seja agrupado sob mais do que apenas um único pai, mas não tem o problema de uma confusão de nós de um gráfico geral com ciclos. Você ainda pode navegar facilmente em um DAG, mas existem várias maneiras de voltar à raiz (porque pode haver mais de um pai). Em geral, um único DAG pode ter várias raízes, mas na prática pode ser melhor ficar apenas com uma raiz, como uma árvore. Se você entende herança única versus herança múltipla em OOP, então você conhece árvore versus DAG. Eu já respondi isso aqui .

O nome diz muito sobre o que você precisa saber sobre sua definição: é um gráfico onde cada aresta flui em uma direção e, uma vez que você rasteja por uma aresta, seu caminho nunca o levará de volta ao vértice que acabou de deixar.

Não posso falar sobre todos os usos (a Wikipedia ajuda nisso), mas para mim os DAGs são extremamente úteis para determinar dependências entre recursos. Meu mecanismo de jogo, por exemplo, representa todos os recursos carregados (materiais, texturas, sombreadores, texto simples, json analisado etc.) como um único DAG. Exemplo:

Um material são os programas N GL, em que cada um precisa de dois shaders e cada shader precisa de uma fonte de shader de texto simples. Ao representar esses recursos como um DAG, posso consultar facilmente o gráfico em busca de recursos existentes para evitar cargas duplicadas. Digamos que você queira que vários materiais usem vertex shaders com o mesmo código-fonte. É um desperdício recarregar a fonte e recompilar os sombreadores para cada uso quando você pode simplesmente estabelecer uma nova borda para o recurso existente. Desta forma, você também pode usar o gráfico para determinar se alguma coisa depende de um recurso e, se não, excluí-lo e liberar sua memória; na verdade, isso acontece de maneira quase automática.

Por extensão, os DAGs são úteis para expressar pipelines de processamento de dados. A natureza acíclica significa que você pode escrever com segurança código de processamento contextual que pode seguir ponteiros para baixo das bordas de um vértice, sem nunca encontrar novamente o mesmo vértice. Linguagens de programação visual, como VVVV , Max MSP ou interfaces baseadas em nó do Autodesk Maya, todas dependem de DAGs.

Um gráfico acíclico direcionado é útil quando você deseja representar ... um gráfico acíclico direcionado! O exemplo canônico é uma árvore genealógica ou genealogia.