Sto cercando (o sto tentando di progettare) una tecnica per la corrispondenza di nodi con grafici molto simili basati sulla struttura del grafico *. Negli esempi seguenti, il grafico in alto ha 5 nodi e il grafico in basso ha 6 nodi. Vorrei abbinare i nodi dal grafico superiore ai nodi nel grafico in basso, in modo che i nodi "0" corrispondano, e i nodi "1" corrispondano, ecc. Questo sembra logicamente possibile, perché posso farlo nel mio testa per questi semplici esempi. Ora ho solo bisogno di esprimere la mia intuizione nel codice. Esistono algoritmi o schemi stabiliti che potrei prendere in considerazione?
(* Quando dico in base alla struttura del grafico, voglio dire che la soluzione non dovrebbe dipendere dalle etichette del nodo, le etichette numeriche sui nodi sono solo per dimostrazione.)
AGGIORNAMENTO: è stato correttamente sottolineato che usando solo la struttura, la maggior parte di questi grafici non può essere risolta con una precisione del 100%. Ho aggiunto alcune considerazioni su ciascun grafico.
Sono anche interessato alle prestazioni di qualsiasi potenziale soluzione. Quanto bene saranno in scala? Posso unire grafici con milioni di nodi?
In casi più complessi, riconosco che la soluzione migliore può essere soggetta a interpretazione. Comunque, spero in un "buon" modo di unire grafici complessi.
(Questi sono i grafici diretti, la porzione più spessa di un bordo rappresenta la testa.)
Questograficoèunciclocon1nodo"collegato all'esterno". Dopo aver collegato un secondo nodo all'esterno, non è possibile determinare se il nuovo nodo (nodo 5) è collegato al nodo 1 o 3. I 4 nodi che compongono il ciclo non possono essere perfettamente uguagliati.
Inodi1e5possonoesserescambiatinelgraficoinbassosenzamodificarelastruttura.Pertanto,puoisoloindovinareconunaprecisione50/50cheèilnuovonodo.
Questo ultimo grafico è l'unico per il quale è possibile identificare il nuovo nodo con una precisione del 100%.
Grazie Kirk Broadhurst, per averlo indicato.