-
Notifications
You must be signed in to change notification settings - Fork 2
/
main.cpp
358 lines (318 loc) · 11.7 KB
/
main.cpp
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <utility>
#include <tuple>
#include <iomanip>
#include <stdlib.h>
#include <chrono>
#include <vector>
#include "Grafo.h"
#include "No.h"
using namespace std;
// Inicio da funcao para leitura do arquivo de entrada
Grafo *leitura(ifstream &arquivo, int direcionado, int aresta_ponderado, int no_ponderado) {
int id_no_origem;
int id_no_alvo;
int ordem;
// Pegando a ordem do grafo
arquivo >> ordem;
// Criando objeto grafo
Grafo *grafo = new Grafo(ordem, direcionado, aresta_ponderado, no_ponderado);
// Leitura do arquivo
if (!grafo->getArestaPonderado() && !grafo->getNoPonderado()) {
// Primeiro caso: aresta sem peso e no sem peso
float peso_aresta;
while (arquivo >> id_no_origem >> id_no_alvo) {
// Aresta sem peso por padrao recebe peso 1
peso_aresta = 1;
grafo->inserirAresta(id_no_origem, id_no_alvo, peso_aresta);
}
} else if (grafo->getArestaPonderado() && !grafo->getNoPonderado()) {
// Segundo caso: aresta com peso e no sem peso
float peso_aresta;
while (arquivo >> id_no_origem >> id_no_alvo >> peso_aresta) {
grafo->inserirAresta(id_no_origem, id_no_alvo, peso_aresta);
}
} else if (grafo->getNoPonderado() && !grafo->getArestaPonderado()) {
// Terceiro caso: aresta sem peso e no com peso
float peso_no_origem, peso_no_alvo, peso_aresta;
while (arquivo >> id_no_origem >> peso_no_origem >> id_no_alvo >> peso_no_alvo) {
peso_aresta = 1;
grafo->inserirAresta(id_no_origem, id_no_alvo, peso_aresta);
grafo->getNo(id_no_origem)->setPeso(peso_no_origem);
grafo->getNo(id_no_alvo)->setPeso(peso_no_alvo);
}
} else if (grafo->getNoPonderado() && grafo->getArestaPonderado()) {
// Quarto caso: aresta com peso e no com peso
float peso_no_origem, peso_no_alvo, peso_aresta;
while (arquivo >> id_no_origem >> peso_no_origem >> id_no_alvo >> peso_no_alvo >> peso_aresta) {
grafo->inserirAresta(id_no_origem, id_no_alvo, peso_aresta);
grafo->getNo(id_no_origem)->setPeso(peso_no_origem);
grafo->getNo(id_no_alvo)->setPeso(peso_no_alvo);
}
}
// Inserindo Nos que faltam
while (grafo->getOrdem() != ordem) {
grafo->inserirNo(grafo->getOrdem() + 1);
}
return grafo;
}
// Fim da funcao para leitura do arquivo de entrada
// Inicio da funcao para leitura do arquivo de entrada do segundo trabalho
Grafo *leituraInstancias(ifstream &arquivo) {
int direcionado = 0;
int aresta_ponderado = 1;
int no_ponderado = 0;
// Criando objeto grafo
int ordem = 0;
Grafo *grafo = new Grafo(ordem, direcionado, aresta_ponderado, no_ponderado);
// Flag de controle para saber se está lendo os Nos ou as arestas
bool inserindoNos = true;
// Percorrendo linha por linha do arquivo de entrada
for (string line; getline(arquivo, line);) {
if (line == "" || line == "\r" || line == "\n") {
inserindoNos = false;
}
if (inserindoNos) {
grafo->inserirNoComGrupo(stoi(line));
} else {
int id_no_origem, id_no_alvo;
float peso_aresta;
while (arquivo >> id_no_origem >> id_no_alvo >> peso_aresta) {
grafo->inserirAresta(id_no_origem, id_no_alvo, peso_aresta);
}
break;
}
}
cout << "Leitura concluida com sucesso! Nos: " << grafo->getOrdem() << " e Arestas: " << grafo->getNumArestas()
<< endl;
cout << "Quantidade de Grupos: " << grafo->getQtdGrupos() << endl;
return grafo;
}
// Fim da funcao para leitura do arquivo de entrada do segundo trabalho
// Inicio funcao salvar string em .dot
void salvarStringDot(string retorno, ofstream &arquivo_saida) {
arquivo_saida << retorno;
}
// Fim funcao salvar string em .dot
// Inicio funcao opcoes no menu
int menu() {
int selecao;
cout << "MENU" << endl;
cout << "----" << endl;
// cout << "[1] Fecho Transitivo Direto" << endl;
// cout << "[2] Fecho Transitivo Indireto" << endl;
// cout << "[3] Caminho Minimo entre dois vertices - Dijkstra" << endl;
// cout << "[4] Caminho Minimo entre dois vertices - Floyd" << endl;
// cout << "[5] Arvore Geradora Minima de Prim" << endl;
// cout << "[6] Arvore Geradora Minima de Kruskal" << endl;
// cout << "[7] Arvore do Caminhamento em Profundidade" << endl;
// cout << "[8] Imprimir Ordenacao Topologica" << endl;
// cout << "[9] Imprimir Grafo de Entrada" << endl;
cout << "[1] Algoritmo Guloso AGMG" << endl;
cout << "[2] Algoritmo Guloso AGMG Randomizado" << endl;
cout << "[3] Algoritmo Guloso AGMG Randomizado Reativo" << endl;
cout << "[0] Sair" << endl;
cin >> selecao;
return selecao;
}
// Fim funcao opcoes no menu
// Inicio funcao menu salvar arquivo
int menuSalvar() {
int selecao;
cout << "Voce deseja salvar o resultado da operacao?" << endl;
cout << "[0] Nao" << endl;
cout << "[1] Sim" << endl;
cin >> selecao;
return selecao;
}
// Fim funcao menu salvar arquivo
// Inicio funcao selecionar no menu
void selecionar(int selecao, Grafo *grafo, ofstream &arquivo_saida) {
//String de retorno dos resultados das funcoes, utilizada para exportar o grafo em .dot no arquivo de saida.
string retorno = "";
switch (selecao) {
// Fecho Transitivo Direto
// case 1: {
// cout << "Digite o ID do vertice de origem: " << endl;
// int id;
// cin >> id;
// retorno = grafo->fechoTD(id);
// break;
// }
// // Fecho Transitivo Indireto
// case 2: {
// cout << "Digite o ID do vertice de origem: " << endl;
// int id;
// cin >> id;
// retorno = grafo->fechoTIRec(id);
// break;
// }
// // Caminho Minimo entre dois vertices - Dijkstra
// case 3: {
// cout << "Digite o ID do vertice de origem: " << endl;
// int id;
// cin >> id;
// cout << "Digite o ID do vertice alvo: " << endl;
// int id_alvo;
// cin >> id_alvo;
// retorno = grafo->djikstra(id, id_alvo);
// break;
// }
// // Caminho Minimo entre dois vertices - Floyd
// case 4: {
// cout << "Digite o ID do vertice de origem: " << endl;
// int id;
// cin >> id;
// cout << "Digite o ID do vertice alvo: " << endl;
// int id_alvo;
// cin >> id_alvo;
// retorno = grafo->floyd(id, id_alvo);
// break;
// }
// // Arvore Geradora Minima de Prim
// case 5: {
// cout << "Digite a ordem do subgrafo de entrada: ";
// int tamanho;
// cin >> tamanho;
// int vertices[tamanho];
// for (int i = 0; i < tamanho; i++) {
// cout << "Digite o " << std::to_string(i + 1) << "o vertice: ";
// cin >> vertices[i];
// cout << endl;
// }
// Grafo *subGrafo = grafo->subgrafo(vertices, tamanho);
// retorno = subGrafo->agmPrim();
// break;
// }
// // Arvore Geradora Minima de Kruskal
// case 6: {
// cout << "Digite a ordem do subgrafo de entrada: ";
// int tamanho;
// cin >> tamanho;
// int vertices[tamanho];
// for (int i = 0; i < tamanho; i++) {
// cout << "Digite o " << std::to_string(i + 1) << "o vertice: ";
// cin >> vertices[i];
// cout << endl;
// }
// Grafo *subGrafo = grafo->subgrafo(vertices, tamanho);
// retorno = subGrafo->agmKruskal();
// break;
// }
// // Arvore pelo Caminhamento em Profundidade
// case 7: {
// int id;
// cout << "Digite o id de origem: ";
// cin >> id;
// retorno = grafo->buscaProf(id);
// break;
// }
// // Imprimir Ordenacao Topologica
// case 8: {
// retorno = grafo->ordTopologica();
// break;
// }
// // Imprimir Grafo de Entrada
// case 9: {
// retorno = grafo->imprimir();
// break;
// }
// Algoritmo Guloso AGMG
case 1: {
retorno = grafo->AGMGPrim();
break;
}
// Algoritmo Guloso AGMG Randomizado
case 2: {
int qnt_it;
cout << "Digite a quantidade de iteracoes: " << endl;
cin >> qnt_it;
float alfa;
cout << "Digite o alfa: " << endl;
cin >> alfa;
retorno = grafo->AGMGPrimRandomizado(alfa, qnt_it);
break;
}
// Algoritmo Guloso AGMG Randomizado Reativo
case 3: {
retorno = grafo->AGMGRandReativo();
break;
}
case 0: {
cout << "Encerrando o programa" << endl;
return;
}
default: {
cout << "Erro: Opcao invalida!" << endl;
}
}
//Chamada da funcao para verificar se o usuario quer salvar o grafo no arquivo de saida
int selecaoSalvar = menuSalvar();
if (selecaoSalvar) {
salvarStringDot(retorno, arquivo_saida);
cout << retorno << endl;
} else {
salvarStringDot("Voce nao salvou a operacao", arquivo_saida);
cout << "Voce nao salvou a operacao" << endl;
}
}
// Fim funcao selecionar no menu
// Inicio funcao main menu
int mainMenu(ofstream &arquivo_saida, Grafo *grafo) {
int selecao = 1;
while (selecao != 0) {
// system("@cls||clear");
selecao = menu();
if (arquivo_saida.is_open()) {
selecionar(selecao, grafo, arquivo_saida);
} else {
cout << "Erro ao abrir o arquivo de saida!" << endl;
}
arquivo_saida << endl;
}
return 0;
}
// Fim funcao main menu
// Inicio funcao main
int main(int argc, char const *argv[]) {
// Verifica se todos parametros necessarios para compilar foram definidos
if (argc != 3) {
cout
// << "Erro: Esperando: ./<program_name> <arquivo_entrada> <arquivo_saida> <direcionado> <aresta_ponderado> <no_ponderado> "
<< "Erro: Esperando: ./<program_name> <arquivo_entrada> <arquivo_saida>"
<< endl;
return 1;
}
string nome_programa(argv[0]);
string nome_arquivo_entrada(argv[1]);
string instancia;
if (nome_arquivo_entrada.find("v") <= nome_arquivo_entrada.size()) {
string instancia = nome_arquivo_entrada.substr(nome_arquivo_entrada.find("v"));
cout << "Executando " << nome_programa << " com instancia " << instancia << " ... " << endl;
}
// Abrindo arquivos de entrada e saida
ifstream arquivo_entrada;
ofstream arquivo_saida;
arquivo_entrada.open(argv[1], ios::in);
arquivo_saida.open(argv[2], ios::out | ios::trunc);
// Criando grafo da leitura do arquivo
Grafo *grafo;
// Verificando se conseguiu abrir o arquivo de entrada
if (arquivo_entrada.is_open()) {
// grafo = leituraInstancias(arquivo_entrada, atoi(argv[3]), atoi(argv[4]), atoi(argv[5]));
grafo = leituraInstancias(arquivo_entrada);
} else {
cout << "Nao foi possivel abrir o arquivo de entrada: " << argv[1];
}
// Chamando main menu
mainMenu(arquivo_saida, grafo);
// Fechando arquivo de entrada
arquivo_entrada.close();
// Fechando arquivo de saída
arquivo_saida.close();
return 0;
}
// Fim funcao main