ED - Ficha Grafos V1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct grafo
{
    int N, N2;
    int NRamos;
    int *Matriz; // Vai ter N*N casas
}Grafo;

typedef struct no
{
    int Info;
    struct no *Next;
}NO;
typedef struct lista_int
{
    NO *Inicio;
    int Nelementos;
}Lista_Int;

//---------------------------------------------------
void wait(int mlseconds)
{
    clock_t endwait;
    endwait = clock() + mlseconds;
    while(clock() < endwait) {}
}
//---------------------------------------------------
void spaces(int n)
{
    int i;

    for(i = 0; i < n; i++)
        printf("   ");
    return;
}

Grafo *CriarGrafo(int nl)
{
    Grafo *G = (Grafo *)malloc(sizeof(Grafo));
    G->N = nl;
    G->N2 = nl*nl;
    G->NRamos = 0;
    G->Matriz = (int *)malloc(sizeof(int)*nl*nl);
    return G;
}

void DestruirGrafo(Grafo *G)
{
    if(!G)
        return;
    free(G->Matriz);
    free(G);
}

Grafo *PreencherGrafo(char *nficheiro)
{
    Grafo *res = NULL;
    FILE *f = fopen(nficheiro, "r");
    char buffer[200];
    int nos;

    if(f)
    {
        fscanf(f, "%d", &nos);
        res = CriarGrafo(nos);
        for(int i=0; i < res->N2; i++)
            fscanf(f, "%d", &res->Matriz[i]);
    }
    fclose(f);
    return res;
}
/** \brief MostrarGrafo: Fun??o que permite visualizar os dados de um grafo no ecran
* \param G : Grafo
* \return void
*/
void MostrarGrafo(Grafo *G)
{
    printf("\n");
    if(!G)
        return;
    for(int i=0; i < G->N; i++)
    {
        for(int n=0; n < G->N; n++)
        {
            printf("%d", G->Matriz[i*G->N + n]);
            spaces(1);
            if(n >= i && G->Matriz[i*G->N + n] != 0)
                G->NRamos++;
        }
        printf("\n");
    }
    printf("\n");
}
/** \brief DensidadeGrafo: Densidade de um Grafo
*
* \param G : Grafo
* \return void
*/
void DensidadeGrafo(Grafo *G)
{
    if(!G)
        return;
    printf("\nA densidade do grafo é: %f\n\n", 2 * G->NRamos / G->N);
}
/** \brief GrauGrafo : Grau de um Grafo: ? o maior n?mero de liga??es de um n?
*
* \param G : Grafo
* \return void
*
*/
void GrauGrafo(Grafo *G)
{
    if(!G)
        return;

    int nlig;
    int max=0;

    for(int i=0; i < G->N; i++)
    {
        nlig=0;
        for(int n=i; n < G->N; n++)
            if(G->Matriz[i*G->N + n] != 0)
                nlig++;
        if(nlig > max)
            max = nlig;
    }
    printf("\nO grau do grafo e: %d", max);
}

/** \brief GravarFicheiroRAM
*
* \param nficheiro : Nome do ficheiro a gravar
* \param  G : Grafo
* \return void
*
*/
void GravarFicheiroRAM(char *nficheiro, Grafo *G)
{
    if(!G)
        return;

    FILE *f = fopen(nficheiro, "w");
    fprintf(f, "%d\n", G->N);
    fprintf(f, "%d\n", G->NRamos);
    for(int i=0; i < G->N; i++)
        for(int n=i; n < G->N; n++)
            if(G->Matriz[i*G->N + n] != 0)
                fprintf(f, "%d %d %d\n", i, n, G->Matriz[i*G->N + n]);

    fclose(f);
}

/** \brief AdicionarArcoGrafo: Dados dois Nos e o custo, faz a liga??o entre os n?s
*
* \param G Grafo*
* \return void
*
*/
void AdicionarArcoGrafo(Grafo *G)
{
    int n1, n2, c;
    printf("\nInsira o numero dos nos que quer ligar: ");
    scanf("%d %d", &n1, &n2);
    printf("\nInsira o custo da ligcao: ");
    scanf("%d", &c);

    if(G->Matriz[n1 * G->N + n2] != 0)
        printf("\nArco ja existente!");
    else
        G->Matriz[n1 *G->N + n2] = G->Matriz[n2 * G->N + n1] = c;
}

/** \brief RemoverArcoGrafo: Dados dois Nos remove a liga??o entre os n?s
*
* \param G Grafo*
* \return void
*
*/
void RemoverArcoGrafo(Grafo *G)
{
    int n1, n2;
    printf("\nInsira o numero dos nos que quer remover a ligacao: ");
    scanf("%d %d", &n1, &n2);

    if(G->Matriz[n1 * G->N + n2] == 0)
        printf("\nArco inexistente!");
    else
        G->Matriz[n1 *G->N + n2] = G->Matriz[n2 * G->N + n1] = 0;
}


void ListaAddVal(Lista_Int *L, int v)
{
    if(!L)
        return;
    NO *novo = (NO *)malloc(sizeof(NO));
    novo->Info = v;
    novo->Next = NULL;
    NO *n = L->Inicio;
    if(!n)
    {
        L->Inicio =novo;
        L->Nelementos++;
    }
    else
    {
        while(n->Next)
            n = n->Next;
        n->Next = novo;
        L->Nelementos++;
    }
}

Lista_Int *copylist(Lista_Int *L)
{
    Lista_Int *NL = (Lista_Int*)malloc(sizeof(Lista_Int));
    NL->Inicio = NULL;
    NL->Nelementos = 0;
    NO *a = L->Inicio;
    while(a)
    {
        ListaAddVal(NL, a->Info);
        a=a->Next;
    }
    return NL;
}

bool isinlist(Lista_Int *L, int v)
{
    if(!L)
        return false;
    NO *n = L->Inicio;
    while(n)
    {
        if(n->Info == v)
            return true;
        n=n->Next;
    }
    return false;
}

void DestruirLista(Lista_Int *L)
{
    if(!L)
        return;
    NO *n = L->Inicio;
    NO *a;
    while(n)
    {
        a = n->Next;
        free(n);
        n = a;
    }
    free(L);
}

int IrCaminho(Grafo *G, int ni, int nf, Lista_Int **LHistorico, int *custo)
{
    ListaAddVal(*LHistorico, ni);
    if(ni == nf)
        return 1;

    Lista_Int *aux = NULL;
    int maxcusto=0;
    int c;
    for(int i=0; i < G->N; i++)
    {
        if(!isinlist(*LHistorico, i) && G->Matriz[ni *G->N + i] != 0)
        {
            Lista_Int *Copy = copylist(*LHistorico);

            c = *custo + G->Matriz[ni *G->N + i];

            if(IrCaminho(G, i, nf, &Copy, &c) == 1 && aux == NULL || c < maxcusto)
            {
                DestruirLista(aux);
                maxcusto = c;
                aux = Copy;
            }
            else
                DestruirLista(Copy);
        }
    }
    if(aux != NULL)
    {
        *LHistorico = aux;
        *custo = maxcusto;
        return 1;
    }
    return 0;
}
int IrTodosCaminhos(Grafo *G, int ni, int nf, Lista_Int **LHistorico, int *custo)
{
    ListaAddVal(*LHistorico, ni);
    if(ni == nf)
    {
        NO *a = (*LHistorico)->Inicio;
        while(a)
        {
            printf("%d > ", a->Info);
            a=a->Next;
        }
        printf("\n");
        return 1;
    }

    Lista_Int *aux = NULL;
    int maxcusto=0;
    int c;
    for(int i=0; i < G->N; i++)
    {
        if(!isinlist(*LHistorico, i) && G->Matriz[ni *G->N + i] != 0)
        {
            Lista_Int *Copy = copylist(*LHistorico);

            c = *custo + G->Matriz[ni *G->N + i];

            if(IrTodosCaminhos(G, i, nf, &Copy, &c) == 1 && aux == NULL || c < maxcusto)
            {
                DestruirLista(aux);
                maxcusto = c;
                aux = Copy;
            }
            else
                DestruirLista(Copy);
        }
    }
    if(aux != NULL)
    {
        *LHistorico = aux;
        *custo = maxcusto;
        return 1;
    }
    return 0;
}
/** \brief ConetividadeEntreNosGrafo : Calcula o caminho entre 2 n?s, invocando a Fun??o IrCaminho
*
* \param G Grafo*
* \return void
*
*/
void ConetividadeEntreNosGrafo(Grafo *G)
{
    int n1, n2;
    printf("Insira os nos que quer ligar: ");
    scanf("%d %d", &n1, &n2);
    Lista_Int *cam = (Lista_Int *)malloc(sizeof(Lista_Int));
    cam->Inicio = NULL;
    cam->Nelementos =0;
    int custo = 0;
    if(IrCaminho(G, n1, n2, &cam, &custo) == 1)
    {
        printf("Caminho encontrado:\n");
        NO *n = cam->Inicio;
        while(n)
        {
            printf("%d > ", n->Info);
            n=n->Next;
        }
        printf("\nCom custo de %d\n", custo);
        DestruirLista(cam);
    }
    else
        printf("Caminho nao encontrado\n");
}

/** \brief TodosCaminhosEntreNosGrafo : Fun??o que pede os 2 caminhos em quest?o e invoca o algoritmo
*                                      IrTodosCaminho
* \param G Grafo*
* \return void
*
*/
void TodosCaminhosEntreNosGrafo(Grafo *G)
{
    int n1, n2;
    printf("Insira os nos que quer ligar: ");
    scanf("%d %d", &n1, &n2);
    Lista_Int *cam = (Lista_Int *)malloc(sizeof(Lista_Int));
    cam->Inicio = NULL;
    cam->Nelementos =0;
    int custo = 0;
    IrTodosCaminhos(G, n1, n2, &cam, &custo);
    DestruirLista(cam);
}

/** \brief Menu :
*
* \return int
*
*/
int Menu()
{
    printf("1 - Ler Grafo de Ficheiro \n");
    printf("2 - Mostrar Grafo \n");
    printf("3 - Densidade de um Grafo \n");
    printf("4 - Grau de um Grafo \n");
    printf("5 - Gravar Grafo em Ficheiro RAM\n");
    printf("6 - Destruir Grafo\n");
    printf("7 - Adicionar Caminho entre 2 nos\n");
    printf("8 - Remover Caminho entre 2 nos\n");
    printf("9 - Conectividade entre 2 nos e o seu Custo\n");
    printf("10 - Todos Caminhos Possiveis entre 2 nos com todos os Custos\n");
    printf("0 - Sair\n");
    int opcao;
    printf("Qual a OPCAO ? : ");
    scanf(" %d", &opcao);
    return opcao;
}


/** \brief Main : Programa principal
*
* \param argc int
* \param argv[] char*
* \return int
*
*/
int main(int argc, char *argv[])
{
    printf("Inicio Parte 1\n \n");

    char Ficheiro[50];
    //sprintf(Ficheiro, "%s", "Dados\\grafo6");
    sprintf(Ficheiro, "%s", "grafo.txt");

    Grafo *G = NULL;
    G = PreencherGrafo(Ficheiro);
    int Opcao;
    do
    {
        Opcao = Menu();
        switch(Opcao)
        {
            case 1: DestruirGrafo(G);
                G = PreencherGrafo(Ficheiro);
                break;
            case 2: MostrarGrafo(G); break;
            case 3: DensidadeGrafo(G); break;
            case 4: GrauGrafo(G); break;
            case 5: GravarFicheiroRAM(Ficheiro, G); break;
            case 6: DestruirGrafo(G); G = NULL; break;
            case 7: AdicionarArcoGrafo(G); break;
            case 8: RemoverArcoGrafo(G); break;
            case 9: ConetividadeEntreNosGrafo(G); break;
            case 10: TodosCaminhosEntreNosGrafo(G); break;
        };
    } while(Opcao != 0);
    DestruirGrafo(G);
    printf("\nFim \n \n");
    return 0;
}