BookClub/Grafo.cpp at main · liuvaneshka/BookClub · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include "Grafo.h"
#include <iostream>

Grafo::Grafo() {
    matriz_adyacencia = nullptr;
    vertices = new Lista<Lectura*>;
    algoritmo_arbol_expansion = nullptr;
}

void Grafo::agregar_vertice(Lectura* nuevo_vertice) {
    agrandar_matriz_adyacencia();
    vertices->alta(nuevo_vertice);
}

void Grafo::mostrar_grafo() {
    mostrar_vertices();
    mostrar_matriz_adyacencia();
}

void Grafo::agregar_camino(Lectura* origen, Lectura* destino, int peso) {
    int posicion_origen = vertices->obtener_posicion(origen);
    int posicion_destino = vertices->obtener_posicion(destino);

    matriz_adyacencia[posicion_origen][posicion_destino] = peso;
    matriz_adyacencia[posicion_destino][posicion_origen] = peso;
}

void Grafo::agrandar_matriz_adyacencia() {
    int** matriz_aux;
    int nueva_cant_vertices = vertices->obtener_tamanio() + 1;
    matriz_aux = new int*[nueva_cant_vertices];

    for(int i = 0; i < nueva_cant_vertices; i++){
        matriz_aux[i] = new int[nueva_cant_vertices];
    }

    copiar_matriz_adyacente(matriz_aux);
    inicializar_vertice(matriz_aux);
    liberar_matriz_adyacencia();
    matriz_adyacencia = matriz_aux;
}

void Grafo::copiar_matriz_adyacente(int** nueva_adyacente) {
    for(int i = 0; i < vertices -> obtener_tamanio(); i++){
        for(int j = 0; j < vertices -> obtener_tamanio(); j++){
            nueva_adyacente[i][j] = matriz_adyacencia[i][j];
        }
    }
}

void Grafo::inicializar_vertice(int** nueva_adyacente) {
    for(int i = 0; i < vertices -> obtener_tamanio(); i++){
        nueva_adyacente[vertices -> obtener_tamanio()][i] = INFINITO;
        nueva_adyacente[i][vertices -> obtener_tamanio()] = INFINITO;
    }
    nueva_adyacente[vertices -> obtener_tamanio()][vertices -> obtener_tamanio()] = 0;
}

void Grafo::liberar_matriz_adyacencia() {
    for(int i = 0; i < vertices -> obtener_tamanio() ; i++){
        delete[] matriz_adyacencia[i];
    }
    delete[] matriz_adyacencia;
}


void Grafo::arbol_expansion(){
    algoritmo_arbol_expansion = new Prim(matriz_adyacencia, vertices);
    algoritmo_arbol_expansion -> arbol_expansion();
    delete algoritmo_arbol_expansion;
    algoritmo_arbol_expansion = nullptr;
}

Grafo::~Grafo(){
    liberar_matriz_adyacencia();
    matriz_adyacencia = nullptr;
    delete vertices;
    delete algoritmo_arbol_expansion;

}

void Grafo::mostrar_vertices() {
    cout << "Lista de vértices: [";
    for(int i = 1; i <= vertices -> obtener_tamanio(); i++){
        cout << vertices -> consultar(i);
        if(i != vertices -> obtener_tamanio()){
            cout << ", ";
        }
    }
    cout << "]" << endl;
}

void Grafo::mostrar_matriz_adyacencia() {
    cout << "Matriz de adyacencia:" << endl;
    for(int i = 0; i < vertices -> obtener_tamanio(); i++){
        for(int j = 0; j < vertices -> obtener_tamanio() * 2; j++) {
            if(j == vertices -> obtener_tamanio() * 2 - 1){
                cout << endl;
            } else if(j % 2 == 0){
                if(matriz_adyacencia[i][j/2] == INFINITO){
                    cout << "∞";
                } else {
                    cout << matriz_adyacencia[i][j/2];
                }
            } else{
                cout << "|";
            }
        }
    }
    cout << endl;
}