PROBLEMA Creazione Matrice di Adiacenza da Grafo

NotFound

Nuovo Utente
2
0
Salve a tutti. Sviluppando un progetto in linguaggio C, ho creato la lista di adiacenza del grafo per poterci poi lavorare su. Andando avanti mi sono accorto che necessito anche della matrice di adiacenza (al fine di utilizzare l'algoritmo di Floyd Warshall). Ho cercato tra le discussioni passate ma niente mi ha chiarito le idee. Come è strutturata la funzione per la creazione della matrice di adiacenza? Ho bisogno di definire nuovi tipi di dati? Posso eventualmente "tramutare" la mia funzione per la lista di adiacenza e renderla utile per l'acquisizione della matrice di adiacenza?

In due parole il funzionamento di questa parte del programma è che la prima funzione che vi posto, riconosce se abbiamo la necessità di inserire in lista uno oppure due vertici del grafo e agisce di conseguenza invocando la funzione giusta ("inserimento singolo" oppure "inserimento doppio"), reitera fino alla fine dell'inserimento del grafo nella lista. L'ultima funzione è quella per l'inserimento del grafo. Posto anche le definizioni dei tipi di dati che ho implementato.



So di chiedervi tanto,ho rimurginato parecchio sulla situazione ma non ne vengo a capo. Spero qualcuno possa aiutarmi! Grazie!

Definizioni dei tipi di dati che ho implementato.
Codice:
/*Definizione del tipo di dato per i vertici del grafo*/
typedef struct vertice_grafo
{
    char nome[DIM_NOME];                    /*Nome del vertice*/
    struct vertice_grafo *vertice_succ_p;            /*Puntatore al vertice successivo*/
    struct arco_grafo *lista_archi_p;            /*Puntatore alla testa della lista degl'archi*/
    colore_t colore;                    /*Variabile contenente il colore del vertice*/
    int distanza,                        /*Variabile contenente la distanza del vertice dalla sorgente*/
        inizio,                        /*Variabile per la visita in profondità*/
        fine;                        /*Variabile per la visita in profondità*/
    struct vertice_grafo *padre_p;                /*Puntatore al vertice padre*/
} vertice_t;


/*Definizione tipo di dato per gli archi*/
typedef struct arco_grafo
{
    struct vertice_grafo *vertice_adiac_p;                /*Puntatore al vertice di destinazione puntato dall'arco*/
    struct arco_grafo *arco_succ_p;                    /*Puntatore all'arco successivo*/
} arco_t;


/*Definizione tipo di dato per gli elementi della coda (per la visita in ampiezza)*/
typedef struct elem_coda
{
    struct vertice_grafo *elem;            /*Puntatore all'elemento del grafo*/
    struct elem_coda *elem_succ_p;            /*Puntatore all'elemento successivo della coda*/
} elem_coda_t;


/*Definizione del nuovo tipo di dato per gli elementi della pila (per visita in profondità e per memorizzare i padri)*/
typedef struct elem_pila
{
    char nome[DIM_NOME];                    /*Nome del vertice (vertice padre)*/
    struct elem_pila *elem_succ_p;                /*Puntatore all'elemento successivo*/
} elem_pila_t;



Funzione che riconosce se abbiamo la necessità di inserire in lista uno oppure due vertici del grafo e agisce di conseguenza invocando la funzione giusta
Codice:
/*Definizione della funzione per la ricerca della presenza o meno dei vertici*/
vertice_t *ricerca_vertici(vertice_t *p,
                char nome_vertice_origine[DIM_NOME],
                char nome_vertice_destinazione[DIM_NOME])
{
    /*Definizione delle variabili locali della funzione*/
    int origine = 1;
    char evento = 'b';                                /*Variabile che indicherà l'evento*/
    vertice_t *vertice_origine = NULL,                        /*Puntatore all'elemento d'origine*/
                *vertice_destinazione = NULL,                /*Puntatore all'elemento di destinazione*/
                *temp;                            /*Puntatore d'appoggio temporaneo*/


    /*Legenda "evento"
    'a' = entrambi i vertici sono presenti in lista
    'b' = nessuno dei due vertici è presente in lista
    'c' = solo il vertice d'origine è presente in lista
    'd' = solo il vertice di destinazione è presente in lista*/    


    /*Memorizzo la testa della lista*/
    temp = p;


    /*Se la lista non è vuota*/
    if (p != NULL)
    {
        /*Istruzione While che scorre la lista*/
        while ((p != NULL) &&
                (evento == 'b'))
        {
            /*Controllo se l'elemento corrente risulta essere la vertice d'origine*/
            if (strcmp(p->nome, nome_vertice_origine) == 0)
            {
                /*Memorizzo la vertice d'origine*/
                vertice_origine = p;
                /*Cambio di evento*/
                evento = 'c';
                /*Vado alla ricerca della vertice di destinazione*/
                while ((p != NULL) &&
                        (evento == 'c'))
                {
                    if (strcmp(p->nome, nome_vertice_destinazione) == 0)
                    {
                        /*Memorizzo il vertice di destinazione*/
                        vertice_destinazione = p;
                        /*Cambio evento*/
                        evento = 'a';
                    }
                    else
                        /*Aggiorno il puntatore e scorro la lista*/
                        p = p->vertice_succ_p;
                }
            }
            /*Altrimenti controllo se l'elemento corrente risulta essere il vertice di destinazione*/
            else if (strcmp(p->nome, nome_vertice_destinazione) == 0)
            {
                /*Memorizzo il vertice di destinazione*/
                vertice_destinazione = p;
                /*Cambio di evento*/
                evento = 'd';
                /*Vado alla ricerca del vertice d'origine*/
                while ((p != NULL) &&
                        (evento == 'd'))
                {
                    if (strcmp(p->nome, nome_vertice_origine) == 0)
                    {
                        /*Memorizzo il vertice d'origine*/
                        vertice_origine = p;
                        /*Cambio di evento*/
                        evento = 'a';
                    }
                    else
                        /*Aggiorno il puntatore e scorro la lista*/
                        p = p->vertice_succ_p;
                }
            }
            /*Se non è nessuna deli due*/
            else
                /*Aggiorno il puntatore e scorro la lista*/
                p = p->vertice_succ_p;
        }
    }
    /*Sezione di controllo dell evento ed invocazione della corrispettiva funzione*/
    switch (evento)
    {
        case 'a':
        /*Invoco la funzione creazione dell'arco */
        inserimento_arco(vertice_origine,
                    vertice_destinazione);


        break;
        
        case 'b':
        temp = inserimento_doppio(temp,
                    nome_vertice_origine,
                    nome_vertice_destinazione);
        break;


        case 'c':
        origine = 1;
        temp = inserimento_singolo(temp,
                    vertice_origine,
                    nome_vertice_destinazione,
                    origine);
        break;


        case 'd':
        origine *= 0;
        temp = inserimento_singolo(temp,
                    vertice_destinazione,
                    nome_vertice_origine,
                    origine);
        break;
    }
    return (temp);
}

Funzione per l'inserimento di un solo vertice
Codice:
/*Definizione della funzione per l'inserimento di un solo elemento nella lista dei vertici*/
vertice_t *inserimento_singolo(vertice_t *p,
                    vertice_t *elem_trovato,
                    char nome_vertice[DIM_NOME],
                    int origine)
{
    /*Definizione delle variabili locali della funzione*/
    vertice_t *nuovo_p,                            /*Puntatore al nuovo elemento*/
            *corr_p;                        /*Puntatore d'ausilio per scorrere la lista*/


    nuovo_p = corr_p = p;
    /*Scorro la lista fino ad arrivare all'ultimo elemento*/
    while (nuovo_p != NULL)
    {
        corr_p = nuovo_p;
        nuovo_p = nuovo_p ->vertice_succ_p;
    }
    /*Alloco spazio per il nuovo elemento*/
    nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
    /*Inserisco il nome*/
    strcpy(nuovo_p->nome, nome_vertice);
    nuovo_p->lista_archi_p = NULL;
    /*Concateno il nuovo elemento col resto della lista*/
    corr_p->vertice_succ_p = nuovo_p;
    /*Invoco la funzione per la creazione degli archi per il grafo*/
    inserimento_arco(elem_trovato,
                nuovo_p);
    return (p);
}

Funzione per l'inserimento di entrambi i vertici analizzati
Codice:
/*Definizione della funzione per l'inserimento di entrambi i vertici nella lista dei vertici*/
vertice_t *inserimento_doppio(vertice_t *p,
                char nome_vertice_origine[DIM_NOME],
                char nome_vertice_destinazione[DIM_NOME])
{
    /*Definizione delle variabili locali della funzione*/
    vertice_t *nuovo_p,                            /*Puntatore al nuovo elemento*/
                *seguente_p,                    /*Puntatore all'elemento seguente*/
                *corr_p;                    /*Puntatore d'ausilio per scorrere la lista*/


    /*Se la lista dovesse esser vuota*/
    if (p == NULL)
    {
        /*Creo la testa della lista*/
        nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
        /*Inserisco il nome*/
        strcpy(nuovo_p->nome, nome_vertice_origine);
        nuovo_p->lista_archi_p = NULL;
        /*Il nuovo elemento è la testa*/
        p = nuovo_p;
        /*Creo l'elemento seguente*/
        seguente_p = (vertice_t *)malloc(sizeof(vertice_t));
        /*Inserisco il nome*/
        strcpy(seguente_p->nome, nome_vertice_destinazione);
        seguente_p->lista_archi_p = NULL;
        /*Concateno l'elemento seguente*/
        p->vertice_succ_p = seguente_p;
    }
    /*Se non vuota*/
    else
    {
        nuovo_p = corr_p = p;
        /*Scorro la lista fino ad arrivare all'ultimo elemento*/
        while (nuovo_p != NULL)
        {
            corr_p = nuovo_p;
            nuovo_p = nuovo_p->vertice_succ_p;
        }
        /*Creo il nuovo elemento*/
        nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
        /*Inserisco il nome*/
        strcpy(nuovo_p->nome, nome_vertice_origine);
        nuovo_p->lista_archi_p = NULL;
        /*Concateno il nuovo elemento col resto della lista*/
        corr_p->vertice_succ_p = nuovo_p;


        /*Creo l'elemento seguente*/
        seguente_p = (vertice_t *)malloc(sizeof(vertice_t));
        /*Inserisco il nome*/
        strcpy(seguente_p->nome, nome_vertice_destinazione);
        seguente_p->lista_archi_p = NULL;
        /*Concateno l'elemento seguente*/
        nuovo_p->vertice_succ_p = seguente_p;
    }


    /*Invoco la funzione per la creazione degl'archi per il grafo)*/
    inserimento_arco(nuovo_p,
                seguente_p);        
    return (p);
}



Funzione per l'inserimento degli archi in lista
Codice:
/*Definizione della funzione per la creazione degli archi*/
void inserimento_arco(vertice_t *vertice_origine,
                    vertice_t *vertice_destinazione)
{
    /*Definizione delle variabili locali della funzione*/
    int controllo = 1 ;                        /*Variabile di controllo generale*/
    arco_t *arco,                            /*Puntatore al nuovo arco*/
        *arco_corr;                        /*Puntatore d'ausilio per scorrere la lista degl'archi*/


    if (vertice_origine->lista_archi_p == NULL)
    {
        /*Creo l'arco*/
        arco = (arco_t *)malloc(sizeof(arco_t));
        /*Lo inserisco nella lista secondaria*/
        vertice_origine->lista_archi_p = arco;
        /*Inserisco il vertice adiacente*/
        arco->vertice_adiac_p = vertice_destinazione;
        /*Non ho un arco successivo*/
        arco->arco_succ_p = NULL;


        arco = arco_corr = vertice_origine->lista_archi_p;
        /*Scorro la lista secondaria degl'archi*/
        while ((arco != NULL) &&
                (controllo == 1))
        {
            arco_corr = arco;
            /*Controllo se l'arco che voglio inserire è già presente*/
            if (strcmp(arco->vertice_adiac_p->nome, vertice_destinazione->nome) == 0)
            {
                controllo *= 0;
            }
            /*Altrimenti*/
            else
                /*Scorro la lista*/
                arco = arco->arco_succ_p;
        }
        /*Testo la variabile controllo per constatare se poter inserire o meno l'arco*/
        if (controllo == 1)
        {
            /*Creo l'arco*/
            arco = (arco_t *)malloc(sizeof(arco_t));
            /*Lo inserisco come ultimo elemento*/
            arco_corr->arco_succ_p = arco;
            /*Definisco il vertice adiacente*/
            arco->vertice_adiac_p = vertice_destinazione;
            /*Non ho archi successivi*/
            arco->arco_succ_p = NULL;


        }
    }
}
 
Ultima modifica:

lpleo

Nuovo Utente
33
10
Prendi quello che dico con la dovuta cautela perché non sono riuscito a riguardare il libro di algoritmi.
Se non mi ricordo male e se ho capito bene il problema, tu vuoi creare una matrice di adiacenza dato un grafo, il che è abbastanza semplice.
Seguendo questi esempi (eng-wiki) puoi vedere facilmente come una matrice di adiacenza non sia nient'altro che la rappresentazione del grafo in maniera matriciale.
Le coordinate sono l'arco (es la coordinata 1 x 5 indica un arco dal nodo 1 al nodo 5), il valore invece rappresenta l'esistenza o meno dell'arco . Quindi se c'è uno in quelle coordinate esiste un arco tra i due nodi, altrimenti se c'è uno zero l'arco non esiste.

Guardando la pagina di wikipedia al link che ti ho indicato sopra ci sono anche degli esempi.
 

NotFound

Nuovo Utente
2
0
Grazie per avermi risposto. Esatto è quello il mio problema. Solo che vorrei sapere come procedere in termini di programmazione. Perché volevo recuperare la mia funzione per la lista di adiacenza, oppure farne una nuova apposita per la matrice di adiacenza. Ho ben chiaro quale sia la definizione, ma quando cerco di implementarla mi blocco e non capisco come procedere. Per quello volevo una linea guida all'implementazione in sé. Ho trovato sul web alcune funzioni in pseudo codice, ma non riesco a ricavarne nulla. :cav:
 
Ultima modifica:

lpleo

Nuovo Utente
33
10
Secondo me la strada più facile è creare la matrice di adiacenza in una nuova funzione, poiché ti serve il grafo finito. Una volta che hai finito di scrivere il grafo, crei in memoria una matrice di dimensione N*N (o se vuoi salvare in memoria anche il nome del nodo, (N+1 * N+1), con N = numero di nodi). A questo punto visiti il grafo. Per ogni nodo guardi se ha archi e verso che nodi. Una volta che hai ottenuto questa informazione, nel punto relativo (riga X nodo di partenza, colonna Y nodo di destinazione), scrivi 1 nel punto (X,Y).

Puoi anche creare la matrice di adiacenza "a runtime" cioè mentre crei il grafo, ma la cosa si complica un pochino perché hai a che fare con una matrice dinamica.

Se ancora non ti viene in mente un modo di implementarla, prova a mettere giù qualcosa. Mi viene più facile correggere del codice che capire la tua logica (tra l'altro se non erro questa è solo una parte del programma) e scrivere una funzione da zero.
 

Ci sono discussioni simili a riguardo, dai un'occhiata!

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili