[Resolvido] Grafos

[Atreyu 0]

Boas

 

 

Ora eu ando a fazer um trabalho em C++ sobre grafos.

 

Tenho uma classe de Lista de Adjacências que é template, do género:

 

template<class TV, class TR> onde TV são os meus vertíces e TR os meus ramos.

 

Já construi grande parte do trabalho, que envolvia diversas classes, agora encalhei aqui nos grafos, muito devido ao facto dos apontadores.

 

Dita a introdução e passando a acção estou a tentar fazer um método que me remova um Vertice, logo a partida(digo eu) ao eliminar um vertice temos que eliminar os ramos associados a esse vertice, certo?

 

O que eu ando a tentar a algo do género:

 

template<class, TV, class TR>
void ListAdjGrafo<TV,TR>::remover_Vertice(const TV &vert) const{
 Vertice<TV,TR> *vertice=encvert_conteudo(vert); // ve o conteudo do Vertice

if (vertice){ // se o vertice existir

Ramo<TV,TR> *ramos=vertice->apramo; // vai buscar os ramos associados

while(ramos){ // enquanto existir ramos

// Agora esta o problema não sei como apago os ramos

}

} // fecha o while

// supostamente faz delete do vertice já sem nenhum ramo associado

}

 

Se alguem que ajuda-se eu agradecia :)

 

Cumps

[José Enésio 4]

Hmm... delete?

Você pode definir um destrutor para os vértices e ramos que irá limpar os dados quando passar o delete, depois você aponta o ponteiro do ramo no vértice para NULL. Essa é a maneira que eu conheço de apagar dados, pelo menos. :)

[Atreyu 0]

Algo assim:

 

template<class, TV, class TR>
void ListAdjGrafo<TV,TR>::remover_Vertice(const TV &vert) const{
Vertice<TV,TR> *vertice=encvert_conteudo(vert); // ve o conteudo do Vertice

if (vertice){ // se o vertice existir

Ramo<TV,TR> *ramos=vertice->apramo; // vai buscar os ramos associados

while(ramos){ // enquanto existir ramos

if(ramos->apv)
delete ramo->apv;

if(ramos->apr)
delete ramos->apr;

// Actualiza

ramos=ramos->apr;
cout<<"ola"<<endl; // para ver quantos ramos apaga

}

} // fecha o while

delete vertice

}

Ora eu tenho dois ramos associados ao vertice que quero apagar, e de facto aparece 2 vezes "ola" no ecran....mas depois o programa crasha! lol

 

PS: apaga os posts em cima! enganei-me!

 

 

Esta imagem certamente irá ajudar:

 

[José Enésio 4]

Opa, aqui tem um problema:

 

if(ramos->apr)
delete ramos->apr;

// Actualiza

ramos=ramos->apr;

Como podemos tentar continuar checando os ramos se você vai definir o próximo ramo para o que acabou de ser deletado?

 

Minha sugestão? Já que está trabalhando com classes, utilize destrutores. Basta você definir no destrutor do vértice por exemplo, para ele pagar o ramo que está referenciado nele, e no ramo você define para deletar os dados ali que você quer deletar que estão referenciados nele, se meus cálculos estiverem certos basta dar um delete no primeiro vértice que ele vai deletando o resto. :D

[Atreyu 0]

Opa, aqui tem um problema:

 

if(ramos->apr)
delete ramos->apr;

// Actualiza

ramos=ramos->apr;

Como podemos tentar continuar checando os ramos se você vai definir o próximo ramo para o que acabou de ser deletado?

 

Minha sugestão? Já que está trabalhando com classes, utilize destrutores. Basta você definir no destrutor do vértice por exemplo, para ele pagar o ramo que está referenciado nele, e no ramo você define para deletar os dados ali que você quer deletar que estão referenciados nele, se meus cálculos estiverem certos basta dar um delete no primeiro vértice que ele vai deletando o resto. :D

 

Pois o que eu quero fazer e mesmo um destrutor de vertice. A questão é que tou a ficar com a cabeça aos papos com tantas voltas! lol

 

Como é que apagando um vertice ele apaga os ramos associados?...

 

Que granda Nó! E que isto parece ser bastante simples! :|

[José Enésio 4]

Destrutor é que nem construtor:

 

class Vertice
{
	Vertice()
	{
		cout << "Vértice criado!!!";
	}
	~Vertice()
	{
		cout << "Vértice deletado!!!";
	}
};

O destrutor é chamado quando um objeto é deletado. Isso pode acontecer no fim do programa, ou quando usamos delete por exemplo. A moral do que eu falei é a seguinte: se definirmos o destrutor do vértice para aplicar um delete no ramo que está referenciado dentro dele, e se o destrutor do ramo também aplicar delete nos dados dentro dele, no caso outros vértices, os destrutores serão chamados, e consequentemente vai ir deletando até ter um ramo que não aponta para vértice ou um vértice que não aponta para ramo, no caso deverá ser realizada uma comparação com NULL nos dados da classe, bem como no construtor da classe, definir os ponteiros todos para NULL.

[Atreyu 0]

Destrutor é que nem construtor:

 

class Vertice
{
	Vertice()
	{
		cout << "Vértice criado!!!";
	}
	~Vertice()
	{
		cout << "Vértice deletado!!!";
	}
};

O destrutor é chamado quando um objeto é deletado. Isso pode acontecer no fim do programa, ou quando usamos delete por exemplo. A moral do que eu falei é a seguinte: se definirmos o destrutor do vértice para aplicar um delete no ramo que está referenciado dentro dele, e se o destrutor do ramo também aplicar delete nos dados dentro dele, no caso outros vértices, os destrutores serão chamados, e consequentemente vai ir deletando até ter um ramo que não aponta para vértice ou um vértice que não aponta para ramo, no caso deverá ser realizada uma comparação com NULL nos dados da classe, bem como no construtor da classe, definir os ponteiros todos para NULL.

Ok! Ja percebi qualquer coisa! Nas minhas classes Vertice e Ramo já tem os seus destrutores.

Mas não tou a fazer nada...ou seja estão como ta em cima...agora dentro desses destrutores faço o delete do vertice e delete do ramo certo?

 

E depois no metodo remover_vertice chamo esse mesmo destrutor?

[José Enésio 4]

Na realidade me referia a algo assim:

 

class Ramo;

class Vertice
{
	public:
	Ramo* apramo;
	Vertice()
	{
		apramo = NULL;
	}
	~Vertice()
	{
		if(apramo != NULL)
		{
			delete apramo;
			apramo = NULL;
		}
	}
};

class Ramo
{
	public:
	Vertice* apv;
	Ramo* apr;
	Ramo()
	{
		apv = NULL;
		apr = NULL;
	}
	~Ramo()
	{
		if(apv != NULL)
		{
			delete apv;
			apv = NULL;
		}
		if(apr != NULL)
		{
			delete apr;
			apr = NULL;
		}
	}
}

O que acontece aqui: quando aplica delete no vértice, ele aplica delete no ramo, e o ramo vai aplicando delete nos vértices e ramos seguintes. Pelo menos na teoria é para dar certo, não tenho certeza se C++ tem algum super padrão que impede que uma solução simples como essa seja correta e no lugar sugere uma solução alternativa gigante e desnecessária. Já aconteceu comigo ^^'.

 

Para botar isso em funcionamento, basta aplicar delete no vértice que você não quer mais.

 

template<class, TV, class TR>
void ListAdjGrafo<TV,TR>::remover_Vertice(const TV &vert) const{
  Vertice<TV,TR> *vertice=encvert_conteudo(vert); // ve o conteudo do Vertice
  delete vertice;
}

[Atreyu 0]

Como se diz por ai: Valeu cara :)

 

Como o diz o ditado: percebes? Ou queres que te faça um desenho? lol

 

Obrigada pelo desenho :)

 

Ando agora a passar de java para c++ e isto não anda a ser facil!

[José Enésio 4]

Como se diz por ai: Valeu cara :)

 

Como o diz o ditado: percebes? Ou queres que te faça um desenho? lol

 

Obrigada pelo desenho :)

 

Ando agora a passar de java para c++ e isto não anda a ser facil!

Desenho é a melhor forma de explicar alguma coisa. Por isso que eu adoro desenhar, apesar de meus desenhos ficarem medonhos e portanto eu preferir guardá-los bem fundo em um caderno obscuro que guardo só deuses sabem onde! http://forum.imasters.com.br/public/style_emoticons/default/grin.gif

 

Java para C++ acho que deve ser bem chato mesmo, tentei passar para Java mas não achei muito prático, baixei um programão da Sun para desenvolver em Java, o bixo demorava muuuito pra iniciar e ainda era meio lento já rodando, resolvi desistir ^^ mas a moral é que a moral da linguagem é de certa forma parecida com C++... oras, a quem estou tentando enganar, a moral da maioria das linguagens que conheço e uso é muito parecida... talvez seja por isso que eu aprendi elas? hehe

 

Agora, já que os problemas estão resolvidos, acho que posso marcar este tópico como resolvido :)