PDA

Visualizza la versione completa : [C] indegree e outdegree


Mattia423
17-08-2019, 10:29
Buond, oggi voglio calcolare indegree e outdegree di un nuodo di un grafo.Che sono, rispettivamente, il numero di archi in entrata e in uscita dal nodo.

In pratica per l'out-degree del nodo la lunghezza della lista di adiacenza che parte dal nodo, dalla sua "head" per come l'ho definito io. Mentre l'indegree di un nodo il numero di volte che il nodo compare nella lista di adiacenza di qualche altro nodo.

Queste sono le due funzioni che ho creato io:


int outdegree (WGRAPH g, NODE x, int d){
LIST r;
if(g[x].visited){ //se stato usato
d=0; //la lunghezza della lista che parte dal nodo per ora 0
for(r = g[x].head; r != NULL; r = r->next){ //inizio a scorrere la lista che parte dal nodo (dalla sua head) fino alla fine
d += 1; //ogni volta che scorro la lista di una posizione conto il passaggio
}
return d;
}
return 0;
}

e


int indegree (WGRAPH g, NODE x){
int d;
LIST r;
int s = 0;
LIST p = g[x].head;
d = p->label; //d prende l'etichetta del nodo di cui voglio conoscere l'indegree
for(int j=0; j<MAX; j+=1){ //inizio a scorrere il grafo
if(g[j].used){ //se il nodo usato
for(r = g[j].head; r != NULL; r = r->next){ //inizio a scorrere la sua lista di adiacenza
if(r->label == d) //se trovo un valore in tale lista uguale all'etichetta del nodo di cui voglio l'indegree
s = s+1; //allora prendi nota incrementando di 1
}
}

}
return s;
}



C' sempre qualcosa che sbaglio perch mi compila, ma poi non mi calcola proprio nessuno dei due valori.
Inoltre per quel che riguarda l'indegree non capisco una cosa: e se esistono due nodi che hanno la stessa etichetta? In quel caso mi posso trovare in qualche lista di adiacenza lo stesso valore, ma che proviene da i due nodi diversi e cos mi falsa tutto. Quindi cosa dovrei fare in quel caso?

Grazie in anticipo a chiunque voglia aiutarmi (e un grazi ulteriore a Scara95 per l'altra volta) :unz:

Scara95
19-08-2019, 09:19
Potresti riportare la definizione di WGRAPH?

Mattia423
19-08-2019, 10:38
Hai ragione, me ne sono proprio dimenticato! Eccola qui:


typedef int NODE; // tipo di etichetta
typedef short int BOOLEAN; // 0=falso, 1=vero

typedef struct WGNODE* LIST; // lista di nodi adiacenti
struct WGNODE { // struttura di un nodo
NODE label; // etichetta del nodo
float weight; // peso dell'arco
LIST next; // nodi vicini
};
struct WGENTRY { // struttura di un entry point
BOOLEAN used; // 1 se utilizzato per un nodo
BOOLEAN visited; // 1 se visitato
int order; // numero d'ordine (v. acyclic)
int outdegree; // numero di outlink
LIST head; // lista di nodi adiancenti
};
typedef struct WGENTRY WGRAPH[MAX]; // un grafo pesato e' accessibile medianteun array di entry point da cui
// iniziano liste di nodi adiancenti

Scara95
19-08-2019, 11:34
Potresti riportare anche le funzioni di inserimento di archi e nodi?

In outdegree:

d non dovrebbe essere un argomento della funzione, ma ci non influisce sul calcolo.
la flag da controllare used (che segnala se il nodo utilizzato o non) e non visited (che se segnala se il nodo stato visitato durante un algoritmo di visita.
un valore pi corretto per il caso in cui non sia utilizzato -1. 0 un valore valido nel range della funzione (un nodo pu essere isolato o terminale), -1 non lo e segnala un errore


In indegree sbagliata la logica. Tu devi scorrere le liste di adiacenza di ogni nodo usato (come stai gi facendo) ma il confronto lo devi fare con la label di x che ti stato passato come parametro, che, per come implementato, x stesso. Infatti il nome di un nodo corrisponde all'indice che ha nell'array. Motivo per cui 2 nodi non possono avere lo stesso nome.

Attento comunque che potresti avere archi duplicati nelle liste di adiacenza. Come nota a margine non ti serve necessariamente scorrere tutta la lista per ogni nodo, infatti quando trovi un arco uscente verso il nodo di interesse, se il grafo ben costruito, non ne puoi trovare un altro uguale.

Mattia423
19-08-2019, 12:32
Prima di tutto grazie ancora!
Poi di seguito ti metto le funzioni per l'inserimento di nodi e archi come hai chiesto:


int add(WGRAPH g,NODE x){ // aggiungi un nodo x a g
NODE i = x % MAX; // etichetta "interna"
g[i].head = NULL; // all'inizio senza adiacenti
g[i].used = 1; // usato un elemento dell'array
g[i].visited = 0; // nodo non ancora visitato
g[i].order = 0; // ne' con un numero d'ordine
g[i].outdegree = 0; // privo di outlink
return i; // ritorna l'etichetta "interna"
} // e termina

void link(WGRAPH g,NODE i,NODE j,float w) { // aggiungi un arco (i,j) con peso w
LIST p = (LIST)malloc(sizeof(struct WGNODE)); // alloca una cella per l'arco
p->next = g[i].head; // collega la cella al nodo
g[i].head = p; // la cella diventa la testa
p->label = j; // assegna l'etichetta alla cella
p->weight = w; // memorizza il peso
g[i].outdegree += 1; // incrementa l'outdegree
} // termina

Poi per quel che riguarda outdegree, come hai giustamente notato, non ha senso che "d" sia un argomento della funzione e ho cambiato used con visited, questo stato un errore senza scusanti. Poi ho cambiato pure lo 0 con il -1 come hai suggerito perci il risultato :


int outdegree (WGRAPH g, NODE x){
int d;
LIST r;
if(g[x].used){ //se stato usato
d=0; //la lunghezza della lista che parte dal nodo per ora 0
for(r = g[x].head; r != NULL; r = r->next){ //inizio a scorrere la lista che parte dal nodo (dalla sua head) fino alla fine
d += 1; //ogni volta che scorro la lista di una posizione conto il passaggio
}
return d;
}
return -1;
}

Passiamo ora ad indegree ...
Se ho capito bene io complicavo solamente le cose, ti riposto il codice aggiustato. In pratica ho eliminato LIST p = g[x].head; e d = p->label; perch tanto posso confrontare r->label con x!



int indegree (WGRAPH g, NODE x){
LIST r;
int s = 0;
for(int j=0; j<MAX; j+=1){ //inizio a scorrere il grafo
if(g[j].used){ //se il nodo usato
for(r = g[j].head; r != NULL; r = r->next){ //inizio a scorrere la sua lista di adiacenza
if(r->label == x) //se trovo un valore in tale lista uguale all'etichetta del nodo di cui voglio l'indegree. QUESTO il cambiamento che ho fatto
s = s+1; //allora prendi nota incrementando di 1
}
}

}
return s;
}

Invece c' una cosa che non ho capito, ovvero quando dici "potresti avere archi duplicati nelle liste di adiacenza".
Mentre per l'ultimo suggerimento che mi hai lasciato faccio finta di non averlo neanche letto, non voglio complicarmi troppo le cose e preferisco che se le complichi il mio PC piuttosto:D

Scara95
19-08-2019, 16:33
Non ti serve calcolare outdegree (ovvero la lunghezza della list di adiacenza) perch l'hai gi salvato in g[i].outdegree che incrementi ogni volta che inserisci un arco.

Potresti avere archi duplicati nel senso che se io faccio:

link(g, 5, 7, 0.5);
link(g, 5, 7, 0.7);

Non c' nessun controllo sul reinserimento. Ho quindi due archi uscenti verso lo stesso modo (che sbagliato).

Quel x%MAX in add sbagliato per 2 motivi:

l'unica funzione in cui lo fai, perci se poi cerco un nodo con l'etichetta che ho usato per l'inserimento non detto che lo ritrovi
Non c' nessun controllo per le collisioni. Esempio supponiamo che MAX sia 100, io aggiungo 31, 631 e 131. Vengono tutti rappresentanti dalla stessa cella, scorrettamente.

Loading