#!/usr/bin/env python

import Grafo
import Prim
import GrafoUtils


def PercursoBuscaProfundidade(g,inicio=0):
	"""Retorna a ordem de visita de vertices num percurso feito através
	de busca em profundidade. Vertices aparecem apenas uma vez."""
	caminho=[]

	# Inicia o vizitando o inicio :-)
	VisitaBuscaProfundidade(g,inicio,caminho)
	
	for v in g.listaVertices():
		if g.getCor(v) == 'branco':
			VisitaBuscaProfundidade(g,v,caminho)
	return caminho

def VisitaBuscaProfundidade(g,v,caminho=[]):
	caminho.append(v)
	g.setCor(v,'cinza')
	for u in g.listaAdjacencia(v):
		if g.getCor(u) == 'branco':
			VisitaBuscaProfundidade(g,u,caminho)
	
	
def ConsertaParaAGM(grafo_original,debug=0):
	"""Conserta um grafo para a Heuristica da AGM.
	
	Converte ele num grafo completo que garanta a desigualdade triangular."""
	# Duplicamos o grafo e obtemos o valor da maior aresta...
	if debug: print "\tDuplicando o grafo original..."
	g=grafo_original.copy()
	max=g.obtemMaiorAresta()

	# A heuristica da AGM requer um grafo completo 	faltam=[]
	faltam=[]
	if debug: print "\tVerificando se o grafo é completo"
	if not GrafoUtils.ehCompleto(g,faltam):
		for e in faltam:
			u,v=e
			g.insereAresta(u,v,3*max) # pq 3? pq não?
			
	# Esse grafo completo tem que e que respeitar
	# a desigualdade triangular. 
	if debug: print "\tVerificando se o grafo é respeita a desig. triangular"
	max_diff = GrafoUtils.respeitaDesigualdadeTriangular(g,debug=0)
	if max_diff != 0:
		if debug: print "\tModificando o grafo para respeitar a D.T"
		# Grafo não respeita a DT. Acrecer todas as arestas de 
		# max_diff resolve o problema
		for e in g.listaArestas():
			u,v=e
			g.modificaAresta(u,v,g.obtemAresta(u,v)+max_diff)
	
	return g



def HeuristicaDaAGM(grafo_original,raiz=0,debug=0):
	"""Calcula o caminho do TSP usando a heuristica da AGM"""
#	# Duplicamos o grafo e obtemos o valor da maior aresta...
#	if debug: print "\tDuplicando o grafo original..."
#	g=Grafo.Grafo(grafo_original.numeroVertices())
#	max=0
#	for e in grafo_original.listaArestas():
#		u,v=e
#		peso=grafo_original.obtemAresta(u,v)
#		g.insereAresta(u,v,peso)
#		if peso > max:
#			max = peso
#	
#	# A heuristica da AGM requer um grafo completo e que respeite
#	# a desigualdade triangular. Ajustemos o grafo para respeitar
#	# esses requerimentos O(n^3)
#	faltam=[]
#	if debug: print "\tVerificando se o grafo é completo"
#	if not GrafoUtils.ehCompleto(g,faltam):
#		for e in faltam:
#			u,v=e
#			g.insereAresta(u,v,3*max) # pq 3? pq não?
#	if debug: print "\tVerificando se o grafo é respeita a desig. triangular"
#	max_diff = GrafoUtils.respeitaDesigualdadeTriangular(g,debug=0)
#	if max_diff != 0:
#		if debug: print "\tModificando o grafo para respeitar a D.T"
#		# Grafo não respeita a DT. Acrecer todas as arestas de 
#		# max_diff resolve o problema
#		for e in g.listaArestas():
#			u,v=e
#			g.modificaAresta(u,v,g.obtemAresta(u,v)+max_diff)
	g=grafo_original
	
	# Grafo OK. Gera AGM.
	if debug: print "\tGerando AGM"
	pais=Prim.AGMPrim(g,raiz)
	# Gera outro grafo (a AGM), esse para ser percorrido pelo BFS
	g_dfs=Grafo.Grafo(g.numeroVertices())
	# liga todo filho ao sei pai
	for u in range(len(pais)):
		if pais[u] is not None:
			g_dfs.insereAresta(u,pais[u])
	
	# Obtem a lista de visita de vértices da DFS
	if debug: print "\tGerando o caminho..."
	caminho=PercursoBuscaProfundidade(g_dfs,raiz) 
	# Curto-circuitos gerados caminhando nos vertices na ordem fornecida por 'caminho'
	
	if debug: print "\tFeito."
	return caminho

def VizinhoMaisProximo(g,inicio=0):
	"""Executa a heuristica do vizinho mais próximo no grafo g.
	
	Returna uma lista contendo o caminho encontrado."""

	# Inicializações
	for u in g.listaVertices():
		g.setCor(u,'branca')
	caminho=[]
	
	#Iniciamos a pesquisa no vertice 'inicio' (default para 0)
	vertice=inicio

	# Escolhendo os |V| vertices do caminho
	for z in range(g.numeroVertices()):
		g.setCor(vertice,'cinza')	# marca o vertice atual
		caminho.append(vertice)		# Coloca ele no caminho
		#Seleciona o menor vizinho:
		menor_custo=None
		menor_vizinho=None
		for u in g.listaAdjacencia(vertice):
			if g.getCor(u) != 'branca':
				continue
			if (menor_vizinho is not None ):
				if menor_custo <= g.obtemAresta(vertice,u):
					continue
			# Se ainda estamos aqui é pq o vertice é candidato
			menor_vizinho=u
			menor_custo=g.obtemAresta(vertice,u)
		#Já temos um ganhador. Continue o caminho dele....
		vertice=menor_vizinho
	
	return caminho


if __name__ == '__main__':
	g=GrafoUtils.TSPLIB2Grafo('../brazil58.tsp')
	
	print "Aplicando a heuristica do vizinho mais proximo."
	min_caminho=VizinhoMaisProximo(g,0)
	min_custo=GrafoUtils.custo_caminho(min_caminho,g)
	for u in range(1,g.numeroVertices()):
		caminho=VizinhoMaisProximo(g,u)
		custo=GrafoUtils.custo_caminho(caminho,g)
		if custo < min_custo:
			min_custo=custo
			min_caminho = caminho
	print "Pela Heuristica do Caminho Mais proximo, achamos um caminho de custo", min_custo, '\n', 'Caminho:',
	for i in min_caminho:
		print i, 
	print ''

	print "Aplicando a heuristica da Arvore Geradora Minima"
	print "\tConsertando o grafo para a heuristica"
	g_fix=ConsertaParaAGM(g,debug=1)
	min_caminho=HeuristicaDaAGM(g_fix,0,debug=0)
	min_custo=GrafoUtils.custo_caminho(min_caminho,g)
	for u in range(1,g.numeroVertices()):
		print "\t raiz no",u,
		caminho=HeuristicaDaAGM(g_fix,u,debug=0)
		custo=GrafoUtils.custo_caminho(caminho,g)
		print ' custo',custo
		if custo < min_custo:
			min_custo=custo
			min_caminho = caminho		
	print "Pela Heuristica da AGM, achamos um caminho de custo", min_custo, '\n', 'Caminho:',
	for i in min_caminho:
		print i, 
	print ''