Visualizzazione dei risultati da 1 a 6 su 6

Hybrid View

  1. #1
    Prima di tutto grazie ancora!
    Poi di seguito ti metto le funzioni per l'inserimento di nodi e archi come hai chiesto:

    codice:
    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 è:
    codice:
    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!


    codice:
    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
    Ultima modifica di Mattia423; 19-08-2019 a 11:35

  2. #2
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,589
    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:
    codice:
    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.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2025 vBulletin Solutions, Inc. All rights reserved.