Różne sposoby wdrożenia DAG w java

Question

Jestem wykonawczych DAG i zastanawiasz się, czy po to jedyna droga do reprezentowania go w Javie:

class Node{ 
List<Node> parents; 
List<Node> successors; 
int value; } 

class DAG{ 
Node root; // assuming only one root exists 
} 

szukam czegoś prostszego bez dwóch list do rodziców i dzieci.
czy to możliwe? Mam również problem z tą reprezentacją, że gdy dotarłem do określonego węzła x i chciałem ścieżki od x do węzła głównego, w jaki sposób mogę ją znaleźć bez przechodzenia przez wszystkie ustawione zestawy?

Answer 1

Aby uprościć kierowaną strukturę wykresów, nie jest konieczne, aby węzły miały odsyłacze do swoich przodków. Chciałbym również umieścić klasę węzła wewnątrz twojej klasy DAG. Koncepcyjnie ta reprezentacja ma więcej sensu, ponieważ na grafie skierowanym, jeśli węzeł A łączy się z węzłem B, nie musi istnieć ścieżka od B do A. W rzeczywistości nie może istnieć ścieżka w obu kierunkach, ponieważ byłby to cykl.

public class DAG { 
    Node root; // assuming only one root exists 

    public static class Node{ 
     List<Node> successors; 
     int value; 
    } 
} 

Aby znaleźć ścieżkę od korzenia do danego węzła, to trzeba uruchomić algorytm przeszukiwania grafu. Oznacza to możliwość odwiedzania innych węzłów na wykresie, prawdopodobnie rekurencyjnie, aż zlokalizujesz dany węzeł. Jeśli chcesz uniknąć powtarzania tego rodzaju obliczeń, można również zapisać ścieżkę z korzenia do danego węzła z mniej więcej tak:

class PathMap { 
    HashMap<DAG.Node, List<DAG.Node> > pathMap; 

    public List<DAG.Node> getPathFromRoot(DAG.Node n) { 
    List<DAG.Node> pathFromRoot = pathMap.get(n); 
    return pathFromRoot; 
    } 
} 

Teraz może być kilka różnych ścieżek od korzenia do A dany węzeł. W takim przypadku możesz zaimplementować shortest-path-first algorithm, aby znaleźć i zapisać optymalną ścieżkę. Zobacz ten kod: dzone article dla pseudokodowania.

Answer 2

To, czy uzasadnione jest upuszczenie listy rodziców, zależy od typowego przypadku użycia. Jak zauważył Thorn, w zasadzie można upuścić rodziców w DAG, ponieważ są one dorozumiane przez dzieci (lub rodziców). Jeśli jednak w aplikacjach często trzeba znaleźć przodka (ów) danego węzła, listy nadrzędne mogą pomóc w szybkim wykonaniu tego algorytmu (ponieważ nie zawsze trzeba zaczynać od korzenia i potencjalnie przechodzić cały wykres, zamiast cofać się tak daleko, jak to konieczne od danego węzła).

Dodałbym to jako komentarz do odpowiedzi Thorn, ale nie mam wystarczającej liczby przedstawicieli, aby to skomentować. Więc dołącz to w swojej odpowiedzi.