grafo.c 5.86 KB
Newer Older
Vytor Calixto's avatar
Vytor Calixto committed
1 2 3
#include <stdlib.h>
#include "grafo.h"
#include "lista.h"
4
#include "filha.h"
Vytor Calixto's avatar
Vytor Calixto committed
5 6
#include "vertice.h"
#include "tabuleiro.h"
7
#include <stdio.h>
Vytor Calixto's avatar
Vytor Calixto committed
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Grafo criaGrafo() {
    Grafo g = malloc(sizeof(struct Grafo));

    g->vertices = constroiLista();
    return g;
}

Vertice insereVertice(Grafo g, Vertice v) {
    if(insereLista(v, g->vertices)) {
        return v;
    }
    return NULL;
}

void criaArco(Vertice v, Vertice w) {
Vytor Calixto's avatar
Vytor Calixto committed
24 25
    insereUnicoLista(w, v->filhos);
    insereUnicoLista(v, w->pais);
Vytor Calixto's avatar
Vytor Calixto committed
26 27
}

28
/* Algoritmo recursivo
29
Para cada celula do tabuleiro, indo da esquerda pra direita, de cima pra baixo.
30 31
    Verifica se essa célula já foi visitada, se sim, retorna.
    Se não, cria um vertice para ela e chama o algoritmo FLoodfill(celula, vertice) recursivo para esta celula
32 33 34


Floodfill(celula, vertice)
35 36 37 38 39 40 41
    atrela o vertice a este.
    visita este
    se nenhum dos vizinhos eh da mesma cor ou se os vizinhos da mesma cor ja tiverem vertices, entao
        retorna.
    se algum dos vizinhos for da mesma cor, chama
        floodfill(vizinho de mesma cor, vertice)
    retorna
42 43 44 45
-----------------------------------------------------------
*/

void tabuleiroParaGrafo(Tblr t, Grafo g) {
46 47 48
    g->x = t->x;
    g->y = t->y;
    g->cores = t->cores;
49
    //Para cada celula do tabuleiro
Vytor Calixto's avatar
Vytor Calixto committed
50 51
    for(int i=0; i < t->x; ++i) {
        for(int j=0; j < t->y; ++j) {
52 53 54 55
            Celula c = t->celulas[i * t->y +j];
            //Verifica se essa célula já foi visitada
            if(c->vert == NULL){
                //Se não, cria um vertice para ela e chama o algoritmo FLoodfill(celula, vertice) recursivo para esta celula
56 57
                // Crio um vértice para mim
                Vertice v = criaVertice();
Vytor Calixto's avatar
Vytor Calixto committed
58
                v->cor = c->cor;
59
                v->peso = 0;
Vytor Calixto's avatar
Vytor Calixto committed
60
                insereVertice(g, v);
61 62
                //Chama o flood fill
                floodFill(t, v, i, j);
Vytor Calixto's avatar
Vytor Calixto committed
63
            }
64

65 66 67
            // A célula tendo um vértice, criamos os arcos pros vizinhos
            Celula cima, baixo, esq, dir;
            //Cima
Vytor Calixto's avatar
Vytor Calixto committed
68 69
            if(i > 0) {
                cima = t->celulas[(i-1) * t->y + j];
70
                if(cima->vert && cima->cor != c->cor) {
71
                    criaArco(cima->vert, c->vert);
72
                    criaArco(c->vert, cima->vert);
Vytor Calixto's avatar
Vytor Calixto committed
73 74
                }
            }
75 76 77 78 79 80
            // Esquerda
            if(j > 0) {
                esq = t->celulas[i * t->y + (j - 1)];
                if(esq->vert && esq->cor != c->cor) {
                    criaArco(esq->vert, c->vert);
                    criaArco(c->vert, esq->vert);
Vytor Calixto's avatar
Vytor Calixto committed
81 82 83 84 85
                }
            }
            // Baixo
            if(i < t->x - 1) {
                baixo = t->celulas[(i + 1) * t->y + j];
86
                if(baixo->vert && baixo->cor != c->cor) {
87
                    criaArco(baixo->vert, c->vert);
88
                    criaArco(c->vert, baixo->vert);
Vytor Calixto's avatar
Vytor Calixto committed
89 90
                }
            }
91 92 93 94 95 96
            // Direita
            if(j < t->y - 1) {
                dir = t->celulas[i * t->y + (j + 1)];
                if(dir->vert && dir->cor != c->cor) {
                    criaArco(dir->vert, c->vert);
                    criaArco(c->vert, dir->vert);
Vytor Calixto's avatar
Vytor Calixto committed
97 98 99 100
                }
            }
        }
    }
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
}

void floodFill(Tblr t, Vertice v, int i, int j){
    Celula c = t->celulas[i * t->y + j];

    // Se a cor da célula é diferente da do vértice retorna
    if(c->cor != v->cor) return;
    // Se a célula já tem um vértice, retorna
    if(c->vert) return;

    // Se as cores são iguais...
    c->vert = v;
    v->peso = v->peso + 1;

    //Cima
    if(i > 0) {
        floodFill(t, v, (i-1), j);
    }
    // Esquerda
    if(j > 0) {
        floodFill(t, v, i, (j-1));
    }
    // Baixo
    if(i < t->x - 1) {
        floodFill(t, v, (i+1), j);
    }
    // Direita
    if(j < t->y - 1) {
        floodFill(t, v, i, (j+1));
    }
Vytor Calixto's avatar
Vytor Calixto committed
131 132
    return;
}
133

134 135
int calculaAltura(Grafo g, Lista raiz) {
    int alturaMax = 0;
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
    for(No n = primeiroNoLista(g->vertices); n; n = getSucessorNo(n)) {
        Vertice v = (Vertice) getConteudo(n);
        v->altura = -1;
    }

    Filha fila = constroiFilha();
    for(No n = primeiroNoLista(raiz); n; n = getSucessorNo(n)) {
        Vertice v = (Vertice) getConteudo(n);
        v->altura = 0;
        insereFilha(v, fila);
    }

    while(tamanhoFilha(fila) > 0) {
        No n = primeiroNoFilha(fila);
        if(!n) {
            continue;
        };
        Vertice v = (Vertice) getConteudo(n);
        for(No m = primeiroNoLista(v->filhos); m; m = getSucessorNo(m)) {
            Vertice filho = (Vertice) getConteudo(m);
            if(filho->altura == -1) {
                filho->altura = v->altura+1;
158 159 160
                if(filho->altura > alturaMax) {
                    alturaMax = filho->altura;
                }
161 162 163
                insereFilha(filho, fila);
            }
        }
164
        free(n);
165
    }
166 167
    destroiFilha(fila, NULL);
    return alturaMax;
168 169
}

170 171 172 173 174
void destroiGrafo(Grafo g) {
    destroiLista(g->vertices, destroiVertice);
    free(g);
    g = NULL;
    return;
Vytor Calixto's avatar
Vytor Calixto committed
175
}
176 177 178 179 180 181 182 183 184 185 186

void grafoParaDot(Grafo g, Lista grupo, FILE* fp) {
    fprintf(fp, "strict graph g {\n");
    // Pinta os nós que estão no grupo de vermelho
    for(No n = primeiroNoLista(grupo); n; n = getSucessorNo(n)) {
        Vertice v = (Vertice) getConteudo(n);
        fprintf(fp, "\t\"%p\" [color=red];\n", v);
    }
    // Imprime o grafo
    for(No n = primeiroNoLista(g->vertices); n; n = getSucessorNo(n)) {
        Vertice pai = (Vertice) getConteudo(n);
187
        fprintf(fp, "\t\"%p\" [label=\"cor=%d\npeso=%d\nbonus=%lu\naltura=%d\"];\n", pai, pai->cor, pai->peso, pai->bonus, pai->altura);
188 189
        for(No m = primeiroNoLista(pai->filhos); m; m = getSucessorNo(m)) {
            Vertice filho = (Vertice) getConteudo(m);
190
            fprintf(fp, "\t\"%p\" [label=\"cor=%d\npeso=%d\nbonus=%lu\naltura=%d\"];\n", filho, filho->cor, filho->peso, filho->bonus, filho->altura);
191 192 193 194 195
            fprintf(fp, "\t\"%p\" -- \"%p\";\n", pai, filho);
        }
    }
    fprintf(fp, "}\n");
}