Dopo questa domanda , la soluzione per risolvere l'associazione dei dati è quella di utilizzare DFS e Ordinamento topologico . Non sono esattamente sicuro di cosa significhi. Ecco un'animazione che dimostra approssimativamente ciò che sto considerando.
Supponiamo di avere un modello di associazione dati come questo:
●
↓
● → ● → ● → ● ● ← ●
↑ ↑ ↓
● → ● → ● ← ● → ●
↓ ↓ ↑
● ● → ● ← ●
↓ ↓
● ●
↑
●
E poi cambiamo un campo.
●
↓
● → ● → ● → ● ● ← ●
↑ ↑ ↓
◌ → ● → ● ← ● → ●
↓ ↓ ↑
● ● → ● ← ●
↓ ↓
● ●
↑
●
Quindi si propaga:
●
↓
● → ● → ◌ → ● ● ← ●
↑ ↑ ↓
○ → ◌ → ● ← ● → ●
↓ ↓ ↑
◌ ● → ● ← ●
↓ ↓
● ●
↑
●
piu '...
●
↓
● → ● → ○ → ◌ ● ← ●
↑ ↑ ↓
○ → ○ → ◌ ← ● → ●
↓ ↓ ↑
○ ● → ● ← ●
↓ ↓
● ●
↑
●
...
●
↓
● → ● → ○ → ○ ◌ ← ●
↑ ↑ ↓
○ → ○ → ○ ← ● → ●
↓ ↓ ↑
○ ◌ → ● ← ●
↓ ↓
● ●
↑
●
●
↓
● → ● → ○ → ○ ○ ← ●
↑ ↑ ↓
○ → ○ → ○ ← ● → ●
↓ ↓ ↑
○ ○ → ◌ ← ●
↓ ↓
◌ ●
↑
●
●
↓
● → ● → ○ → ○ ○ ← ●
↑ ↑ ↓
○ → ○ → ○ ← ◌ → ●
↓ ↓ ↑
○ ○ → ○ ← ●
↓ ↓
○ ◌
↑
●
●
↓
● → ● → ○ → ○ ○ ← ●
↑ ↑ ↓
○ → ○ → ○ ← ☀ → ◌
↓ ↓ ↑
○ ○ → ○ ← ●
↓ ↓
○ ○
↑
●
A volte incontra un aggiornamento recente, come mostrato con ☀. Ma continua:
●
↓
● → ● → ○ → ○ ○ ← ●
↑ ↑ ↓
○ → ○ → ○ ← ○ → ○
↓ ↓ ↑
○ ○ → ○ ← ●
↓ ↓
○ ○
↑
●
Ora non ha più avuto cambiamenti, quindi torna allo stato invariato.
●
↓
● → ● → ● → ● ● ← ●
↑ ↑ ↓
● → ● → ● ← ● → ●
↓ ↓ ↑
● ● → ● ← ●
↓ ↓
● ●
↑
●
Quindi, in questo processo, ci sono alcune cose:
- Tutti i nodi entrano in uno stato "modificato", fino a quando tutti i nodi sono stati modificati.
- In qualche modo si scopre che tutti i nodi che verranno modificati sono stati modificati. Ciò gli consente di tornare nello stato "invariato".
Questo grafico è abbastanza semplificato perché in realtà potrebbero esserci molti cicli complicati e molti altri collegamenti per nodo.
Tuttavia, dato che le frecce indicano la direzione in questo grafico ciclico orientato, mi chiedo come questo algoritmo possa eseguire efficientemente questa propagazione degli aggiornamenti.
L'approccio ingenuo dovrebbe scorrere tutti i nodi che hanno cambiato ogni passaggio, per vedere se c'è qualcosa da cambiare. Forse c'è un terzo stato, "cambiato e non più propagazione". Una volta che tutto è in quel terzo stato (controllando ogni nodo ogni passaggio), allora sarebbe fatto. Ti chiedi se esiste un modo efficace per farlo, quindi non ha bisogno di scorrere ogni nodo in ogni passaggio.
Inoltre, è possibile che più valori vengano modificati contemporaneamente, quindi dovrebbe essere in grado di gestirli ugualmente, cioè:
●
↓
● → ● → ● → ● ● ← ◌
↑ ↑ ↓
◌ → ● → ● ← ● → ●
↓ ↓ ↑
● ● → ● ← ●
↓ ↓
● ◌
↑
●
