fleury_algorithm

//
//  main.c
//  fleury_algorithm
//
//  Created by Henrique de Almeida on 10/12/2018.
//  Copyright © 2018 Henrique de Almeida. All rights reserved.
//

//Graph
//6 9
//1 2
//1 4
//1 3
//1 5
//2 4
//3 4
//3 6
//3 5
//4 6

# include <stdio.h>
# include <stdlib.h>
# define MAX 50

typedef enum { false, true } bool;

typedef struct edge{
    int firstNode;
    int secondNode;
}Edge;

typedef struct edgeArray{
    int size;
    Edge edges[12];
}EdgeArray;

int main(int argc, const char * argv[]) {
    
    FILE *arq;
    char *arquivo = "entrada.txt";
    int i, j, arestas, vertices, aux;
    int grafo[MAX + 1][MAX + 1];
    int grau[MAX + 1];
    i = 0;
    j = 0;
    
    // Inicialização das matrizes com -1
    for(j = 0; j <= MAX; j++)
        for(i = 0; i <= MAX; i++){
            
            grafo[j][i] = -1;
        }
    
    for (i = 0; i <= MAX; i++){
        
        grau[i] = 0;
    }
    
    arq = fopen(arquivo, "r");
    
    if(arq == 0) {
        perror("fopen");
        exit(1);
    }
    
    fscanf(arq, "%i", &vertices);
    fscanf(arq, "%i", &arestas);
    
    // Tratamento da entrada
    if(vertices > MAX){
        printf("\nO numero de vertices deve ser <= %i\n", MAX);
        exit(1);
    }
    
    // Inicializacão da matriz
    for(i = 0; i <= vertices; i++)
        for (j = 0; j <= vertices; j++){
            
            grafo[i][j] = 0;
        }
    aux = arestas;
    i = 0;
    j = 0;
    
    // Colocando as arestas na matriz
    EdgeArray edgeArray;
    int index = 0;
    while (aux > 0){
        fscanf(arq, "%i", &i);
        fscanf(arq, "%i", &j);
        grafo[i][j] = 1;
        grafo[j][i] = 1;
        aux--;
        
        //Código de Henrique (vulgo, eu)
        edgeArray.edges[index].firstNode = i;
        edgeArray.edges[index].secondNode = j;
        edgeArray.size++;
        
        index++;
    }
    
    // Calculando o grau dos vertices
    for (i = 1; i <= MAX; i++)
        for(j = 0; j <= MAX; j++){
            
            if (grafo[i][j] == 1){
                grau[i]++;
            }
        }
    
    // Verificando a quantidade de vertices com grau impar
    j = 2;
    aux = 0;
    for(i = 1; i <= MAX; i++){
        
        if(grau[i]%j != 0){
            aux++;
            grau[i] = -1;
        }
    }
    
    // Classificação do grafo
    if (aux == 0){
        printf("\nTodos os vertices possuem grau par, portanto o grafo é Euleriano.\n");
    }
    else{
        if (aux == 2){
            printf("\nExistem 2 vertices com grau impar, portanto o grafo é Semi-Euleriano.\n");
        }
        else{
            printf("\nExiste(m) %i vertice(s) com grau impar, portanto ", aux);
            printf("o grafo não é Euleriano e nem Semi-Euleriano.\n");
        }
    }
    printf("\n");
    
    //Fleury's Algorithm
    int path[arestas + 1];
    int currentVertex = 1;
    int position = 0;
    path[position] = currentVertex;
    bool isLastVertex = false;
    int vertex = 1;
    while (position <= arestas && vertex <= vertices) {
        if (vertex != currentVertex) {
            if (grafo[currentVertex][vertex] == 1) {
                if ((grau[vertex] > 1) || (grau[vertex] == 1 && isLastVertex)) {
                    //Remove edge from graph
                    grafo[currentVertex][vertex] = 0;
                    grafo[vertex][currentVertex] = 0;
                    grau[vertex]--;
                    grau[currentVertex]--;
                    currentVertex = vertex;
                    position++;
                    path[position] = currentVertex;
                    //Check if it's the last vertex standing
                    if (position == arestas - 1) {
                        isLastVertex = true;
                    }
                    vertex = 1;
                } else {
                    vertex++;
                }
            } else {
                vertex++;
            }
        } else {
            vertex++;
        }
    }
    printf("O caminho Euleriano é: \n\n");
    for (int i = 0; i <= arestas; i++) {
        if (i != arestas) {
            printf("(%i)->", path[i]);
        } else {
            printf("(%i)", path[i]);
        }
    }
    printf("\n\n");
    return 0;
}