#include "GrafoUtils.h"
#include <iostream>
#include <fstream>
#include <iterator>
#include <cstdlib>


Grafo& TSPLIB2Grafo(const std::string& filename) throw(ErroGrafo)
{
	int i,j;
	
	int dimension=-1;	// Dimensao padrão :-)
	Grafo* g;

	// Variáveis auxiliares no tratamento do arquivo
	std::string option = "";
	int value=0;
	
	std::ifstream fh (filename.c_str());
	std::istream_iterator<std::string> fh_i (fh);

	if (!fh){
		std::cerr<<"Não consegui abrir o arquivo de entrada.\n";
		throw ErroGrafo();
	}
	
	// Trata o 'header'
	while ( *fh_i != "EDGE_WEIGHT_SECTION") {
		std::cout << "option >>" << *fh_i;
		if (*fh_i == "DIMENSION:"){ 
			fh_i++;
			std::cout << " !! " << *fh_i << '\n';
			dimension = atoi((*fh_i).c_str());
			std::cout << "A dimensão é de "<< dimension<<"\n";
		} else {
			// Não nos interessa: pega o proximo string
			fh_i++;
			std::cout << *fh_i << '\n';
		}
		fh_i++;
		option = *fh_i;
	}
	
	if (dimension < 0){
		// Ops! Algo aconteceu de errado na leitura
		std::cerr << "Erro na leitura do arquivo '"<< filename<<"'\n";
		throw ErroGrafo("Não consigo entender o arquivo de entrada");
	}

	
	// Trata o corpo
	g = new Grafo(dimension);
	for (j = 0; j < dimension - 1; j++){
		for (i = j + 1; i < dimension; i++){
			fh >> value;
			g->insereAresta(i,j,value);
		}
	}

	fh.close();
	
	return (*g);
}


//def ehCompleto(Grafo& grafo,faltam=[]):
//	/*!  Verifica se um grafo é completo.
//	
//	Opcionalmente você pode fornecer um array em 'faltam' onde as arestas
//	que faltam serão inseridas. Supomos grafos não direcionados
//	sem laços.*/
//	n=grafo.numeroVertices()
//	
//	# Checando  de forma mais inteligente... ( so a matriz diag. sup.)
//	for j in range(n -1):
//		for i in range(j+1,n):
//			if not grafo.existeAresta(i,j):
//				faltam.append((i,j))
//	
//	if len(faltam) == 0:
//		return 1
//	else:
//		return 0
//
//def respeitaDesigualdadeTriangular(grafo, debug=1):
//	/*! Verifica se um grafo COMPLETO respeita a desigualdade triangular e,
//	caso não respeite, qual é a diferença máxima encontrada.
//	
//	Retorna 0 se o grafo respeitar, e, caso contrário, a differenca máxima
//	encontrada.
//	
//	o(n^3)... Testando todas as combinações mesmo...*/
//	
//	diff_maxima = 0
//
//	if not ehCompleto(grafo):
//		return 0
//	
//	# Para cada vértice i,j,k percententes ao grafo....
//	for i in grafo.listaVertices():
//		if debug: print i
//		for j in grafo.listaVertices():
//			if i == j:
//				continue
//			for k in grafo.listaVertices():
//				if (i == k) or (j == k):
//					continue
//				# Calcula a diferença
//				diff = grafo.obtemAresta(i,j) -\
//				 (grafo.obtemAresta(j,k)+grafo.obtemAresta(k,i))
//				# OPs! Será que encontramos uma diff maio??
//				if diff > diff_maxima:
//					if debug: print "(%i,%i,%i) ofende!"%(i,j,k)
//					diff_maxima = diff
//	return diff_maxima
//
//
//def custo_lista_paternidade(lista,grafo):
//	custo = 0
//	for u in range(len(lista)):
//		if lista[u] is not None:
//			custo = custo + grafo.obtemAresta(u,lista[u])
//
//	return custo

int custo_caminho(ListaVertices caminho,Grafo grafo)
{
	int custo = 0;
	int tamanho = caminho.size();
	for(int i = 0; i < tamanho; i++){
		custo += grafo.obtemAresta(caminho[i],
					   caminho[(i+1)%tamanho]);
	}

	return custo;
}
//
//
//
//
//if __name__ == '__main__':
//	filename='../brazil58.tsp'
//	m=TSPLIB2Grafo(filename)