#ifndef GRAFO_H
#define GRAFO_H 1

#include <vector>
#include <string>
#include <utility>
#include <stdexcept>


typedef std::pair<int,int> Aresta;
typedef int Vertice;				// Ma' nem pens'em redefini'ssa'qui
typedef std::vector<Vertice> ListaVertices;
typedef std::vector<Aresta> ListaArestas;
typedef std::vector<Vertice>::const_iterator ListaVerticesCIterator;
typedef std::vector<Aresta>::const_iterator ListaArestasCIterator;
typedef std::vector<std::vector<bool> > MatrizBool;
typedef std::vector<std::vector<int> > MatrizInt;

enum CorVertice {branco,cinza,preto};

//! Classe base p/ todas as exceções que aparecerem quando tratarmos de grafos.
class ErroGrafo{
	std::string descricao;	
public:
	//! Construtor
	/*!
	  \param descricao fornece uma string para descrever melhor o erro
	*/
	ErroGrafo(const std::string descricao="Erro na operação com grafos"){
		this->descricao = descricao;
	}
	const std::string& getDescription(){ return descricao;}
};

class ArestaDuplicada: public ErroGrafo {
	public:
	ArestaDuplicada(const std::string descricao="Aresta Duplicada"): ErroGrafo(descricao){};
};

class ArestaDesconhecida: public ErroGrafo {
	public:
	ArestaDesconhecida(const std::string descricao="Aresta Desconhecida"): ErroGrafo(descricao){};
};

class VerticeDesconhecido: public ErroGrafo {
	public:
	VerticeDesconhecido(const std::string descricao="Vértice Desconhecido"): ErroGrafo(descricao){};

};


	
//! Uma classe que modela um grafo atraves de matriz de adjacencias
/*!
    Lembrando, G=(V,E). O grafo eh grafo nao-direcionado - e não sei se
    já pela definição de GND -  e não possui self-loops
*/
class Grafo {

	int n;
	MatrizBool matriz_adj;  // matriz de adj. - eta complicação
	MatrizInt matriz_pesos; // matriz com o peso das arestas
	std::vector<CorVertice> cores;		   // vetor com as cores dos vertices

	/*! Mapeia uma aresta (u,v) para uma posição (i,j) dentro
	    da matriz de adjacencias ( que é triangular)
	 */
	const Aresta mapeiaTriangular(Vertice u, Vertice v);
	const Aresta mapeiaTriangular(Aresta e);
	
	//! Insere uma areta na matriz de adj.
	void insAresta(Vertice u, Vertice v) throw (VerticeDesconhecido);

	//! Remove uma areta da matriz de adj.
	void delAresta(Vertice u, Vertice v) throw (VerticeDesconhecido);

	
	
	//! 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
	    Lança uma exception caso a aresta não exista
	 */
	int getAresta(Vertice u, Vertice v) throw(ArestaDesconhecida,VerticeDesconhecido);

	//! 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
	    Lanca uma exception ArestaDesconhecida caso a aresta não exista
	 */
	void setAresta(Vertice u, Vertice v,int peso) throw (ArestaDesconhecida,VerticeDesconhecido);
public:
	
	//!Cria o grafo.
	/*! 
	 * \param n eh o numero de verticesque o novo gravo deve ter.
	 */	
	Grafo(int n=10);
	
	//! Retorna o numero de vértices do grafo
	int numeroVertices();

	//! Verifica a existencia de uma aresta
	/*! 
	    Lanca uma VerticeDesconhecido exception caso os vertices
	    informados nao existam
	    \param u vertice de saida da aresta a ser testada
	    \param v vertice de chegada da aresta a ser testada
	 */
	bool existeAresta(Vertice u, Vertice v) throw (VerticeDesconhecido);

	//! Verifica a existencia de uma aresta
	/*! 
	    Lanca uma VerticeDesconhecido exception caso os vertices
	    informados nao existam
	    \param e aresta a ser testada
	 */
	bool existeAresta(Aresta e) throw (VerticeDesconhecido);


	/* //! Retorna uma ListaVertices == V do Grafo G=(V,E)
	ListaVerticesCIterator listaVertices(){
		return this.m
	}*/
	
	//! Retorna a lista de vertices adjacentes ao vertice n
	ListaVertices& listaAdjacencia(Vertice vertice);
	
	//! Lista as arestas do grafo 
	ListaArestas& listaArestas();
	
	//! Insere uma nova aresta no grafo
	/*!
	    \param u vertice de saida da aresta a ser inserida
	    \param v vertice de chegada da aresta a ser inserida
	    \param peso  peso a ser colocado nessa aresta
	 */
	void insereAresta(Vertice u, Vertice v, int peso=1) throw(ArestaDuplicada,VerticeDesconhecido) ;

	
	//! Remove uma aresta.
	/*!
	    Caso a aresta nao exista, uma exception.
	    Caso os vertices nao existam (mencionar arestas com vertices que nem a V pertencem),
	    uma exception eh lancada.
	 */
	void removeAresta(Vertice u, Vertice v) throw (ArestaDuplicada,VerticeDesconhecido);

	
	//! Retorna o peso de uma aresta.
	/*
	    Caso ela não exista, uma exception é lancada.
	 */
	int obtemAresta(Vertice u, Vertice v)  throw(ArestaDesconhecida,VerticeDesconhecido);	
	//! Modifica o peso de uma aresta.
	/*! 
	    Caso a aresta nao exista, uma exception eh lancada.
	    Caso os vertices nao existam, uma exception eh lancada.
	 */
	void modificaAresta(Vertice u, Vertice v, int peso) throw(ArestaDesconhecida,VerticeDesconhecido);			
	
	//! Modifica a cor de um vértice
	void setCor(Vertice vertice,CorVertice cor) throw (VerticeDesconhecido);

	//! Retorna a cor de um vértice
	const CorVertice getCor(Vertice vertice) throw (VerticeDesconhecido);

	//! Imprime a matriz de adj.
	void imprimeMatrizAdj();
	
	/*
	//! Retorna uma copia desse grafo 
	def copy(self):
		g=Grafo(self.__n)
		for e in self.listaArestas():
			u,v=e
			g.insereAresta(u,v,self.obtemAresta(u,v))
		return g
	
	//! Retorna o valor da maior aresta.
	+*  E se não existir aresta nenhuma?!
	def obtemMaiorAresta(self):
		
		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
	*/	
		
		
};	


#endif