Diversi modi per implementare i DAG in java

Question

Io sono l'attuazione DAG e chiedendo se il seguente è l'unico modo per rappresentarlo in Java:

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

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

Sto cercando qualcosa di più semplice senza due liste per genitori e figli.
è possibile? Inoltre ho un problema con questa rappresentazione che se ho raggiunto un nodo particolare x e volevo il percorso da x al nodo radice, come posso trovarlo senza passare attraverso tutti i genitori impostati?

Answer 1

Per semplificare la struttura del grafico orientato, non è necessario che i nodi abbiano collegamenti ai rispettivi antenati. Metterei anche la classe Node nella tua classe DAG. Concettualmente questa rappresentazione ha più senso in ogni caso poiché in un grafo orientato, se il nodo A si collega al nodo B, non c'è bisogno di un percorso da B ad A. Infatti non ci può essere un percorso in entrambe le direzioni perché quello sarebbe un ciclo.

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

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

Per trovare il percorso dalla radice a un nodo particolare, è necessario eseguire un algoritmo per cercare nel grafico. Ciò significa che è possibile visitare gli altri nodi nel grafico, probabilmente in modo ricorsivo, finché non si individua il nodo specificato. Se si vuole evitare di ripetere questo tipo di calcoli, si potrebbe anche memorizzare il percorso dalla radice ad un dato nodo con qualcosa di simile:

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

Ora ci possono essere più diversi percorsi dalla radice ad un dato nodo In tal caso, è possibile implementare un valore shortest-path-first algorithm per trovare e memorizzare il percorso ottimale. Vedi questo dzone article per pseudocodice.

Answer 2

Se l'elenco dei genitori è ragionevole o meno, dipende dal tipico caso d'uso. Come ha sottolineato Thorn, in linea di principio puoi far cadere i genitori in un DAG poiché sono implicitamente dati dai bambini (o dai genitori). Tuttavia, se nelle vostre applicazioni spesso avete bisogno di trovare alcuni antenati di un dato nodo, gli elenchi genitori potrebbero aiutare a implementare un algoritmo veloce per farlo (poiché non avreste sempre bisogno di iniziare dalla root e potenzialmente attraversare l'intero grafico, invece andando indietro per quanto necessario dal nodo dato).

avrei aggiunto questo come commento alla risposta di Thorn, ma non ho abbastanza rep per commentare. Quindi sentiti libero di includerlo nella sua risposta.