Grafos

[Carlitox]

Olá,

Estou precisando de ajuda se poderem para um trabalho da Universidade.

O trabalho consiste em ler um ficheiro txt carregar os objectos para dois arrays, com alocação dinámica, vai aumentando a capacidade.

São eles Locais e Vias os objectos.

Depois de criados, vou criar um grafo usando a class: class ListAdjGrafo

Incluindo estas também

#include "Vertice.h"

#include "Ramo.h"

//class ListAdjGrafo, onde

#ifndef ListAdjGrafo_
#define ListAdjGrafo_

#include "Vertice.h"
#include "Ramo.h"


template<class TV,class TR>
class ListAdjGrafo
{
    private:
        int nvertices;
        int nramos;
        Vertice<TV,TR>* graf;

         Vertice<TV,TR>* encvert_conteudo(const TV& v) const;
        Vertice<TV,TR>* encvert_key(int numvert) const;

    public:
        ListAdjGrafo();
        ListAdjGrafo(const ListAdjGrafo<TV,TR>& G);
        ~ListAdjGrafo(); 

        int NumVert() const;
        int NumRamos() const;

        void juntar_vertice(const TV& vert);
        void juntar_ramo(const TR& rcont, const TV& vorigem, const TV& vdestino);
        
         int grau_entrada (const TV& vert) const;
        int grau_saida (const TV& vert) const;
        
        void escreve_grafo() const;
        
        //novo metodo para testar
        void remover_Vertice(const TV &vert);*/

};

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

template<class TV,class TR>
ListAdjGrafo<TV,TR>::ListAdjGrafo(const ListAdjGrafo<TV,TR>& G)
{
        Vertice<TV,TR>* apv=G.graf;
    Ramo<TV,TR>* apr;

    graf=NULL;
    int numvert=0;

    while (apv)        //adiciona os vertices
    {
       numvert++;
       Vertice<TV,TR>* vert=new Vertice<TV,TR>(apv->vconteudo,numvert); 
        if (graf == NULL)
       graf = vert;
    else
        {
       vert->apvertice = graf; 
       graf = vert; 
    }
        apv = apv->apvertice; 
    }
        nvertices = G.nvertices;

    apv=G.graf;
    while (apv)             //adiciona os ramos  
    {
        Vertice<TV,TR>* vorig = encvert_conteudo(apv->vconteudo);
        apr = apv->apramo;        
        while (apr)             
        {
           Ramo<TV,TR>* ramo = new Ramo<TV,TR>(apr->rconteudo,apr->apv);
           
           if (vorig->apramo == NULL)
              vorig->apramo=ramo;
           else
           {
               ramo->apr = vorig->apramo;
               vorig->apramo = ramo; 
           }
           apr = apr->apr;
        } 
        apv = apv->apvertice; 
    }
    nramos = G.nramos;
}



template<class TV,class TR>
ListAdjGrafo<TV,TR>::~ListAdjGrafo()
{
    Vertice<TV,TR>* apv = graf;
    Vertice<TV,TR>* tempv; 
    Ramo<TV,TR>* tempr;
    Ramo<TV,TR>* temp;

    while (apv)
    {
      tempr = apv->apramo; 
      while (tempr)
      {
          temp = tempr; 
          tempr = tempr->apr;
          delete temp; 
      }
      tempv = apv; 
          apv = apv->apvertice;
      delete tempv; 
    }
    graf = NULL;
    nvertices=0;
    nramos=0;
}

template<class TV,class TR>
int ListAdjGrafo<TV,TR>::NumVert() const
{
    return nvertices;
}

template<class TV,class TR>
int ListAdjGrafo<TV,TR>::NumRamos() const
{
    return nramos;
}


template<class TV,class TR>
Vertice<TV,TR>* ListAdjGrafo<TV,TR>::encvert_conteudo(const TV& v) const
{
    Vertice<TV,TR>* ap=graf;
    
    while (ap != NULL)
    {
        if (ap->vconteudo == v)
            return ap;
        else 
            ap=ap->apvertice;
    }
        return ap;
}

template<class TV,class TR>
Vertice<TV,TR>* ListAdjGrafo<TV,TR>::encvert_key(int numvert) const
{
    Vertice<TV,TR>* ap=graf;
    
    while (ap != NULL)
    {
        if (ap->key == numvert)
            return ap;
        else 
            ap=ap->apvertice;
    }
        return ap;
}

template<class TV,class TR>
void ListAdjGrafo<TV,TR>::juntar_vertice(const TV& vert)
{
    if (nvertices == 0)
    {
        nvertices++;
        Vertice<TV,TR>* vertice = new Vertice<TV,TR>(vert,nvertices);
        graf = vertice;
    }
    else
    {
        Vertice<TV,TR>* ap=graf;
        Vertice<TV,TR>* ant=graf;
        bool enc=false; 

        while (ap != NULL && !enc)
        {
        if (ap->vconteudo == vert)
          enc=true;
        else
        {
          ant = ap; 
          ap=ap->apvertice;
        }
            }
        if (!enc) //vertice não existe
        {
           nvertices++;    
           Vertice<TV,TR>* vertice=new Vertice<TV,TR>(vert,nvertices);
           ant->apvertice = vertice;
        }
    }
}

template<class TV,class TR>
void ListAdjGrafo<TV,TR>::juntar_ramo(const TR& rcont, const TV& vorig, const TV& vdest)
{
    Ramo<TV,TR>* tempramo=NULL; 
    Ramo<TV,TR>* ant;
    Vertice<TV,TR>* vertorig;
    Vertice<TV,TR>* vertdest=NULL;
     
    vertorig=encvert_conteudo(vorig);
    if (vertorig == NULL)
    {
        juntar_vertice(vorig);
        vertorig=encvert_conteudo(vorig);
    }
    vertdest=encvert_conteudo(vdest);
    if (vertdest == NULL)
    {
        juntar_vertice(vdest);
        vertdest=encvert_conteudo(vdest);
    }
    
    tempramo=vertorig->apramo;            //insere no fim da lista de ramos
        ant = tempramo; 
    while (tempramo != NULL)
    {
        ant = tempramo; 
        tempramo=tempramo->apr; 
    }
    if (tempramo == NULL)                             
    {
        tempramo = new Ramo<TV,TR>(rcont,vertdest);
        tempramo->apr= NULL;
        if (ant)
          ant->apr = tempramo;
        else
                  vertorig->apramo = tempramo; 
         nramos++;
    }
}


template<class TV,class TR>
int ListAdjGrafo<TV,TR>::grau_entrada (const TV& vert) const 
{
    int grau = 0;
    Vertice<TV,TR>* ap=graf;
    Ramo<TV,TR>* ap1;
    
     while(ap)
    {
        ap1=ap->apramo;
        while(ap1)
        {
            if (vert == ap1->apv->vconteudo) 
              grau++;
            
            ap1=ap1->apr; 
        }
        ap=ap->apvertice;
    }
    return grau;
}


template<class TV,class TR>
int ListAdjGrafo<TV,TR>::grau_saida (const TV& vert) const
{
    Vertice<TV,TR>* ap=encvert_conteudo(vert);
    Ramo<TV,TR>* ap1;
    int grau = 0;
    
    if (ap->vconteudo == vert)
    {
        ap1=ap->apramo;
        while (ap1)  
        {
            grau++;
            ap1=ap1->apr; 
        }
        ap=ap->apvertice;
    }
    return grau;
}

template<class TV,class TR>
void ListAdjGrafo<TV,TR>::escreve_grafo() const 
{
    Vertice<TV,TR>* v = graf;
    Ramo <TV,TR>* r;
    
    if (v == NULL)
        cout << "Grafo não definido !" << endl; 
    else
    {
        cout << "Num de locais " << nvertices  << endl; 
        cout << "Num vias " << nramos  << endl<< endl; 

        //percorre todos os vertices
        while (v != NULL)
        {    
            cout <<"--------------------------------- " << endl;
            cout << "O local: "<< endl;
            cout <<"--------------------------------- " << endl;
            cout << *(v->vconteudo) << endl;
            cout << "Liga-se: "<<endl;
            cout <<"--------------------------------- " << endl;

             r = v->apramo;

            //percorre todos os ramos
            while (r)
            {
                cout <<*(r->apv->vconteudo) << endl;

                cout <<"Via de ligacao "<< endl;
                cout <<*(r->rconteudo) << endl;
                r = r->apr;
            }   
            cout<<endl;
            v = v->apvertice;
        }
    }
}

void ListAdjGrafo<TV,TR>::remover_Vertice(const TV &vert) {
   Vertice<TV,TR>* v=graf;
   Vertice<TV,TR>* v2=graf;
    Ramo<TV,TR>* ap1;    
    Ramo<TV,TR>* ap2;    
    if (v == NULL)
        cout << "Grafo não definido !" << endl; 
    else
    {
        while (v != NULL){
            ap2=v->apramo;
            ap1=v->apramo;
            if (v->vconteudo==vert)//caso o conteudo seja igual ao vertice, elimina todos os ramos com origem em vert
            {
                while (ap1)
                {
                    ap2=ap1;
                    ap1=ap1->apr;
                    ap2->apr=NULL;
                    delete ap2;
                    nramos--;
                }
                v->apramo=NULL;
            }
            else {        //caso o conteudo não seja igual ao vertice    
                while (ap1){

                    if(ap1->apv->vconteudo==vert){ //verifica se  para cada vertice, existe algum ramo que aponte para o vert
                        if (v->apramo==ap1)
                            v->apramo=ap1->apr;
                        else
                        ap2->apr=ap1->apr;                        
                        ap1=NULL;
                        delete ap1;                        
                        nramos--;                        
                    } 
                    else {
                    ap2=ap1;
                    ap1=ap1->apr;}
            
                }
            }
        v=v->apvertice;
        }    
        v=graf;
        v2=graf;
        while (v != NULL){
        //    int verticesPercorridos=0;
            bool encontrouVertice=false;
            while (v){
                if (encontrouVertice){
                    v->key=v->key--;
                }
                if(v->vconteudo==vert){ //verifica se  para cada vertice, existe algum ramo que aponte para o vert
                    encontrouVertice=true;
                    if (graf==v)
                            graf=v->apvertice;
                        else
                            v2->apvertice=v->apvertice;                        
                        v=NULL;
                        delete v;                        
                        nvertices--;
                        v=v2->apvertice;
                }else{
                    v2=v;
                    v=v2->apvertice;
                }
            }
        }
    }
}

#endif

class vertice

#ifndef Vertice_
#define Vertice_



template<class TV,class TR>
class ListAdjGrafo;

template<class TV,class TR>
class Ramo;

template<class TV, class TR>    //Classe dos vertices do grafo
class Vertice
{
    friend class ListAdjGrafo<TV, TR>;

    private:
        TV vconteudo;
        int key;
        Vertice<TV,TR>* apvertice;
        Ramo<TV,TR>* apramo;

    public:
        Vertice();
        Vertice(const TV& conteudo, int k);
        Vertice(const Vertice<TV,TR>& v);
        ~Vertice();

};

template<class TV,class TR>
Vertice<TV,TR>::Vertice()
{
    key = 0;
    apvertice=NULL;
    apramo=NULL;
}

template<class TV,class TR>
Vertice<TV,TR>::Vertice(const TV& conteudo, int k)
{
    vconteudo=conteudo;
    key = k;
    apvertice=NULL;
    apramo=NULL;
}

template<class TV,class TR>
Vertice<TV,TR>::Vertice(const Vertice<TV,TR>& v)
{
    vconteudo = v.vconteudo;
    key = v.key;
    apvertice=v.apvertice;
    apramo=v.apramo;
}

template<class TV,class TR>
Vertice<TV,TR>::~Vertice()
{

}


#endif

Class ramo

#ifndef Ramo_
#define Ramo_

template<class TV,class TR>
class ListAdjGrafo;

template<class TV,class TR>
class Vertice;

template<class TV,class TR>   //Class representativa dos ramos que ligam vertices do grafo
class Ramo
{
    friend class ListAdjGrafo<TV,TR>;
    
    private:
        TR rconteudo;
        Vertice<TV,TR>* apv;
        Ramo<TV,TR>* apr;
    
    public:
        Ramo();
        Ramo(const TR& rcont, Vertice<TV,TR>* pv);
        Ramo(const Ramo<TV,TR>& r);
        ~Ramo();
};

template<class TV,class TR>
Ramo<TV,TR>::Ramo()
{
    apv=NULL;
    apr=NULL;
}

template<class TV,class TR>
Ramo<TV,TR>::Ramo(const TR& rcont, Vertice<TV,TR>* pv)
{
    rconteudo=rcont;
    apv=pv;
    apr=NULL;
}

template<class TV,class TR>
Ramo<TV,TR>::Ramo(const Ramo<TV,TR>& r)
{
    rconteudo=r.rconteudo;
    apv=r.apv;
    apr=r.apr;
}

template<class TV,class TR>
Ramo<TV,TR>::~Ramo()
{

}

#endif

Já fiz alguns metodos, na class ListAdjGrafo, falta-me ainda este que queria a vossa ajuda.

- apresentar todos os percursos possíveis entre dois locais (cidades, vilas ou locais de interesse

turístico, estas são classes derivadas de locais)

Conta-Caminhos (apinicio, apfim, vector, cont)

vector[apinicio→key]=1

apramo= apinicio→apramo

Enqto apramo /= Nulo

nvdest= apramo→apv→key

Se (apinicio→vconteudo = = apfim→vconteudo)

cont++

Se (vector[nvdest] == 0)

Conta-Caminhos(apramo→apv,apfim,vector,cont)

apramo = apramo→apr

FEnqto

vector[apinicio→key] = 0 ;

Fim Conta-Caminhos

Obrigado pela atençao

Editado Novembro 28, 2008 por Carlitox