#!/usr/bin/env python

import Grafo,GrafoUtils



# Eu evitaria globais mas complicaria demais a minha vida....
melhor_caminho=None
melhor_custo=None

def visitaTSP(g,caminho=[0],custo=0,parciais=0,):
	"""Realiza a busca em profundidade no grafo g.
	
	'caminho'	deve conter o nó inicial da busca.
	'parciais'	OPCIONAL determina se valores parciais são impressos
			ou não (bool)
	'custo'		o custo inicial
	
	Retorna o menor caminho"""

	global melhor_caminho, melhor_custo

	vertice=caminho[-1] # vertice é o ultimo no caminho...
	g.setCor(vertice,'cinza') #
	
	# Podando...
	if (melhor_custo is None) or (melhor_custo > custo):
		# Continua a visita, seguindo para os vizinhos
		for u in g.listaAdjacencia(vertice):
			if g.getCor(u) == 'branco':
				visitaTSP(g,
					 caminho+[u], # Parcial+aresta
					 custo+g.obtemAresta(vertice,u),
					 parciais)
					 
			# Teste de fim da recursão....
			elif (u == caminho[0]) and (len(caminho) == g.numeroVertices()):
			       # custo do trajeto completo....
				custo = custo + g.obtemAresta(vertice,u)
				if (melhor_custo is None) or (melhor_custo > custo):
					melhor_caminho=[]+caminho
					melhor_custo=custo
					if parciais:
						print '\nCusto do melhor caminho (parcial): %i' % custo

	else:
		if parciais:
			print "+",
			
	# Desfaz a trilha...
	g.setCor(vertice,'branco')

	
def test_module():
	g=Grafo.Grafo(7)
	
	# Essa matriz está transposta.....
	m=[[  None,     3,     5,    48,    48,     8,     8],
	   [  None,  None,     3,    48,    48,     8,     8],
	   [  None,  None,  None,    72,    72,    48,    48],
	   [  None,  None,  None,  None,     0,     6,     6],
	   [  None,  None,  None,  None,  None,     6,     6],
	   [  None,  None,  None,  None,  None,  None,     0],
	   [  None,  None,  None,  None,  None,  None,  None]]
	for i in range(len(m)):
		for j in range(0,i+1):
			g.insereAresta(i,j,m[j][i])
	g.imprimeMatrizAdj()
	visitaTSP(g)	

if __name__ == '__main__':
	try:
		entrada=sys.argv[1]
	except:
		entrada='entrada'
	
	g=GrafoUtils.TSPLIB2Grafo(entrada)
	visitaTSP(g)

	# Saida para a STDOUT
	print 'Menor custo:', melhor_custo
	print melhor_caminho

	# Saída para arquivo saída
	
	
	fh=open('saida','w')
	for i in melhor_caminho:
		fh.write('%i\n'% i )
	
	fh.close()