#!/usr/bin/env python

def geraMatriz(n=10, valor_padrao=None):
	matriz=[]
	for i in range(n):
		matriz.append([])
		for j in range(n):
			matriz[i].append(valor_padrao)
	
	return matriz

class ErroGrafo(Exception):
	pass

class ArestaDuplicada(ErroGrafo):
	pass

class ArestaDesconhecida(ErroGrafo):
	pass

class VerticeDesconhecido(ErroGrafo):
	pass

class Grafo:
	"""Uma classe que modela um grafo atraves de matriz de adjacencias.
	
	Lembrando, G=(V,E). O grafo eh grafo nao-direcionado.
	Na nossa representação de matriz de adj., um elemento M[i][j]==None
	representa a ausência de uma aresta entre os nós i e j"""
	def __init__(self,n=10):
		"""Cria o grafo.
		
		O primeiro argumento eh o numero de vertices( n = |V| ).	
		Por default, o valor do numero de vertices eh 10."""
		self.__n=n
		self.__matriz=geraMatriz(n)
		# Todos os vertices sao inicialmente brancos
		self.__cores= ["branco"]*n

	def __mapeiaTriangular(self,u,v):
		"""Mapeia uma aresta (u,v) para uma posição (i,j) dentro
		da matriz de adjacencias ( que é triangular)"""
		if u >= v :
			i=u
			j=v
		else:
			i=v
			j=u
		return (i,j)

		
	def __getAresta(self,u,v):
		"""Obtem o valor de uma "aresta" na matriz.
		
		Função para tratamento direto da matriz de adj.
		Adicionalmente ela garante que o grafo é não-direcionado"""

		(i,j)=self.__mapeiaTriangular(u,v)
		try:
			return self.__matriz[i][j]
		except IndexError:
			#IndexErrors podem ser causados apenas por acessos
			#Fora do limite da matriz, ou seja: o valor de
			#u ou de v não está em {0,...|V|-1}
			raise VerticeDesconhecido("Voce forneceu um valor invalido como vertice.")

	def __setAresta(self,u,v, peso):
		"""Modifica o valor de uma "aresta" na matriz
		
		Função para tratamento direto da matriz de adj.
		Adicionalmente ela garante que o grafo é não-direcionado"""

		(i,j)=self.__mapeiaTriangular(u,v)
		try:
			self.__matriz[i][j]=peso
		except IndexError:
			#IndexErrors podem ser causados apenas por acessos
			#Fora do limite da matriz, ou seja: o valor de
			#u ou de v não está em {0,...|V|-1}
			raise VerticeDesconhecido("Voce forneceu um valor invalido como vertice.")

	def numeroVertices(self):
		"Retorna o numero de vértices do grafo"
		return self.__n

	def existeAresta(self, u,v):
		"""Verifica a existencia de uma aresta.

		Lanca uma exception caso os vertices informados nao existam"""
		if self.__getAresta(u,v) is not None:
			return 1
		return 0


	def listaVertices(self):
		"""Retorna uma V, a lista de vertices do Grafo."""
		return range(self.__n)
	
	def listaAdjacencia(self,vertice):
		"""Retorna a lista de vertices adjacentes ao vertice n"""
		adj=[]
		for i in range(self.__n):
			if self.existeAresta(vertice,i):
				adj.append(i)

		return adj
	
	def listaArestas(self, vertice=None):
		"""Lista as arestas do grafo ou, caso seja dado um vertice
		como argumento, lista  as arestas que saem desse vertice."""
		arestas=[]
		
		if vertice is None:
			# Loop nos itens da matriz triangular...
			for i in self.listaVertices():
				for j in range(0,i+1):
					if self.existeAresta(i,j):
						arestas.append((i,j))
		else:
			for i in self.listaVertices():
				if self.existeAresta(vertice,i):
					arestas.append((vertice,i))

		return arestas
	
	def insereAresta(self,u,v,peso=1):
		if self.existeAresta(u,v):
			raise ArestaDuplicada("A aresta (%i,%i) ja existe" % (u,v))
		else:
			self.__setAresta(u,v,peso)
	
	def removeAresta(self,u,v):
		"""Remove uma aresta.
		
		Caso a aresta nao exista, ele simplesmente ignora o pedido.
		Caso os vertices nao existam, uma exception eh lancada."""
		self.modificaAresta(u,v,None)
	
	def obtemAresta(self,u,v):
		"""Retorna o pese de uma aresta.

		Caso ela não exista, uma exception é lancada"""
		if self.existeAresta(u,v):
			return self.__getAresta(u,v)
		else:
			raise ArestaDesconhecida("A aresta (%i,%i) não existe" % (u,v))
	
	def modificaAresta(self,u,v,peso):
		"""Modifica o peso de uma aresta.
		
		Colocar o valor de peso como None efetivamente remove a	aresta.
		Caso a aresta nao exista, uma exception eh lancada.
		Caso os vertices nao existam, uma exception eh lancada."""
		if self.existeAresta(u,v):
			self.__setAresta(u,v,peso)
		else:
			raise ArestaDesconhecida("A aresta (%i,%i) não existe" % (u,v))
			
	
	def setCor(self, vertice, cor="branco"):
		"""Modifica a cor de um vértice"""
		try:
			self.__cores[vertice]=cor
		except:
			#IndexErrors podem ser causados apenas por acessos
			#Fora do limite da matriz, ou seja: o valor de
			#u ou de v não está em {0,...|V|-1}
			raise VerticeDesconhecido("Voce forneceu um valor invalido como vertice.")
	
	def getCor(self, vertice):
		"""Retorna a cor de um vértice"""
		try:
			return self.__cores[vertice]
		except:
			#IndexErrors podem ser causados apenas por acessos
			#Fora do limite da matriz, ou seja: o valor de
			#u ou de v não está em {0,...|V|-1}
			raise VerticeDesconhecido("Voce forneceu um valor invalido como vertice.")


	def imprimeMatrizAdj(self):
		"""Imprime a matriz de adj."""
		titulo = "-=- -=- -=- Matriz de Adjacência -=- -=- -=-"
		print titulo.center(72)
		for j in range(self.__n):
			for i in range(self.__n):
				if self.existeAresta(i,j):
					print " %3i "% self.obtemAresta(i,j),
				else:
					print " %3s "%'-',
			print "" # nova linha...
	
	
	def copy(self):
		"""Retorna uma copia desse grafo"""
		g=Grafo(self.__n)
		for e in self.listaArestas():
			u,v=e
			g.insereAresta(u,v,self.obtemAresta(u,v))
		return g
	
	def obtemMaiorAresta(self):
		"""Retorna o valor da maior aresta.
		
		Retorna None caso não hajam arestas."""
		arestas=self.listaArestas()
		maior=None
		
		if len(arestas) == 0 :
			return None

		# Obtem um valor inicial para 'maior'
		e=arestas.pop()
		u,v=e
		maior=self.obtemAresta(u,v)
		
		for e in arestas:
			u,v=e
			valor=self.obtemAresta(u,v)
			if valor > maior:
				maior = valor

		return maior