[C] Adiacenza nei grafi

[-hide-]

Il mio problema è riscontrato all'interno di questo esercizio:
Un dispositivo di rete è composto dalle seguenti strutture: una coda circolare (in grado di memorizzare N pacchetti), un grafo G=(V,E) (rappresentato mediante liste di adiacenza), due pile (pila A e pila B). Ogni pacchetto è caratterizzato da un indirizzo_mittente (un intero comperso tra 0 e V-1), un indirizzo_destinatario (un intero compreso tra 0 e V-1) ed un campo payload di tipo generico struct data.
Compito del dispositivo è quello di smistare i pacchetti prelevandoli (mediante un ciclo infinito) dalla coda circolare ed inserendoli nelle pile in base alla topologiia del grafo. In particolare, i pacchetti in cui il mittente è un vicino del destinatario devono essere inoltrati sulla pila A, tutti gli altri sulla pila B.
Descrivere la struttura dati ed implementare le funzioni principali in lungiaggio C.

Ciò su cui vorrei un aiuto è la parte in grassetto. Non riesco a scoprire i vicini di un particolare nodo (in tal caso mittente), perché in una struttura del tipo:
for (n = adj[mittente]; n != NULL; n = n->next) {
/* qualcosa qui dentro */
}
n = n->next non fa cambiare il nodo sul quale si ricercano i vicini?

[oNaSsIs]

Il problema potrebbe essere risolto in diversi modi, però secondo me una soluzione semplice potrebbe essere aggiungere un campo hop intero all'interno della struttura pacchetto, ammesso che l'esercizio conceda la possibilità di modificare tale struttura. In questo modo utilizzi il campo hop come un contatore che conta il numero di salti, ossia il numero di nodi che il pacchetto attraversa, se hop=1 e il pacchetto è arrivato a destinazione significa che il destinatario è proprio un vicino.
Considera che il campo hop esiste anche nella realtà, si chiama TTL (Time To Live) e viene utilizzato per evitare cicli infiniti da parte di un pacchetto.

In alternativa ti basta fare una scansione della lista di adiacenza del mittente prima di "spedire" il pacchetto.
Però la prima soluzione secondo me è più flessibile, perchè ti permette di avere anche ulteriori informazioni come ad esempio la distanza tra due nodi...

[-hide-]

Il problema potrebbe essere risolto in diversi modi, però secondo me una soluzione semplice potrebbe essere aggiungere un campo hop intero all'interno della struttura pacchetto, ammesso che l'esercizio conceda la possibilità di modificare tale struttura. In questo modo utilizzi il campo hop come un contatore che conta il numero di salti, ossia il numero di nodi che il pacchetto attraversa, se hop=1 e il pacchetto è arrivato a destinazione significa che il destinatario è proprio un vicino.
Considera che il campo hop esiste anche nella realtà, si chiama TTL (Time To Live) e viene utilizzato per evitare cicli infiniti da parte di un pacchetto.


Puoi farmi un esempio dell'utilizzo del campo hop, perché credo che il mio problema sia proprio nel capire quando effettua un salto.

[oNaSsIs]

Naturalmente il campo di ogni pacchetto sarà inizializzato a 0 e verrà incrementato ad ogni salto, ossia ogni volta che passi da un nodo all'altro e questa operazione tu la esegui proprio nel momento in cui scrivi:
n = n->next

[Don[ITA]]

Forse ho capito male io, ma non basta fare così??

coda Q;
pila A, B;
while(true) {
bool inserito := false;
pacchetto P := dequeue(Q); //estraggo il pacchetto dalla coda
int adjp := adj[P.mittente]; //prendo gli adiacenti del mittente
for(i := 0 to adjp.length) //scorro gli adiacenti del mittente
if(P.destinatario == adjp[i]) then //se il destinatario è tra gli adiacenti del mittente
enqueue(P, A) //lo inserisco in A
inserito := true;
break;
if(!inserito) then
enqueue(P, B) //altrimenti lo inserisco in B
inserito := false;
} //fine ciclo infinito

Ovviamente è "pseudocodice" ma dovresti capirlo abbastanza facilmente.
Questa è solo una bozza per rendere l'idea, ma se è corretta dovresti anche essere in grado di sistemarla a tuo piacimento :)

Spero di aver capito bene!!! :doh:

Cya

[oNaSsIs]

Questa è l'alternativa che avevo suggerito nel primo post:

In alternativa ti basta fare una scansione della lista di adiacenza del mittente prima di "spedire" il pacchetto.
Però la prima soluzione secondo me è più flessibile, perchè ti permette di avere anche ulteriori informazioni come ad esempio la distanza tra due nodi...
Però guardando il tuo pseudocodice forse l'esercizio è più semplice di quello che io pensavo, perchè ero convinto che comunque bisognava simulare l'intero cammino,ma se non è così allora consiglio anche io questa soluzione, in alternativa se invece il cammino va effettivamente simulato reputo la prima migliore...

[tuccio`]

Il mio problema è riscontrato all'interno di questo esercizio:


Ciò su cui vorrei un aiuto è la parte in grassetto. Non riesco a scoprire i vicini di un particolare nodo (in tal caso mittente), perché in una struttura del tipo:
for (n = adj[mittente]; n != NULL; n = n->next) {
/* qualcosa qui dentro */
}
n = n->next non fa cambiare il nodo sul quale si ricercano i vicini?se adj[mittente], come immagino, è la lista dei nodi adiacenti al nodo mittente.. perché dovrebbe? |: