#!/usr/bin/env python

"""GrafoUtils.py - Funções Auxiliares para o tratamento dos problemas do
trabalho prático #1"""

import Grafo

def TSPLIB2Matriz(filename=None):
	"""Retorna uma Matriz correspondente a encontrada num arquivo no
	formato da TSPLib"""
	dim=10			# Dimensao padrão :-)
	
	fh=open(filename,'r')
	
	# Trata o 'header'
	linha=fh.readline()
	linha=linha.strip()
	while linha != 'EDGE_WEIGHT_SECTION':
		print "Linha >>", linha
		(option,value)=linha.split(":",2)
		value=value.strip()	# Remove o \n do final da str
		if option == 'DIMENSION':
			dim=int(value)
		if (option == 'EDGE_WEIGHT_TYPE') and (value != 'EXPLICIT'):
			raise "Eu só sei tratar arquivos com EADGE_WEIGHT_TYPE do tipo EXPLICIT, e essa é do tipo '%s'" % value
		if (option == 'EDGE_WEIGHT_FORMAT') and (value != 'UPPER_ROW'):
			raise "Eu só sei tratar arquivos com EADGE_WEIGHT_FORMAT do tipo UPPER_ROW, e essa é do tipo '%s'" % value	
		
		linha = fh.readline()
		linha=linha.strip()
	
	# Trata o corpo
	matriz=Grafo.geraMatriz(dim)
	for j in range(dim - 1):
		linha=fh.readline()
		linha=linha.strip()
		valores=linha.split(' ',dim-(j+1))
		for i in range(j+1,dim):
			matriz[i][j] = int(valores[0])
			del valores[0]		# remove a frete da lista...

	fh.close()
	
	return matriz

def Matriz2Grafo(matriz):
	"""Converte uma matriz de adjacências Triangular Superior
	(sem diagonal) 	para um grafo"""
	dim=len(matriz)			# Obtem a dimensão da matriz
	grafo=Grafo.Grafo(dim)		# Cria o gra... ah! da pra ver!

	# Acrescenta as arestas ao grafo...
	for i in range(dim):		# Para cada coluna...
		for j in range(0,i+1):  # Para cada linha
			grafo.insereAresta(i,j,matriz[i][j])
	
	return grafo


def TSPLIB2Grafo(filename=None):
	"""Retorna um grafo correspondente ao encontrada num arquivo no
	formato da TSPLib"""
	return Matriz2Grafo(TSPLIB2Matriz(filename))

def ehCompleto(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

def custo_caminho(lista,grafo):
	custo = 0
	for i in range(len(lista)):
		custo = custo + grafo.obtemAresta(lista[i],
						  lista[(i+1)%len(lista)])

	return custo




if __name__ == '__main__':
	filename='../brazil58.tsp'
	m=TSPLIB2Grafo(filename)