TAD Grafo

/* CABECERA */

#ifndef GRAFO_H
#define GRAFO_H

typedef int TElemento;

typedef struct nodoArista{
    TElemento elem;
    int peso;
    struct nodoArista* ptrSig;
}TNodoArista;

typedef struct nodoVertice{
    TElemento elem;
    TNodoArista *inicio;
    struct nodoVertice* ptrSig;
}TNodoVertice;

typedef struct{
    TNodoVertice *inicio;
}TGrafo;

void crearGrafo(TGrafo*);

void insertarArista(TGrafo*,TElemento,TElemento,int);
void insertarVertice(TGrafo*,TElemento);

int existeArista(TGrafo*,TElemento,TElemento);
int existeVertice(TGrafo*,TElemento);

void eliminarArista(TGrafo*,TElemento,TElemento);
void eliminarVertice(TGrafo*,TElemento);

void imprimirGrafo(TGrafo*);

int numVertices(TGrafo*);

#endif  /* GRAFO_H */





/* IMPLEMENTACION */

#include <stdio.h>
#include <stdlib.h>
#include "grafo.h"

void crearGrafo(TGrafo*grafo){
    grafo->inicio = NULL;
}

void insertarVertice(TGrafo*grafo,TElemento v){
    if (!existeVertice(grafo,v)){
        TNodoVertice *ptrNuevoVertice;
        ptrNuevoVertice = (TNodoVertice*)malloc(sizeof(TNodoVertice));
        ptrNuevoVertice->elem = v;
        ptrNuevoVertice->inicio = NULL;

        ptrNuevoVertice->ptrSig = grafo->inicio;
        grafo->inicio = ptrNuevoVertice;
    }
}

void insertarArista(TGrafo*grafo,TElemento v1,TElemento v2,int peso){
    if (!existeArista(grafo,v1,v2)){
        insertarVertice(grafo,v1);
        insertarVertice(grafo,v2);

        TNodoVertice* ptrRecVertice;
        ptrRecVertice = grafo->inicio;
        while(ptrRecVertice && ptrRecVertice->elem != v1)
            ptrRecVertice = ptrRecVertice->ptrSig;

        TNodoArista* ptrNuevaArista;
        ptrNuevaArista = (TNodoArista*)malloc(sizeof(TNodoArista));
        ptrNuevaArista->elem = v2;
        ptrNuevaArista->peso = peso;

        ptrNuevaArista->ptrSig = ptrRecVertice->inicio;
        ptrRecVertice->inicio = ptrNuevaArista;
    }
}

int existeArista(TGrafo*grafo,TElemento v1,TElemento v2){
    if (existeVertice(grafo,v1)==0)
        return 0;
    else{
        if(existeVertice(grafo,v2)==0)
            return 0;
        else{
            TNodoVertice *ptrRecVertice;
            ptrRecVertice = grafo->inicio;
            while(ptrRecVertice && ptrRecVertice->elem != v1)
                ptrRecVertice = ptrRecVertice->ptrSig;
            TNodoArista* ptrRecArista;
            ptrRecArista = ptrRecVertice->inicio;
            while(ptrRecArista){
                if (ptrRecArista->elem == v2)
                    return 1;
                ptrRecArista = ptrRecArista->ptrSig;
            }
            return 0;
        }
    }
}

int existeVertice(TGrafo*grafo,TElemento v){
    TNodoVertice *ptrRecVertice;
    ptrRecVertice = grafo->inicio;

    while(ptrRecVertice && ptrRecVertice->elem != v)
        ptrRecVertice = ptrRecVertice->ptrSig;

    if (ptrRecVertice == NULL)
        return 0;
    else
        return 1;
}

void eliminarArista(TGrafo*grafo,TElemento v1,TElemento v2){
    TNodoVertice * ptrRecVertice;
    if (existeArista(grafo,v1,v2)){
        ptrRecVertice = grafo->inicio;
        while(ptrRecVertice && ptrRecVertice->elem != v1)
            ptrRecVertice = ptrRecVertice->ptrSig;

        TNodoArista *ptrRecArista, *ptrAnt, *ptrEliminar;
        ptrRecArista = ptrRecVertice->inicio;
        ptrAnt = NULL;
        while(ptrRecArista && ptrRecArista->elem != v2){
            ptrAnt = ptrRecArista;
            ptrRecArista = ptrRecArista->ptrSig;
        }
        if (ptrAnt == NULL){
            ptrEliminar = ptrRecVertice->inicio;
            ptrRecVertice->inicio = ptrRecVertice->inicio->ptrSig;
        }else{
            ptrEliminar = ptrRecArista;
            ptrAnt->ptrSig = ptrRecArista->ptrSig;
        }
        free(ptrEliminar);
    }
}

void eliminarVertice(TGrafo*grafo,TElemento v){
    if (existeVertice(grafo,v)){
        TNodoVertice *ptrRecVertice, *ptrAntVertice, *ptrEliminar;
        ptrRecVertice = grafo->inicio;
        ptrAntVertice = NULL;

        while(ptrRecVertice && ptrRecVertice->elem != v){
            ptrAntVertice = ptrRecVertice;
            ptrRecVertice = ptrRecVertice->ptrSig;
        }

        TNodoArista *ptrRecArista,*ptrEliminarArista;
        ptrRecArista = ptrRecVertice->inicio;
        while(ptrRecArista){
            ptrEliminarArista = ptrRecVertice->inicio;
            ptrRecArista = ptrRecArista->ptrSig;
            free(ptrEliminarArista);
        }

        if (ptrAntVertice == NULL){
            ptrEliminar = grafo->inicio;
            grafo->inicio = grafo->inicio->ptrSig;
        }
        else{
            ptrEliminar = ptrRecVertice;
            ptrAntVertice->ptrSig = ptrRecVertice->ptrSig;
        }
        free(ptrEliminar);

        ptrRecVertice = grafo->inicio;
        while(ptrRecVertice){
            ptrRecArista = ptrRecVertice->inicio;
            while(ptrRecArista){
                if (ptrRecArista->elem == v)
                    eliminarArista(grafo,ptrRecVertice->elem,v);
                ptrRecArista = ptrRecArista->ptrSig;
            }
            ptrRecVertice = ptrRecVertice->ptrSig;
        }
    }
}

void imprimirGrafo(TGrafo*grafo){
    TNodoVertice *ptrRecVertice;
    TNodoArista *ptrRecArista;
    ptrRecVertice = grafo->inicio;
    while(ptrRecVertice){
        printf("V: %2d\n       A:",ptrRecVertice->elem);
        ptrRecArista = ptrRecVertice->inicio;
        while(ptrRecArista){
            printf("% 2d w:%d",ptrRecArista->elem,ptrRecArista->peso);
            ptrRecArista = ptrRecArista->ptrSig;
        }
        printf("  NULL\n");
        ptrRecVertice = ptrRecVertice->ptrSig;
    }
}

int numVertices(TGrafo*grafo){
    TNodoVertice *ptrRecVertice;
    ptrRecVertice = grafo->inicio;
    int cont = 0;

    while(ptrRecVertice){
        cont++;
        ptrRecVertice = ptrRecVertice->ptrSig;
    }
    return cont;
}





/* MAIN */

#include <stdio.h>
#include <stdlib.h>
#include "grafo.h"

int main(int argc, char** argv) {

    TGrafo grafo;

    crearGrafo(&grafo);

    insertarVertice(&grafo,5);
    insertarVertice(&grafo,4);
    insertarVertice(&grafo,3);
    insertarVertice(&grafo,2);
    insertarVertice(&grafo,1);

    insertarArista(&grafo,5,1,2);
    insertarArista(&grafo,4,1,1);
    insertarArista(&grafo,4,2,1);
    insertarArista(&grafo,4,3,1);
    insertarArista(&grafo,4,5,1);

    insertarArista(&grafo,11,1,6);
    insertarArista(&grafo,10,13,1);

    imprimirGrafo(&grafo);

    eliminarVertice(&grafo,4);
    eliminarArista(&grafo,5,1);
    imprimirGrafo(&grafo);

    return (EXIT_SUCCESS);
}