Ordinamento: quale struttura!?

[Absolut]

Ciao ragazzi, avrei una domanda da sottoporvi.

Mettiamo che io abbia una topologia di rete con nodi: A,B,C,D,E, F,G,H,I,L,M
Che sappia che A è direttamente collegato direttamente con con B e C, che B lo sia con A, D, E e via dicendo. Ovvero che io sappia chi è collegato a chi.

Ora voglio estrarli secondo il criterio "numero massimo di connessioni", ma con alcuni vincoli ovvero.

Inizialmente vedo che B è quello che ha il maggior nmero di connessioni. Allora levo dalla lista dei nodi B e tutti i vicini di B
A questo punto volgio trovare quello con maggior numerodi connessioni, senza tener conto di B e tutti i suoi vicini.

Quale struttura dovrei utilizzare per fare questo ordinamento!? e quale sarebbe il suo costo computazionale!?

vi ringrazio!

[m0rdr3d]

Non mi sono molto chiare alcune cose:

• Tu vuoi ordinare tutti i nodi in ordine di grado decrescente?
• Se ho capito bene, una volta estratto B, i nodi vicini non vengono più considerati, ma questo vuol dire che non faranno parte dell'ordinamento? E se due nodi vicini fossero di grado massimo ed uguale?
• Il dominio del problema, ovvero il numero di nodi, è noto a priori? Questo potrebbe incidere fortemente sull'approccio utilizzato e sulla complessità finale.

[Absolut]

Il numero di nodi è noto a priori.

Se hanno lo stesso grado, si prendoo in ordine alfabetico

Estratto B e i suoi vicini... questi non fanno più parte dell'ordinamento!

[targzeta]

Non so che ordinamento vuoi fare, ma in questi casi si usano le matrici di adiacenza.

Emanuele

[Absolut]

Ovvio per sapere i vicini....
Io intendevo struttre per gestire l'ordinamento.... so di heap binarie ordinate.... ma non so esattamente se fanno al caso mio!

[targzeta]

L'ho detto io che non ho capito che ordinamento vuoi fare. Da quello che hai scritto sembra che il primo nodo deve essere quello con più link, poi non si capisce bene che fine fanno i suoi vicini, e poi sembra che il secondo nodo debba essere quello che, una volta tolto il quello con più link ed i suoi vicini, rimane quello con più link .

Per questa soluzione va bene una matrice di adiacenza.
Emanuele

[Absolut]

Allora esattamente faccio questo:

1) Ordino i nodi in modo decrescente secondo node_degree
2) Estraggo il primo e tutti i suoi vicini, e li elimino dalla lista.
3) Eseguo nuovamente l'ordinamento
4) levo il primo e i suoi vicini dalla lista.....
e cosi via.....

Al primo passaggio, una volta levato il nodo con più vicini (chiamiamolo X) devo fare l'ordinamento di nuovo perchè il secondo della lista(chiamiamolo Y) potrebbe essere un vicino di X e verrebbe levato. Oppure Y occupava la seconda posizione, ma visto che ora levo X e tutti i suoi vicini... magari alcuni di questi erano vicini di Y e ora Y stesso andrebbe ad occupare una nuova posizione!


scusatemi ragazzi, ma non sono esperto in queste cose.....

[targzeta]

Quello che ancora non capisco è che fine facciano i vicini. Supponiamo che abbiamo questa situazione:

Codice: Seleziona tutto

A->B
B->C
C->D

Seguo il tuo ragionamento. B e C hanno entrambe due connessioni, Quindi prendo B, tolgo A e C. Quindi mi rimane solo D. Il risultato?

Codice: Seleziona tutto

B, D

?

Emanuele

[Absolut]

Esatto.. i vicini li butti..... come se non ci fossero più..... il problema ora è gestire una rete con 500 nodi e 6000 links, insomma quest'ordine di grandezza.....

[targzeta]

E perchè la matrice di adiacenza non ti basta? Oltre a dirti i vicini ti dice anche quanti link possiede. Ordini una sola volta i link che possiedono tutti i nodi e poi agisci di conseguenza. Prendi quello con il maggior numero di link, elimini i suoi vicini e riprendi il primo.
Non so se mi sono spiegato ma la matrice di adiacenza ti da già un vettore di questo tipo:

Codice: Seleziona tutto

A = 20
C = 12
E = 10
B = 8
D = 6

Quindi tu prendi il primo (A), scandisci la matrice per trovare i sui vicini e li elimini dal risultato, poi prendi di nuovo il primo etc...

Emanuele

[m0rdr3d]

A questo punto non potrebbe essere più efficace utilizzare la rappresentazione a liste?
La complessità asintotica non cambia, ma ti permette di diminuire notevolmente il numero di nodi che controlli quando vai ad eliminare i vicini.

[Absolut]

boh.. nn saprei... secondo voi cosa è meglio!?

[targzeta]

Se la matrice di adiacenza la implementi come si deve, ovvero come una mappa di bit, l'individuazione dei vicini risulta molto veloce.

Emanuele