Czy ktoś może mi w prosty sposób wyjaśnić, czym jest skierowany graf acykliczny?

Czy ktoś może mi w prosty sposób wyjaśnić, czym jest skierowany graf acykliczny? Zajrzałem do Wikipedii, ale tak naprawdę nie widzę jej zastosowania w programowaniu.

kropki z liniami wskazującymi na inne kropki

graf = struktura składająca się z węzłów połączonych ze sobą krawędziami

skierowane = połączenia między węzłami (krawędziami) mają kierunek: A -> B to nie to samo co B -> A

acyclic = "non-circle" = przejście od węzła do węzła przez podążanie za krawędziami, nigdy nie napotkasz tego samego węzła po raz drugi.

Dobrym przykładem skierowanego grafu acyklicznego jest drzewo. Należy jednak pamiętać, że nie wszystkie skierowane grafy acykliczne są drzewami.

Widzę wiele odpowiedzi wskazujących na znaczenie DAG (Directed Acyclic Graph), ale nie ma odpowiedzi na temat jego zastosowań. Oto bardzo prosty -

Wykres wymagań wstępnych - podczas kursu inżynierskiego każdy student ma za zadanie wybrać przedmioty zgodne z wymaganiami, takimi jak wymagania wstępne. Teraz jest jasne, że nie możesz brać udziału w zajęciach ze sztucznej inteligencji [B] bez wymaganego kursu z algorytmów [A]. Stąd B zależy od A lub, mówiąc lepiej, A ma krawędź skierowaną do B. Tak więc, aby dotrzeć do Węzła B, musisz odwiedzić Węzeł A. Wkrótce okaże się, że po dodaniu wszystkich przedmiotów z ich wymaganiami wstępnymi do wykresu okaże się, że jest to ukierunkowany graf acykliczny.

Gdyby istniał cykl, nigdy nie ukończyłbyś kursu: str

System oprogramowania na uniwersytecie, który umożliwia studentom rejestrowanie się na kursy, może modelować przedmioty jako węzły, aby upewnić się, że student ukończył wymagany kurs przed zarejestrowaniem się na bieżący kurs.

Mój profesor podał tę analogię i najlepiej pomogło mi to zrozumieć DAG, zamiast używać skomplikowanej koncepcji!

Inny przykład czasu rzeczywistego -> Przykład czasu rzeczywistego pokazujący, jak DAG mogą być używane w systemie wersji

Przykładowe zastosowania skierowanego grafu acyklicznego w programowaniu obejmują mniej więcej wszystko, co reprezentuje łączność i przyczynowość.

Na przykład załóżmy, że masz potok obliczeniowy, który można konfigurować w czasie wykonywania. Jako przykład załóżmy, że obliczenia A, B, C, D, E, F i G zależą od siebie: A zależy od C, C zależy od E i F, B zależy od D i E, a D zależy od F. Można to przedstawić jako DAG. Gdy masz już DAG w pamięci, możesz pisać algorytmy do:

• upewnij się, że obliczenia są oceniane we właściwej kolejności ( sortowanie topologiczne )
• jeśli obliczenia można wykonywać równolegle, ale każde obliczenie ma maksymalny czas wykonania, można obliczyć maksymalny czas wykonania całego zestawu

wśród wielu innych rzeczy.

Poza dziedziną programowania aplikacji każde przyzwoite automatyczne narzędzie do kompilacji (make, ant, scons itp.) Będzie używać DAG, aby zapewnić właściwą kolejność kompilacji komponentów programu.

W kilku odpowiedziach podano przykłady użycia wykresów (np. Modelowanie sieci), a Ty zapytałeś „co to ma wspólnego z programowaniem?”.

Odpowiedź na to pod-pytanie brzmi, że nie ma ono wiele wspólnego z programowaniem. Ma to związek z rozwiązywaniem problemów.

Podobnie jak listy połączone są strukturami danych używanymi do określonych klas problemów, wykresy są przydatne do przedstawiania pewnych relacji. Połączone listy, drzewa, wykresy i inne abstrakcyjne struktury mają połączenie z programowaniem, ponieważ można je zaimplementować w kodzie. Istnieją na wyższym poziomie abstrakcji. Nie chodzi o programowanie, chodzi o zastosowanie struktur danych w rozwiązywaniu problemów.

Skierowane grafy acykliczne (DAG) mają następujące właściwości, które odróżniają je od innych grafów:

1. Ich krawędzie wskazują kierunek.
2. Nie mają cykli.

Cóż, w tej chwili przychodzi mi do głowy jedno zastosowanie - DAG (znane jako Wait-For-Graphs - więcej szczegółów technicznych ) są przydatne w wykrywaniu zakleszczeń, ponieważ ilustrują zależności między zestawem procesów i zasobów (oba są węzłami w DAG) . Zakleszczenie nastąpiłoby po wykryciu cyklu.

Zakładam, że znasz już podstawową terminologię dotyczącą grafów; w przeciwnym razie zacznij od artykułu o teorii grafów .

Skierowane odnosi się do faktu, że krawędzie (połączenia) mają kierunki. Na schemacie kierunki te są pokazane strzałkami. Przeciwieństwem jest wykres niekierowany, którego krawędzie nie określają kierunków.

Acykliczny oznacza, że ​​jeśli zaczniesz od dowolnego węzła X i przejdziesz przez wszystkie możliwe krawędzie, nie możesz wrócić do X bez powrotu do już używanej krawędzi.

Kilka zastosowań:

• Arkusze kalkulacyjne; wyjaśniono to w artykule DAG .
• Kontrola wersji : jeśli spojrzysz na diagram na tej stronie, zobaczysz, że ewolucja kodu kontrolowanego przez wersję jest ukierunkowana (na tym diagramie idzie „w dół”) i acykliczna (nigdy nie wraca „w górę”) .
• Drzewo genealogiczne: jest ukierunkowane (jesteś dzieckiem swoich rodziców, a nie na odwrót) i acykliczne (Twoi przodkowie nigdy nie mogą być Twoim potomkiem).

DAG to wykres, na którym wszystko płynie w tym samym kierunku i żaden węzeł nie może odwoływać się z powrotem do siebie.

Pomyśl o drzewach przodków; są w rzeczywistości DAGami.

Wszystkie DAG mają

• Węzły (miejsca przechowywania danych)
• Skierowane krawędzie (które wskazują ten sam kierunek)
• Węzeł przodków (węzeł bez rodziców)
• Liście (węzły, które nie mają dzieci)

DAG różnią się od drzew. W strukturze przypominającej drzewo musi istnieć unikalna ścieżka między każdymi dwoma węzłami. W DAG węzeł może mieć dwa węzły nadrzędne.

Oto dobry artykuł o DAGach . Mam nadzieję że to pomogło.

Wszelkiego rodzaju wykresy są używane w programowaniu do modelowania różnych relacji w świecie rzeczywistym. Na przykład sieć społecznościowa jest często reprezentowana przez wykres (w tym przypadku cykliczny). Podobnie topologie sieci, drzewa genealogiczne, trasy lotnicze, ...

Z perspektywy kodu źródłowego lub nawet kodu trzech adresów (TAC) możesz bardzo łatwo zwizualizować problem na tej stronie ...

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

Jeśli przejdziesz do sekcji drzewa wyrażeń, a następnie przewiniesz nieco w dół, zobaczysz „sortowanie topologiczne” drzewa i algorytm oceny wyrażenia.

W takim przypadku możesz użyć DAG do oceny wyrażeń, co jest przydatne, ponieważ ocena jest normalnie interpretowana, a użycie takiego ewaluatora DAG przyspieszy w zasadzie prostą interpretację, ponieważ nie jest to wypychanie i wyskakiwanie na stos, a także dlatego, że eliminuje wspólne wyrażenia podrzędne.

Podstawowy algorytm obliczania DAG w języku innym niż starożytny egipski (tj. Angielski) jest następujący:

1) Zrób swój obiekt DAG w ten sposób

Potrzebujesz listy na żywo, a ta lista zawiera wszystkie bieżące węzły DAG na żywo i wyrażenia podrzędne DAG. Wyrażenie podrzędne DAG jest węzłem DAG lub można je również nazwać węzłem wewnętrznym. Przez węzeł DAG na żywo mam na myśli to, że jeśli przypiszesz do zmiennej X, stanie się ona aktywna. Typowe wyrażenie podrzędne, które następnie używa X, używa tego wystąpienia. Jeśli X zostanie ponownie przypisany do, wówczas tworzony jest NOWY WĘZEŁ DAG i dodawany do aktualnej listy, a stary X jest usuwany, więc następne wyrażenie podrzędne, które używa X, będzie odnosić się do nowej instancji i nie będzie kolidować z wyrażeniami podrzędnymi, które wystarczy użyć tej samej nazwy zmiennej.

Po przypisaniu do zmiennej X, przypadkowo wszystkie węzły wyrażenia podrzędnego DAG, które są aktywne w momencie przypisania, stają się nieaktywne, ponieważ nowe przypisanie unieważnia znaczenie wyrażeń podrzędnych używających starej wartości.

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

Więc to, co robisz, to przechodzenie przez drzewo we własnym kodzie, takim jak na przykład drzewo wyrażeń w kodzie źródłowym. Na przykład wywołaj istniejące węzły XNodes.

Więc dla każdego XNode musisz zdecydować, jak dodać go do DAG i istnieje możliwość, że jest już w DAG.

To bardzo prosty pseudokod. Nie jest przeznaczony do kompilacji.

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

Więc to jest jeden sposób patrzenia na to. Podstawowy spacer po drzewie i po prostu dodawanie i odwoływanie się do węzłów Dag na bieżąco. Korzeń dag jest tym, co DagNode zwraca korzeń drzewa, na przykład.

Oczywiście przykładowa procedura może być podzielona na mniejsze części lub utworzona jako podklasy z funkcjami wirtualnymi.

Jeśli chodzi o sortowanie Dag, przechodzisz przez każdy DagNode od lewej do prawej. Innymi słowy, podążaj za lewą krawędzią DagNodes, a następnie za prawą krawędzią boczną. Numery są przypisywane odwrotnie. Innymi słowy, kiedy osiągniesz DagNode bez dzieci, przypisz temu węzłowi bieżący numer sortowania i zwiększ numer sortowania, aby rekurencja rozwinęła liczby przypisane w kolejności rosnącej.

Ten przykład obsługuje tylko drzewa z węzłami, które mają zero lub dwoje dzieci. Oczywiście niektóre drzewa mają węzły z więcej niż dwojgiem dzieci, więc logika jest nadal taka sama. Zamiast obliczać od lewej do prawej, obliczaj od lewej do prawej itd.

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

Jeśli wiesz, jakie drzewa są w programowaniu, wtedy DAG w programowaniu są podobne, ale pozwalają węzłowi mieć więcej niż jednego rodzica. Może to być przydatne, gdy chcesz, aby węzeł znajdował się pod czymś więcej niż tylko jednym rodzicem, ale nie masz problemu z zawiązanym bałaganem na ogólnym wykresie z cyklami. Nadal możesz łatwo nawigować po DAG, ale istnieje wiele sposobów, aby wrócić do katalogu głównego (ponieważ może być więcej niż jeden rodzic). Pojedynczy DAG może generalnie mieć wiele korzeni, ale w praktyce lepiej jest trzymać się jednego korzenia, jak drzewo. Jeśli rozumiesz dziedziczenie pojedyncze i wielokrotne w OOP, znasz drzewo kontra DAG. Odpowiedziałem już na to tutaj .

Nazwa mówi ci większość tego, co powinieneś wiedzieć o jego definicji: jest to wykres, na którym każda krawędź płynie tylko w jednym kierunku, a kiedy zejdziesz po krawędzi, twoja ścieżka nigdy nie wróci do wierzchołka, który właśnie opuściłeś.

Nie mogę mówić o wszystkich zastosowaniach (Wikipedia pomaga w tym), ale dla mnie DAG są niezwykle przydatne przy określaniu zależności między zasobami. Na przykład mój silnik gry reprezentuje wszystkie załadowane zasoby (materiały, tekstury, shadery, zwykły tekst, przeanalizowany plik JSON itp.) Jako pojedynczy DAG. Przykład:

Materiał to programy N GL, z których każdy potrzebuje dwóch shaderów, a każdy shader potrzebuje źródła shadera w postaci zwykłego tekstu. Reprezentując te zasoby jako DAG, mogę łatwo przeszukiwać wykres pod kątem istniejących zasobów, aby uniknąć podwójnych obciążeń. Załóżmy, że chcesz, aby kilka materiałów korzystało z programów do cieniowania wierzchołków z tym samym kodem źródłowym. Ponowne ładowanie źródła i rekompilowanie shaderów do każdego użycia jest marnotrawstwem, gdy można po prostu ustanowić nową przewagę istniejącego zasobu. W ten sposób możesz również użyć wykresu, aby określić, czy cokolwiek zależy od zasobu, a jeśli nie, usunąć go i zwolnić pamięć, w rzeczywistości dzieje się to prawie automatycznie.

W związku z tym DAG są przydatne do wyrażania potoków przetwarzania danych. Acykliczny charakter oznacza, że ​​możesz bezpiecznie pisać kod przetwarzania kontekstowego, który może podążać za wskaźnikami w dół po krawędziach od wierzchołka, bez ponownego napotkania tego samego wierzchołka. Wizualne języki programowania, takie jak VVVV , Max MSP lub interfejsy oparte na węzłach Autodesk Maya, opierają się na DAG.

Skierowany graf acykliczny jest przydatny, gdy chcesz przedstawić ... skierowany graf acykliczny! Przykładem kanonicznym jest drzewo genealogiczne lub genealogia.