Ricerca del nodo principale nel grafico aciclico diretto

1

Ho implementato un algoritmo di condivisione strutturale per la creazione di alberi persistenti in stile Clojure, ma si basa sul nodo figlio che conosce il proprio genitore.

function fork
  return new Node
    children: this.children
    value: this.value
    parent: this.parent.fork()

Se si chiama fork su un nodo nell'albero, verrà creato un nuovo nodo, con un genitore biforcuto, in modo ricorsivo fino alla radice. In questo modo puoi prendere qualsiasi nodo, cambiarlo e quindi avere accesso a una versione immutabile dell'intero albero.

Tuttavia, l'idea fondamentale per questa struttura di dati è che dovrebbe essere un grafo aciclico diretto, con un riferimento a un genitore che fornisce i cicli del grafico. Ho anche avuto alcuni problemi con la creazione del nuovo genitore. Il nodo dovrebbe conoscere il genitore biforcuto, ma per forzare il genitore dovrebbe sapere del suo nuovo figlio. Questo è praticamente una dipendenza circolare, ma sono riuscito a eluderlo con alcuni riferimenti e mutazione.

C'è un modo più sano per farlo?

    
posta Dan Prince 07.09.2015 - 15:45
fonte

0 risposte

Leggi altre domande sui tag