[C++] Grafo con lista delle adiacenze

[pietrol83]

ciao a tutti ho implementato la seguente struttura dati:

nodogl.h

#ifndef nodogl_h
#define nodogl_h

#include<iostream>
#include<stdlib.h>
#include "listap.h"

using namespace std;

template<class tipoelem>
class nodogl
{
   public:
      typedef struct nodoad
      {
         char *etichetta;
         int cursore;
         int peso;
      } adiacente;
      
      nodogl();
      
      void setetichetta(char *);
      void setvalore(tipoelem);
      void setposizione(int);
      void setadiacent(listap<struct nodoad> *);
      
      char *getetichetta();
      tipoelem getvalore();
      int getposizione();
      listap<struct nodoad> *getadiacent();
      
      nodogl<tipoelem> operator=(nodogl<tipoelem> );
      bool operator==(nodogl<tipoelem> ); 
   private:
      char *etichetta;
      tipoelem valore;
      int posizione;
      listap<struct nodoad> *adiacent;
};

#endif

template<class tipoelem>
nodogl<tipoelem>::nodogl()
{
   etichetta = NULL;
   posizione = -1;
   adiacent = new listap<tipoelem>;
}

template<class tipoelem>
void nodogl<tipoelem>::setetichetta(char *et)
{
   etichetta = et;
}

template<class tipoelem>
void nodogl<tipoelem>::setvalore(tipoelem val)
{
   valore = val;
}

template<class tipoelem>
void nodogl<tipoelem>::setposizione(int pos)
{
   posizione = pos;
}

template<class tipoelem>
void nodogl<tipoelem>::setadiacent(listap<struct nodoad> *ad)
{
   adiacent = ad;
}

template<class tipoelem>
char *nodogl<tipoelem>::getetichetta()
{
   return(etichetta);
}

template<class tipoelem>
tipoelem nodogl<tipoelem>::getvalore()
{
   return(valore);
}

template<class tipoelem>
int nodogl<tipoelem>::getposizione()
{
   return(posizione);
}

template<class tipoelem>
listap<struct nodoad> *nodogl<tipoelem>::getadiacent()
{
   return(adiacent);
}

template<class tipoelem>
nodogl<tipoelem> nodogl<tipoelem>::operator=(nodogl<tipoelem> nodo)
{
   this->setetichetta(nodo.getetichetta());
   this->setvalore(nodo.getvalore());
   this->setposizione(nodo.getposizione());
   this->setadiacent(nodo.getadiacent());
}

template<class tipoelem>
bool nodogl<tipoelem>::operator==(nodogl<tipoelem> nodo)
{
   bool etic = (this->getetichetta() == nodo.getetichetta());
   bool val = (this->getvalore() == nodo.getvalore());
   
   return(etic && val);
}

grafola.h

#ifndef grafolla_h
#define grafolla_h

#include<iostream>
#include<stdlib.h>
#include<assert.h>
//#include "listap.h"
#include "nodogl.h"

using namespace std;

template<class tipoelem>
class grafolla
{
   public:
      typedef nodogl<tipoelem> *nodo;
            
      grafolla();
      
      void creagrafo();
      bool grafovuoto();
      void insnodo(nodo);
      void insarco(nodo, nodo);
      void cancnodo(nodo);
      void cancarco(nodo, nodo);
      listap<nodog<tipoelem> > adiacenti(nodo);
      bool esistenodo(nodo);
      bool esistearco(nodo, nodo);
      tipoelem legginodo(nodo);
      void scrivinodo(nodo, tipoelem);
      int leggiarco(nodo, nodo);
      void scriviarco(nodo, nodo, int);
   private:
      nodogl<tipoelem> *nodi;
      int numnodi;
};

#endif

template<class tipoelem>
grafolla<tipoelem>::grafolla()
{
   this->creagrafo();
}

template<class tipoelem>
void grafolla<tipoelem>::creagrafo()
{
   numnodi = 0;
   nodi = new nodogl<tipoelem>[numnodi + 1];
}

template<class tipoelem>
bool grafolla<tipoelem>::grafovuoto()
{
   return(numnodi == 0);
}

template<class tipoelem>
void grafolla<tipoelem>::insnodo(typename grafolla<tipoelem>::nodo node)
{
   assert(!this->esistenodo(node));
   ++numnodi;
   
   cout << "inserire l'etichetta del nodo: ";
   char *c = new char[15];
   cin >> c;
   node->setetichetta(c);
   cout << "inserire il valore del nodo: ";
   tipoelem val;
   cin >> val;
   node->setvalore(val);
   node->setadiacent(NULL);
   node->setposizione(numnodi - 1);
      
   nodogl<tipoelem> *noditmp = new nodogl<tipoelem>[numnodi];
   if(numnodi > 1)
   {
      for(int i = 0; i < numnodi - 1; i++)
         noditmp[i] = nodi[i];
   }
   noditmp[numnodi - 1] = *node;
   nodi = noditmp;
}  

template<class tipoelem>
void grafolla<tipoelem>::insarco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2)
{
   assert(this->esistenodo(n1) && this->esistenodo(n2) && !this->esistearco(n1, n2));
   
   adiacente a;
   a.etichetta = strcpy(a.etichetta, n2->getetichetta());
   a.cursore = n2->getposizione();
   listap<struct nodoad> *l = nodi[n1->getposizione()].getadiacent();
   l->inslista(l->predlista(l->primolista()), a);
}

template<class tipoelem>
void grafolla<tipoelem>::cancnodo(typename grafolla<tipoelem>::nodo node)
{
   assert(this->esistenodo(node));
   
   //eliminazione degli archi (adiacenze) uscenti
   bool trovato = false;
   int i = 0;
   while(!trovato)
   {
      if(nodi[i].etichetta == node.etichetta)
      {
         listap<struct nodoad> *l = nodi[i].adiacent;
         while(!l->listavuota())
            l->canclista(l->primolista());
         trovato = true;
      }
      else
         i++;
   }
   
   //eliminazione degli archi (adiacenze) entranti
   for(int k = 0; k < numnodi; k++)
   {
      if(this->esistearco(nodi[k], node))
         this->cancarco(nodi[k], node);
      else
         k++;
   }
   
   //modifica del vettore dei nodi
   nodo *noditmp = new struct Nodo[numnodi - 1];
   int j;
   for(j = 0; j < i; j++)
      noditmp[j] = nodi[j];
   j = i + 1;
   for(j = i + 1; j < (numnodi - 1); j++)
   {
      noditmp[j - 1] = nodi[j];
      noditmp[j - 1].posizione -= 1;
   }
   nodi = noditmp;
   
   numnodi -= 1;
}

template<class tipoelem>
void grafolla<tipoelem>::cancarco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2)
{
   assert(this->esistenodo(n1) && this->esistenodo(n2) && this->esistearco(n1, n2));
   
   listap<struct nodoad> *l = nodi[n1.posizione].adiacent;
   typename listap<struct nodoad>::posizione p = l->primolista();
   bool trovato = false;
   while(!trovato && (p != l->predlista(l->primolista())))
   {
      if(l->leggilista(p).etichetta == n2.etichetta)
      {
         l->canclista(p);
         trovato = true;
      }
      else
         p = l->suclista(p);
   }
}

template<class tipoelem>
listap<nodog<tipoelem> > grafolla<tipoelem>::adiacenti(typename grafolla<tipoelem>::nodo node)
{
   assert(this->esistenodo(node));
   
   listap<struct Nodo> lis;
   if(nodi[node.posizione].adiacent != NULL)
   {
      listap<nodoad> l = *nodi[node.posizione].adiacent;
      typename listap<nodoad>::posizione p = l.primolista();
      while(p != l.predlista(l.primolista()))
      {
         lis.inslista(lis.predlista(lis.primolista()), nodi[l.leggilista(p).cursore]);
         p = l.suclista(p);
      }
   }
   
   return lis;
}

template<class tipoelem>
bool grafolla<tipoelem>::esistenodo(typename grafolla<tipoelem>::nodo node)
{
   bool esito = false;
   int i = 0;
   while(!esito && (i < numnodi))
   {
      if((nodi[i].etichetta == node.etichetta))
         esito = true;
      else
         i++;
   }
   
   return esito;
}

template<class tipoelem>
bool grafolla<tipoelem>::esistearco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2)
{
   assert(this->esistenodo(n1) && this->esistenodo(n2));
   
   listap<nodoad> *l = nodi[n1.posizione].adiacent;
   typename listap<nodoad>::posizione p = l->primolista();
   bool trovato = true;
   while(!trovato && (p != l->predlista(l->primolista())))
   {
      if(l->leggilista(p).etichetta == nodi[n2.posizione].etichetta)
         trovato = true;
      else
         p = l->suclista(p);
   }
   
   return trovato;
}

template<class tipoelem>
tipoelem grafolla<tipoelem>::legginodo(typename grafolla<tipoelem>::nodo node)
{
   assert(this->esistenodo(node));
   
   return(nodi[node->getposizione()].getvalore());
}

template<class tipoelem>
void grafolla<tipoelem>::scrivinodo(typename grafolla<tipoelem>::nodo node, tipoelem elem)
{
   cout << "node.posizione = " << node->getposizione() << "\n\n";
   cout << "node.etichetta = " << node->getetichetta() << "\n\n";
   cout << "nodi[node.posizione].etichetta = " << nodi[node->getposizione()].getetichetta() << "\n\n";
   assert(this->esistenodo(node));
   nodi[node->getposizione()].setvalore(elem);
}

template<class tipoelem>
int grafolla<tipoelem>::leggiarco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2)
{
   assert(this->esistearco(n1, n2));
   
   listap<nodoad> *l = nodi[n1.posizione].adiacent;
   typename listap<nodoad>::posizione p = l->primolista();
   bool trovato = false;
   
   while(!trovato && (p != l->predlista(l->primolista())))
   {
      if(l->leggilista(p).etichetta == n2.etichetta)
         trovato = true;
      else
         p = l->suclista(p);
   }
   
   return(l->leggilista(p).peso);
}

template<class tipoelem>
void grafolla<tipoelem>::scriviarco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2, int pes)
{
   assert(!this->esistearco(n1, n2));
   
   listap<nodoad> *l = nodi[n1.posizione].adiacent;
   typename listap<nodoad>::posizione p = l->primolista();
   bool trovato = false;
   
   while(!trovato && (p != l->predlista(l->primolista())))
   {
      if(l->leggilista(p).etichetta == n2.etichetta)
      {
         nodoad n = l->leggilista(p);
         n.peso = pes;
         l->scrivilista(p, n);
         trovato = true;
      }
      else
         p = l->suclista(p);
   }
}

testgrafo.cpp

#include<iostream>
#include<stdlib.h>
//#include"grafoma.h"
#include"grafolla.h"

using namespace std;

int main()
{
   grafolla<int> G;
   
   cout << "grafovuoto() = " << G.grafovuoto() << "\n\n";
   
   grafolla<int>::nodo n;
   G.insnodo(n);
   grafolla<int>::nodo n2;
   G.insnodo(n2);
   G.scrivinodo(n, 10);
   cout << "legginodo(n) = " << G.legginodo(n) << "\n\n";
   G.insarco(n, n2);
   system("pause");
   G.scriviarco(n, n2, 20);
   cout << "leggiarco(n, n2) = " << G.leggiarco(n, n2) << "\n\n";
   listap<nodog<int> > L;
   L = G.adiacenti(n);
   G.cancnodo(n);
   system("pause");
   cout << "esistearco(n, n2) = " << G.esistearco(n, n2) << "\n\n";
   L = G.adiacenti(n);
   listap<nodog<int> >::posizione p = L.primolista();

   cout << "esistenodo(n2) = " << G.esistenodo(n2) << "\n\n";
   cout << "esistenodo(n) = " << G.esistenodo(n) << "\n\n";
   
   system("pause");
   return 0;
}

quando compilo il tutto questa mi dà errore nella classe nodogl, dicendo che il prototipo del metodo getadiacent() non corrisponde a nessun metodo nella classe. ecco l'errore:

96 C:\Dev-Cpp\Strutture\Grafi\nodogl.h prototype for `listap<nodoad<tipoelem> >* nodogl<tipoelem>::getadiacent()' does not match any in class `nodogl<tipoelem>'

perchè? ho controllato varie volte e la segnatura del metodo corrisponde al prototipo.

[pietrol83]

ho risolto il problema di cui sopra. adesso ne sorge un altro. in pratica ho modificato il metodo setetichetta della classe nodogl nel seguente modo:

metodo void setetichetta(char *et)

template<class tipoelem>
void nodogl<tipoelem>::setetichetta(char *et)
{
   char *stringa = new char[15];
   etichetta = strcpy(stringa, et);
   stringa = NULL;
}

quando faccio il test, inserisco due nodi nel grafo. nell'inserimento mi viene chiesto di inserire l'etichetta del nodo e il valore dello stesso. per quanto riguarda il primo nodo tutto procede bene, ma nell'inserimento del secondo nodo quando arriva a settare il campo etichetta con il metodo setetichetta l'esecuzione va in crash. sicuramente sarà qualche problema di puntatori (maledetti!!!). perchè per il primo nodo va tutto bene e al secondo va in crash?

[pietrol83]

ok, sono riuscito a risolvere il problema. dovevo allocare la memoria ai nodi nel test.

[oregon]

Non capisco il senso delle 3 righe che hai postato. In realtà dovrebbe essere solamente

strcpy(etichetta, et);

[pietrol83]

si ora mi accorgo che è come dici tu. in precedenza pensavo fosse un problema del metodo setetichetta e ho messo ho scritto tutto quello. dopo che ho scoperto che bisognava semplicemente allocare la memoria ai nodi nel test ho capito che quelle righe non servono a niente.

[pietrol83]

ecco che sorgono altri problemi: nel test, una volta arrivato al metodo scriviarco nel file del test

G.scriviarco(n, n2, 20);

nell'asserzione del metodo mi dice che il nodo n non esiste, infatti ho provato a stampare il valore dell'etichetta del nodo e ho notato che la stringa viene persa. non capisco perchè datoche, controllando gli altri metodi, mi risulta che non esiste un'istruzione che mi cancella l'etichetta. come mai succede questo? e perchè proprio nell'asserzione del metodo scriviarco, visto che la setssa asserzione si trova anche nei metodi precedenti?

[pietrol83]

vi prego aiutatemi a scoprire dove ho sbagliato. :-(

[pietrol83]

ancora nessuno ha scoperto dov'è l'inghippo??? io sto impazzendo a cercare di capire qual'è la riga di codice che mi fa perdere il valore dell'etichetta del nodo.

[pietrol83]

ragazzi vi prego aiutatemi a capire dove cavolo non va bene questo maledetto codice. sono 3 giorni che mi controllo il codice e non riesco a venirne a capo. cerco di spiegare meglio cosa succede:

in pratica quando mando in esecuzione il test della struttura "testgrafo.cpp", una volta arrivato all'istruzione

cout << "esistearco(n, n2) = " << G.esistearco(n, n2) << "\n";

il metodo va in crash, precisamente nella chiamata, all'interno di esistearco(n, n2), ho messo delle istruzione che stampano l'etichetta sia dei nodi passati come argomento sia dei nodi che sono memotrizzati nel vettore, e ho notato che per quanto riguarda il primo nodo nel vettore (nodi[0]) l'etichetta viene persa mentre in una chiamata precedente del metodo esistearco tutto fila liscio. ho visto e rivisto il codice decine di volte ma non sono riuscito a trovare un'istruzione che altera l'etichetta del primo nodo nel vettore. di sicuro mi sfugge qualcosa, voi potere aiutarmi a capire che cosa ho combinato???