skull87
25-01-2009, 20:47
Ciao a tutti, sto affrontando da qualche giorno il problema del calcolo della media dei cammini minimi tra tutte le coppie di vertici, e quindi dei cammini minimi tra tutte le coppie di vertici, per un grafo non orientato e non pesato che come struttura base è circolare:
http://www.galileonews.it/files/Small-World-Network.gif
Ho letto svariato materiale sull'argomento, ma finora non sono riuscito a trovare una soluzione valida per risolvere il problema.
Una di queste pagine è: http://people.hofstra.edu/geotrans/eng/ch1en/meth1en/shimbelmatrix.html
Ho provato ad implementare il prodotto delle matrici in questo modo, ditemi se sbaglio:
C2=C1*C1 --> Aggiorno D come indicato, solo se il valore cambia da 0 a >0
C3=C1*C2 -->
C4=C2*C3
C5=C3*C4
....... e così in avanti finchè nella matrice D non finiscono gli zeri e di conseguenza non trovo tutte le distanze. Ho implementato il codice ottimizzando l'utilizzo di matrici, data la struttura di grafo non orientato tutte le informazioni sono memorizzabili all'interno di un solo triangolo della matrice, ma senza i risultati sperati. Ho provato, partendo da questa matrice di adiacenza per un grafo di 10 vertici:
0100000001
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
0000000001
0000000000
ad effettuare i prodotti tra le matrici ed aggiornare la matrice D anche usando Matlab, purtroppo però mi trovo che fino alla distanza 3 tutto va bene, poi mi viene valutata la distanza tra 0 e 5 uguale a 4, cosa non vera dato che dovrebbe valere 5.
Vi prego di aiutarmi per questa strada, se corretta, oppure di segnalarmi un algoritmo più efficiente per la struttura su cui devo lavorare. Vi ringrazio tantissimo, online ho trovato svariato materiale, ma sinceramente è tutto molto complesso. So dell'esistenza dell'algoritmo di Seidel che però utilizza la ricorsione, e tra l'altro non ne ho trovate implementazioni. Mi rimetto alla vostra esperienza.
Grazie 1000.:muro:
http://www.galileonews.it/files/Small-World-Network.gif
Ho letto svariato materiale sull'argomento, ma finora non sono riuscito a trovare una soluzione valida per risolvere il problema.
Una di queste pagine è: http://people.hofstra.edu/geotrans/eng/ch1en/meth1en/shimbelmatrix.html
Ho provato ad implementare il prodotto delle matrici in questo modo, ditemi se sbaglio:
C2=C1*C1 --> Aggiorno D come indicato, solo se il valore cambia da 0 a >0
C3=C1*C2 -->
C4=C2*C3
C5=C3*C4
....... e così in avanti finchè nella matrice D non finiscono gli zeri e di conseguenza non trovo tutte le distanze. Ho implementato il codice ottimizzando l'utilizzo di matrici, data la struttura di grafo non orientato tutte le informazioni sono memorizzabili all'interno di un solo triangolo della matrice, ma senza i risultati sperati. Ho provato, partendo da questa matrice di adiacenza per un grafo di 10 vertici:
0100000001
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
0000000001
0000000000
ad effettuare i prodotti tra le matrici ed aggiornare la matrice D anche usando Matlab, purtroppo però mi trovo che fino alla distanza 3 tutto va bene, poi mi viene valutata la distanza tra 0 e 5 uguale a 4, cosa non vera dato che dovrebbe valere 5.
Vi prego di aiutarmi per questa strada, se corretta, oppure di segnalarmi un algoritmo più efficiente per la struttura su cui devo lavorare. Vi ringrazio tantissimo, online ho trovato svariato materiale, ma sinceramente è tutto molto complesso. So dell'esistenza dell'algoritmo di Seidel che però utilizza la ricorsione, e tra l'altro non ne ho trovate implementazioni. Mi rimetto alla vostra esperienza.
Grazie 1000.:muro: