[C++] Grafo con lista di adiacenze

[pietrol83]

ciao a tutti, ho implementato la struttura dati grafo con la lista delle adiacenze. nel metodo insarco c'è un'istruzione che dà errore. posto il codice del metodo:

grafola.h

#ifndef grafolla_h
#define grafolla_h

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

using namespace std;

template<class tipoelem>
class grafolla
{
   public:
      typedef struct nodoad
      {
         char etichetta[15];
         int cursore;
         int peso;
      } adiacente;
      
      typedef struct Nodo
      {
         char etichetta[15];
         int posizione;
         tipoelem valore;
         listap<struct nodoad> *adiacent;
      } nodo;
      
      grafolla();
      
      void creagrafo();
      bool grafovuoto();
      void insnodo(nodo);
      void insarco(nodo, nodo);
      void cancnodo(nodo);
      void cancarco(nodo, nodo);
      listap<struct Nodo> 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:
      nodo *nodi;
      int numnodi;
};

#endif

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

template<class tipoelem>
void grafolla<tipoelem>::creagrafo()
{
   nodi = NULL;
   numnodi = 0;
}

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++;
   nodo *noditmp = new struct Nodo[numnodi];
   if(numnodi > 1)
   {
      for(int i = 0; i < numnodi - 1; i++)
         noditmp[i] = nodi[i];
      delete[] nodi;
   }
   cout << "inserire l'etichetta del nodo: ";
   cin >> node.etichetta;
   cout << "inserire il valore del nodo: ";
 
   cin >> node.valore;
   node.adiacent = NULL;
   node.posizione = numnodi - 1;
   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 = n2.etichetta;
   a.cursore = n2.posizione;
   listap<struct nodoad> *l = nodi[n1.posizione].adiacent;
   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<typename grafolla<tipoelem>::nodo> 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.posizione].valore);
}

template<class tipoelem>
void grafolla<tipoelem>::scrivinodo(typename grafolla<tipoelem>::nodo node, tipoelem elem)
{
   assert(this->esistenodo(node));
   
   nodi[node.posizione].valore = 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);
   }
}

l'errore che mi viene visualizzato è il seguente:

101 C:\Dev-Cpp\Strutture\Grafi\grafolla.h ISO C++ forbids assignment of arrays

perchè??? da quando in qua è proibito fare un assegnamento in un campo di un record??

[oregon]

Abbi pazienza ... qual è la linea a cui ti riferisci ? Indicala sempre quando c'è un errore ...

[pietrol83]

certo che l'ho indicata!! è quella in rosso. :-)

[oregon]

Ah ... non si vedeva facilmente ... (se solo l'avessi detto ... )

In ogni caso, mi sembra ovvio ... da quando in C (neanche in C++) un array lo assegni in quel modo ad un altro?

Se parliamo di una stringa di 15 char, come saprai, devi usare la funzione

strcpy

[pietrol83]

ho cambiato la realizzazione implementando per i nodi un'apposita classe. ecco i codici:
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.

[oregon]

Ma scusa, questo è un altro quesito ... che fine ha fatto quello precedente?

Hai usato la strcpy o no?

Così si fa confusione ...

[pietrol83]

ho scritto sempre qui per non creare un alro questio sempre sul grafo con lista di adiacenza.
in pratice è chome se stessi facendo tutto d'accapo, quindi non sono ancora arrivato alla strcpy perchè sono fermo su quell'errore di compilazione che non mi fa andare avanti e non riesco a spiegarmi perchè dato che il metoto e il prototipo corrispondono.

[pietrol83]

vi prego aiutatemi!!!

[LeleFT]

Se l'argomento principale della discussione è cambiato, si apre una nuova discussione; a maggior ragione se il codice sul quale si sta lavorando non è più quello preso in esame finora.

Il fatto di aver dato alla discussione un titolo "più generico" del contenuto stesso della discussione, non esime da quanto detto sopra, anzi, è un motivo in più per rendersi conto che il titolo usato non era adeguato.

Tutto questo nello spirito di voler mantenere un ordine logico delle discussioni all'interno del forum, in modo da agevolare anche gli altri utenti, non solo nel seguire una discussione, ma anche nella ricerca della stessa per eventuali soluzioni o spunti.

Detto questo, visto che il codice sul quale stai lavorando è completamente diverso, apri una nuova discussione (con un titolo più preciso).

Ciao.