//Representação de grafo dirigido atraves de lista de adjacências
template<class TV,class TR>
class grafolistadj
{
	private:
		int nvertices;
		int nramos;
		vertice<TV,TR> *graf;
		vertice<TV,TR> * encontrar_vertice(const TV & v) const;
	public:
		grafolistadj();
		void juntar_vertice(const TV & cont);
		void juntar_ramo(const TR & rcont,const TV & vorigem,const TV & vdestino);
		//void visita_profundidade(const TV & vinicio);
		//void visita_largura(const TV & vinicio);
		void escreve_grafo();


		//--------------------------------
		// Est. Info 2000/2001
		//--------------------------------

		grafolistadj(const grafolistadj<TV, TR>& o)
		{
			nvertices = nramos = 0;
			graf = NULL;
			copia(o);
		}
		~grafolistadj()
		{
			destroiGrafo();
		}

		void destroiGrafo();
		void juntar_ramo_2(const TR & rcont,const TV & vorigem,const TV & vdestino);
		bool caminho(const TV& origem, const TV& destino, TR& peso, vector<TV>& path) const;
		void imprimeTodosCaminhos(const TV& origem, const TV& destino) const;
		bool caminhoMinimo(const TV& origem, const TV& destino, TR& peso, vector<TV>& path) const;

		bool eliminar_ramo(const TR & rcont,const TV & vorigem,const TV & vdestino);
		bool eliminar_ramo(const TV & vorigem,const TV & vdestino);
		bool eliminar_vertice(const TV & cont);

		bool operator==(const grafolistadj<TV, TR>& o);

	private:
		void copia(const grafolistadj<TV, TR>& o);
		bool caminho(const vertice<TV, TR>* pActual, const TV& destino, TR& peso, vector<TV>& path, vector<TV>& visitados) const;
		bool ja_visitado(const TV& vertice, const vector<TV>& visitados) const;
		void imprimeTodosCaminhos(const vertice<TV, TR>* pActual, const TV& destino, vector<TV>& path, vector<TV>& visitados, TR& peso) const;
		void caminhoMinimo(const vertice<TV, TR>* pActual, const TV& destino, TR& peso, vector<TV>& path, vector<TV>& visitados, TR& pesoMin, vector<TV>& pathMin) const;

		//--------------------------------
		// Est. Info 2000/2001
		//--------------------------------
};

template<class TV,class TR>
grafolistadj<TV,TR>::grafolistadj()
{
	nvertices=0;
	nramos=0;
	graf=NULL;
}

template<class TV,class TR>
void grafolistadj<TV,TR>::juntar_vertice(const TV & cont)
{
	vertice<TV,TR> * vert;
	vert=graf;
	graf=new vertice<TV,TR>(cont);
	graf->apvertice=vert;
	nvertices++;
}

template<class TV,class TR>
void grafolistadj<TV,TR>::juntar_ramo(const TR & rcont,const TV & vorigem,const TV &vdestino)
{
	ramo<TV,TR> * tempramo=NULL;
	vertice<TV,TR> * tempvertice,* tempdestino=NULL;
	tempvertice=encontrar_vertice(vorigem);
	tempdestino=encontrar_vertice(vdestino);
		//--------------------------------
		// Est. Info 2000/2001
		//--------------------------------

	if (tempvertice == NULL || tempdestino == NULL)
		return;

		//--------------------------------
		// Est. Info 2000/2001
		//--------------------------------

	tempramo=tempvertice->apramo;

	tempvertice->apramo=new ramo<TV,TR>(rcont,tempdestino);
	tempvertice->apramo->apr=tempramo;
	nramos++;
}

template<class TV,class TR>
vertice<TV,TR> * grafolistadj<TV,TR>:: encontrar_vertice(const TV & v) const
{
	vertice<TV,TR> * ap=graf;
	int enc=1;
	while(ap!=NULL && enc)
	{
		if (ap->conteudo == v)
			enc=0;
		else ap=ap->apvertice;
	}
	if (enc==1)
		return NULL;
	else return ap;
}

template<class TV,class TR>
void grafolistadj<TV,TR>::escreve_grafo()
{
	vertice<TV,TR> * v=graf;
	ramo<TV,TR> * r=v->apramo;
	while(v!=NULL)
	{
		cout<<"O vertice "<<v->conteudo<<" liga-se a:"<<endl;
		r=v->apramo;
		while (r!=NULL)
		{
			cout<<r->apv->conteudo<<"  ";
			cout<<" Conteudo= "<<r->rconteudo<<endl;	
			r=r->apr;
		}
		cout<<endl;
		v=v->apvertice;
	}
}


		//--------------------------------
		// Est. Info 2000/2001
		//--------------------------------


template<class TV,class TR>
void grafolistadj<TV,TR>::copia(const grafolistadj<TV, TR>& o)
{
	destroiGrafo();

	for (vertice<TV, TR>* pItVertice = o.graf; pItVertice != NULL; pItVertice = pItVertice->apvertice)
	{
		this->juntar_vertice(pItVertice->getConteudo());
	}

	for (pItVertice = o.graf; pItVertice != NULL; pItVertice = pItVertice->apvertice)
	{
		for (ramo<TV, TR>* pItRamo = pItVertice->apramo; pItRamo != NULL; pItRamo = pItRamo->apr)
		{
			this->juntar_ramo(pItRamo->getPeso(), pItVertice->getConteudo(), pItRamo->getDestino());
		}
	}
}

template<class TV,class TR>
void grafolistadj<TV,TR>::destroiGrafo()
{
	while (graf != NULL)
	{
		while (graf->apramo != NULL)
		{
			ramo<TV, TR>* pr = graf->apramo;
			graf->apramo = pr->apr;
			delete pr;
		}

		vertice<TV, TR>* pv = graf;
		graf = graf->apvertice;
		delete pv;
	}
}

template<class TV,class TR>
void grafolistadj<TV,TR>::juntar_ramo_2(const TR & rcont,const TV & vorigem,const TV &vdestino)
{
	ramo<TV,TR> * tempramo=NULL;
	vertice<TV,TR> * tempvertice,* tempdestino=NULL;
	tempvertice=encontrar_vertice(vorigem);
	tempdestino=encontrar_vertice(vdestino);

	if (tempvertice == NULL || tempdestino == NULL)
		return;

	tempramo=tempvertice->apramo;
	tempvertice->apramo=new ramo<TV,TR>(rcont,tempdestino);
	tempvertice->apramo->apr=tempramo;
	nramos++;

	tempramo=tempdestino->apramo;
	tempdestino->apramo=new ramo<TV,TR>(rcont,tempvertice);
	tempdestino->apramo->apr=tempramo;
	nramos++;
}

template<class TV,class TR>
bool grafolistadj<TV,TR>::caminho(const TV& origem, const TV& destino, TR& peso, vector<TV>& path) const
{
	vector<TV> visitados;

	path.clear();
	peso = TR();
	return caminho(encontrar_vertice(origem), destino, peso, path, visitados);
}

template<class TV,class TR>
bool grafolistadj<TV,TR>::caminho(const vertice<TV, TR>* pActual, const TV& destino, TR& peso, vector<TV>& path, vector<TV>& visitados) const
{
	// por segurança
	if (pActual ==NULL)
		return false;

	// se chegamos ao destino
	if (pActual->conteudo == destino)
	{
		path.push_back(destino);
		return true;
	}

	// caso geral - tentar um ramo de saida
	path.push_back(pActual->conteudo);
	visitados.push_back(pActual->conteudo);

	for (ramo<TV, TR>* pItRamo = pActual->apramo; pItRamo != NULL; pItRamo = pItRamo->apr)
	{
		if (!ja_visitado(pItRamo->getDestino(), visitados))
		{
			if (caminho(pItRamo->apv, destino, peso, path, visitados))
			{
				peso += pItRamo->getPeso();
				return true;
			}
		}
	}

	// não foi possivel encontrar caminho - retroceder
	path.pop_back();
	return false;
}

template<class TV,class TR>
bool grafolistadj<TV,TR>::ja_visitado(const TV& no, const vector<TV>& visitados) const
{
	for (int i = 0; i < visitados.size(); i++)
	{
		if (no == visitados[i])
			return true;
	}
	return false;
}

template<class TV,class TR>
void grafolistadj<TV,TR>::imprimeTodosCaminhos(const TV& origem, const TV& destino) const
{
	vector<TV> visitados;
	vector<TV> path;
	TR peso = TR();

	imprimeTodosCaminhos(encontrar_vertice(origem), destino, path, visitados, peso);
}

template<class TV,class TR>
void grafolistadj<TV,TR>::imprimeTodosCaminhos(const vertice<TV, TR>* pActual, const TV& destino, vector<TV>& path, vector<TV>& visitados, TR& peso) const
{
	// por segurança
	if (pActual ==NULL)
		return;

	// se chegamos ao destino
	if (pActual->conteudo == destino)
	{
		path.push_back(destino);

		for (int i = 0; i < path.size(); i++)
			cout << path[i] << " ";
		cout << "(" << peso << ")" << endl;

		path.pop_back();

		return ;
	}

	// caso geral - tentar um ramo de saida
	path.push_back(pActual->conteudo);
	visitados.push_back(pActual->conteudo);

	for (ramo<TV, TR>* pItRamo = pActual->apramo; pItRamo != NULL; pItRamo = pItRamo->apr)
	{
		if (!ja_visitado(pItRamo->getDestino(), visitados))
		{
			peso += pItRamo->getPeso();
			imprimeTodosCaminhos(pItRamo->apv, destino, path, visitados, peso);
			peso -= pItRamo->getPeso();
		}
	}

	// retroceder
	path.pop_back();
	visitados.pop_back();
}

template<class TV,class TR>
bool grafolistadj<TV,TR>::caminhoMinimo(const TV& origem, const TV& destino, TR& peso, vector<TV>& path) const
{
	vector<TV> visitados;
	vector<TV> pathTemp;
	TR pesoTemp = TR();

	path.clear();
	peso = TR();
	caminhoMinimo(encontrar_vertice(origem), destino, pesoTemp, pathTemp, visitados, peso, path);
	return path.size() > 0;
}

template<class TV,class TR>
void grafolistadj<TV,TR>::caminhoMinimo(const vertice<TV, TR>* pActual, const TV& destino, TR& peso, vector<TV>& path, vector<TV>& visitados, TR& pesoMin, vector<TV>& pathMin) const
{
	// por segurança
	if (pActual ==NULL)
		return;

	// se chegamos ao destino
	if (pActual->conteudo == destino)
	{
		path.push_back(destino);

		if (pathMin.size() == 0 || peso < pesoMin)
		{
			pathMin = path;
			pesoMin = peso;
		}

		path.pop_back();

		return ;
	}

	// caso geral - tentar um ramo de saida
	path.push_back(pActual->conteudo);
	visitados.push_back(pActual->conteudo);

	for (ramo<TV, TR>* pItRamo = pActual->apramo; pItRamo != NULL; pItRamo = pItRamo->apr)
	{
		if (!ja_visitado(pItRamo->getDestino(), visitados))
		{
			peso += pItRamo->getPeso();
			caminhoMinimo(pItRamo->apv, destino, peso, path, visitados, pesoMin, pathMin);
			peso -= pItRamo->getPeso();
		}
	}

	// retroceder
	path.pop_back();
	visitados.pop_back();
}

template<class TV,class TR>
bool grafolistadj<TV,TR>::operator==(const grafolistadj<TV, TR>& o)
{
	if (this->nramos != o.nramos || this->nvertices != o.nvertices)
		return false;

	for (vertice<TV, TR>* pItVertice = this->graf; pItVertice != NULL; pItVertice = pItVertice->apvertice)
	{
		vertice<TV, TR>* pv = o.encontrar_vertice(pItVertice->getConteudo());
		if (pv == NULL || !((*pItVertice) == (*pv)))
			return false;
	}
	return true;
}


template<class TV,class TR>
bool grafolistadj<TV,TR>::eliminar_ramo(const TR & rcont,const TV & vorigem,const TV & vdestino)
{
	vertice<TV,TR> * tempvertice = encontrar_vertice(vorigem);
	if (tempvertice == NULL)
		return false;

	ramo<TV, TR>* pAntRamo = NULL
	for (ramo<TV, TR>* pItRamo = tempvertice->apramo; pItRamo != NULL; pItRamo = pItRamo->apr)
	{
		if (pItRamo->rconteudo == rcont && pItRamo->getDestino == vdestino)
		{
			if (pAntRamo == NULL)
				tempvertice->apramo = pItRamo->apr;
			else
				pAntRamo->apr = pItRamo->apr;
			delete pItRamo;
			return true;
		}
		pAntRamo = pItRamo;
	}

	return false;
}

template<class TV,class TR>
bool grafolistadj<TV,TR>::eliminar_ramo(const TV & vorigem,const TV & vdestino)
{
	vertice<TV,TR> * tempvertice = encontrar_vertice(vorigem);
	if (tempvertice == NULL)
		return false;

	ramo<TV, TR>* pAntRamo = NULL;
	for (ramo<TV, TR>* pItRamo = tempvertice->apramo; pItRamo != NULL; pItRamo = pItRamo->apr)
	{
		if (pItRamo->getDestino() == vdestino)
		{
			if (pAntRamo == NULL)
				tempvertice->apramo = pItRamo->apr;
			else
				pAntRamo->apr = pItRamo->apr;
			delete pItRamo;
			return true;
		}
		pAntRamo = pItRamo;
	}

	return false;
}

template<class TV,class TR>
bool grafolistadj<TV,TR>::eliminar_vertice(const TV & cont)
{
	vertice<TV, TR>* pAnt = NULL;
	vertice<TV, TR>* pVertice = NULL;

	// procurar vertice, guardando o ponteiro para o anterior
	for (vertice<TV, TR>* pItVertice = graf; pItVertice != NULL; pItVertice = pItVertice->apvertice)
	{
		if (pItVertice->getConteudo() == cont)
		{
			pVertice = pItVertice;
			break;
		}
		pAnt = pItVertice;
	}
	if (pVertice == NULL)
		return false;

	// apagar os ramos cujo vertice de destinbo seja o que se pretende apagar
	for (pItVertice = graf; pItVertice != NULL; pItVertice = pItVertice->apvertice)
	{
		if (pItVertice != pVertice)
		{
			ramo<TV, TR>* pAntRamo = NULL;
			ramo<TV, TR>* pItRamo = pItVertice->apramo;
			while (pItRamo != NULL)
			{
				ramo<TV, TR>* pTemp = pItRamo;

				if (pItRamo->getDestino() == cont)
				{
					if (pAntRamo == NULL)
						pItVertice->apramo = pItRamo->apr;
					else
						pAntRamo->apr = pItRamo->apr;
					pItRamo = pItRamo->apr;
					delete pTemp;
				}
				else
					pItRamo = pItRamo->apr;
				pAntRamo = pItRamo;
			}
		}
	}

	// apagar vertice
	while (pVertice->apramo != NULL)
	{
		ramo<TV, TR>* pr = pVertice->apramo;
		pVertice->apramo = pr->apr;
		delete pr;
	}
	if (pAnt == NULL)
		graf = pVertice->apvertice;
	else
		pAnt->apvertice = pVertice->apvertice;
	delete pVertice;

	return true;
}