PDA

Visualizza la versione completa : [C++] Grafo con matrice di adiacenza


pietrol83
10-05-2012, 15:57
ciao a tutti, ho implementato la struttura dati grafo con matrice di adiacenza. in compilazione mi viene segnalato un errore che non riesco a capire. chi mi spiega cosa ho combinato???

questo è il codice del grafo:

grafoma.h


#ifndef grafoma_h
#define grafoma_h

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

using namespace std;

template<class tipoelem>
class grafoma : public grafo<tipoelem, typename grafoma<tipoelem>::nodo>
{
public:
typedef struct Nodo
{
tipoelem etichetta;
int ordine;
bool mark;
} nodo;

typedef struct Arco
{
nodo sorgente;
nodo destinazione;
int peso;
} arco;

grafoma();

void creagrafo();
bool grafovuoto();
void insnodo(nodo);
void insarco(nodo, nodo);
void cancnodo(nodo);
void cancarco(nodo, nodo);
listap<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:
listap<nodo> nodi;
listap<arco> archi;

int numnodi;
int numarchi;

bool **grafo;
};
#endif

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

template<class tipoelem>
void grafoma<tipoelem>::creagrafo()
{
numnodi = 0;
numarchi = 0;
grafo = NULL;
}

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

template <class tipoelem> //insnodo
void grafoma<tipoelem>::insnodo(nodo node)
{
cout << "inserire l'etichetta del nodo: ";
cin >> node.etichetta;

assert(!this->esistenodo(node));
node.ordine = nodi + 1;
node.mark = true;
nodi.inslista(nodi.predlista(nodi.primolista()));
numnodi++;
bool tmp[numnodi][numnodi];
for(int i = 0; i < numnodi - 1; i++) //creo una matrice temp per copiare quella originale
{
for(int j = 0; j < numnodi - 1; j++)
tmp[i][j] = grafo[i][j];
}
for(int i = 0; i < numnodi; i++) //qui inizializzo la nuova colonna(avendo aggiunto un nodo la matrice aumenta) con gli 0
tmp[i][numnodi - 1] = false;
for(int j = 0; j < numnodi; j++) //qui inizializzo la nuova riga con gli 0
tmp[numnodi - 1][j] = false;
grafo = tmp;
}

template<class tipoelem>
void grafoma<tipoelem>::insarco(nodo n1, nodo n2)
{
assert(this->esistenodo(n1) && this->esistenodo(n2) && !this->esistearco(n1, n2));
arco a;
a.sorgente = n1;
a.destinazione = n2;
grafo[n1.ordine][n2.ordine] = true;
archi.inslista(archi.primolista(), a);
numarchi++;
}

template<class tipoelem>
void grafoma<tipoelem>::cancnodo(nodo node)
{
assert(this->esistenodo(node));
listap<nodo> L;
L = this->adiacenti(node);
if(!L.listavuota())
{
typename listap<nodo>::posizione p = L.primolista();
while(!L.listavuota());
{
if(this->esistearco(node, L.leggilista(p)))
this->cancarco(node, L.leggilista(p));
if(this->esistearco(L.leggilista(p), node))
this->cancarco(L.leggilista(p), node);
}

for(int i = 0; i < numnodi; i++)
grafo[i][node.ordine] = false;
for(int j = 0; j < numnodi; j++)
grafo[node.ordine][j] = false;

node.mark = false;
}
}

template<class tipoelem>
void grafoma<tipoelem>::cancarco(nodo n1, nodo n2)
{
assert(this->esistearco(n1, n2);
grafo[n1.ordine][n2.ordine] = false;
bool trovato = false;
typename listap<arco>::posizione p = archi.primolista();
while(!trovato)
{
if((archi.leggilista(p).sorgento == n1) && (archi.leggilista(p).destinazione == n2))
{
archi.canclista(p);
trovato = true;
}
else
p = archi.suclista(p);
}
}

template<class tipoelem>
listap<typename grafoma<tipoelem>::nodo> grafoma<tipoelem>::adiacenti(nodo node)
{
listap<nodo> L;
typename listap<arco>::posizione p = archi.primolista();
while(p != archi.predlista(archi.primolista()))
{
if(this->esistearco(node, archi.leggilista(p)))
L.inslista(L.primolista(), archi.leggilista(p);
else
p = archi.suclista(p);
}

return L;
}

template<class tipoelem>
bool grafoma<tipoelem>::esistenodo(nodo node)
{
bool esiste = false;
typename listap<nodo>::posizione p = nodi.primolista();

while(!trovato && (p != nodi.predlista(nodi.primolista())))
{
if(nodi.leggilista(p).etichetta == node.etichetta)
esiste = true;
else
p = nodi.suclista(p);
}

return esiste;
}

template<class tipoelem>
bool grafoma<tipoelem>::esistearco(nodo n1, nodo n2)
{
assert(this->esistendo(n1) && this->esistenodo(n2));
bool esiste = false;
typename listap<arco>::posizione p = archi.primolista();

while(!trovato && (p != archi.predlista(archi.primolista())))
{
if((archi.leggilista(p).soregente == n1) && (archi.leggilista(p).destinazione == n2))
esiste = true;
else
p = archi.suclista(p);
}

return esiste;
}

template<class tipoelem>
tipoelem grafoma<tipoelem>::legginodo(nodo node)
{
assert(this->esistenodo(node));
return(node.etichetta);
}

template<class tipoelem>
void grafoma<tipoelem>::scrivinodo(nodo node, tipoelem elem)
{
assert(this->esistenodo(node));
node.etichetta = elem;
}

template<class tipoelem>
int grafoma<tipoelem>::leggiarco(nodo n1, nodo n2)
{
assert(this->esistearco(n1, n2));
typename listap<arco>::posizione p = archi.primolista();
bool trovato = false;
while(!trovato)
{
if((archi.leggilista(p).sorgente == n1) && (archi.leggilista(p).destinazione == n2))
trovato = true;
else
p = archi.suclista(p):
}

return(archi.leggilista(p));
}

template<class tipoelem>
void grafoma<tipoelem>::scriviarco(nodo n1, nodo n2, int pes)
{
assert(this->esistearco(n1, n2));
typename listap<arco>::posizione p = archi.primolista();
bool trovato = false;
while(!trovato)
{
if((archi.leggilista(p).sorgente == n1) && (archi.leggilista(p).destinazione == n2))
{
trovato = true;
archi.leggilista(p).peso = pes;
}
else
p = archi.suclista(p):
}
}

(!!!!!!!)


l'errore che mi viene segnalato è il seguente:
254:2 C:\Dev-Cpp\Strutture\Grafi\grafoma.h unterminated argument list invoking macro "assert"

tra l'altro la riga 254 è quella dove ci sono i punti esclamativi (!!!!!!!!). perchè mi viene segnalato un erroe proprio lì?? e cosa vuoel significare???

Who am I
10-05-2012, 16:32
All' inizio del metodo cancarco hai scritto questa asserzione:



assert(this->esistearco(n1, n2);


Dimenticandoti di chiudere la parentesi tonda.
Ma non ho idea perché l' errore te lo segnala alla riga 254, credo dipenda dal parser.

pietrol83
13-05-2012, 10:54
è sorto un altro problema: nel metodo cancarco, nell'if mi viene segnalato un errore nel confronto col nodo n2, visualizzando il seguente errore:

148 C:\Dev-Cpp\Strutture\Grafi\grafoma.h no match for 'operator==' in '(((listap<grafoma<int>::Arco>*)((grafoma<int>*)this)) + 8u)->listap<tipoelem>::leggilista [with tipoelem = grafoma<int>::Arco](p).grafoma<int>::Arco::destinazione == n2'

perchè l'errore è sul confronto col nodo n2 e non anche sul nodo n1 dato che i confronti sono dello stesso tipo??? inoltre perchè l'operatore == non può essere utilizzato dato che il confronto è su due record???

oregon
13-05-2012, 11:01
sorgento ???

pietrol83
13-05-2012, 11:22
non fare caso al termine sorgento, il codice l'ho pubblicato giorni fa, poi l'ho corretto e l'errore è sempre quello.

oregon
13-05-2012, 11:32
Beh, quando lo compilo ho un po' di errori che tu dici di aver corretto ... se non pubblichi il codice "corretto", "aggiornato" e "completo" è inutile perdere tempo ...

pietrol83
13-05-2012, 11:40
ok allora ti pubblico il link con tutti i codici necessari.

https://skydrive.live.com/redir.aspx?cid=f9fe0d3e54198821&resid=F9FE0D3E54198821!595&parid=F9FE0D3E54198821!514&authkey=!ACl3N5sGad1NNpU

questo è tutto il codie. per il momento sto correggento l'errore sulla riga if del metodo cancarco, se ce ne sono altri (e ne sono sicuro che cene sono) li correggerò successivamente.

pietrol83
14-05-2012, 13:53
nessuno mi aiuta a capire dove ho sbagliato????

pietrol83
14-05-2012, 14:15
questo è il codice del grafo con alcuni aggiornamenti.

grafoma.h


#ifndef grafoma_h
#define grafoma_h

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

using namespace std;

template<class tipoelem>
struct Nodo
{
tipoelem etichetta;
int ordine;
bool mark;
};

template<class tipoelem>
class grafoma : public grafo<tipoelem, struct Nodo<tipoelem> >
{
public:
typedef struct Nodo<tipoelem> nodo;
typedef struct Arco
{
nodo sorgente;
nodo destinazione;
int peso;
} arco;

grafoma();

void creagrafo();
bool grafovuoto();
void insnodo(nodo);
void insarco(nodo, nodo);
void cancnodo(nodo);
void cancarco(nodo, nodo);
listap<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:
listap<nodo> nodi;
listap<arco> archi;

int numnodi;
int numarchi;

bool **grafo;
};
#endif

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

template<class tipoelem>
void grafoma<tipoelem>::creagrafo()
{
numnodi = 0;
numarchi = 0;
grafo = NULL;
}

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

template <class tipoelem> //insnodo
void grafoma<tipoelem>::insnodo(nodo node)
{
cout << "inserire l'etichetta del nodo: ";
cin >> node.etichetta;

assert(!this->esistenodo(node));
node.ordine = numnodi + 1;
node.mark = true;
nodi.inslista(nodi.predlista(nodi.primolista()), node);
numnodi++;
bool **tmp;
tmp = new bool*[numnodi];
for(int i = 0; i < numnodi - 1; i++) //creo una matrice temp per copiare quella originale
{
for(int j = 0; j < numnodi - 1; j++)
tmp[i][j] = grafo[i][j];
}
for(int i = 0; i < numnodi; i++) //qui inizializzo la nuova colonna(avendo aggiunto un nodo la matrice aumenta) con gli 0
tmp[i][numnodi - 1] = false;
for(int j = 0; j < numnodi; j++) //qui inizializzo la nuova riga con gli 0
tmp[numnodi - 1][j] = false;
grafo = tmp;
}

template<class tipoelem>
void grafoma<tipoelem>::insarco(nodo n1, nodo n2)
{
assert(this->esistenodo(n1) && this->esistenodo(n2) && !this->esistearco(n1, n2));
arco a;
a.sorgente = n1;
a.destinazione = n2;
grafo[n1.ordine][n2.ordine] = true;
archi.inslista(archi.primolista(), a);
numarchi++;
}

template<class tipoelem>
void grafoma<tipoelem>::cancnodo(nodo node)
{
assert(this->esistenodo(node));
listap<nodo> L;
L = this->adiacenti(node);
if(!L.listavuota())
{
typename listap<nodo>::posizione p = L.primolista();
while(!L.listavuota());
{
if(this->esistearco(node, L.leggilista(p)))
this->cancarco(node, L.leggilista(p));
if(this->esistearco(L.leggilista(p), node))
this->cancarco(L.leggilista(p), node);
}

for(int i = 0; i < numnodi; i++)
grafo[i][node.ordine] = false;
for(int j = 0; j < numnodi; j++)
grafo[node.ordine][j] = false;

node.mark = false;
}
}

template<class tipoelem>
void grafoma<tipoelem>::cancarco(typename grafoma<tipoelem>::nodo n1, typename grafoma<tipoelem>::nodo n2)
{
assert(this->esistearco(n1, n2));
grafo[n1.ordine][n2.ordine] = false;
bool trovato = false;
typename listap<arco>::posizione p = archi.primolista();
while(!trovato)
{
if((archi.leggilista(p).sorgente == n1) && (archi.leggilista(p).destinazione == n2))
{
archi.canclista(p);
trovato = true;
}
else
p = archi.suclista(p);
}
}

template<class tipoelem>
listap<typename grafoma<tipoelem>::nodo> grafoma<tipoelem>::adiacenti(nodo node)
{
listap<nodo> L;
typename listap<arco>::posizione p = archi.primolista();
while(p != archi.predlista(archi.primolista()))
{
if(this->esistearco(node, archi.leggilista(p)))
L.inslista(L.primolista(), archi.leggilista(p));
else
p = archi.suclista(p);
}

return L;
}

template<class tipoelem>
bool grafoma<tipoelem>::esistenodo(nodo node)
{
bool esiste = false;
typename listap<nodo>::posizione p = nodi.primolista();

while(!esiste && (p != nodi.predlista(nodi.primolista())))
{
if(nodi.leggilista(p).etichetta == node.etichetta)
esiste = true;
else
p = nodi.suclista(p);
}

return esiste;
}

template<class tipoelem>
bool grafoma<tipoelem>::esistearco(nodo n1, nodo n2)
{
assert(this->esistendo(n1) && this->esistenodo(n2));
bool esiste = false;
typename listap<arco>::posizione p = archi.primolista();

while(!esiste && (p != archi.predlista(archi.primolista())))
{
if((archi.leggilista(p).soregente == n1) && (archi.leggilista(p).destinazione == n2))
esiste = true;
else
p = archi.suclista(p);
}

return esiste;
}

template<class tipoelem>
tipoelem grafoma<tipoelem>::legginodo(nodo node)
{
assert(this->esistenodo(node));
return(node.etichetta);
}

template<class tipoelem>
void grafoma<tipoelem>::scrivinodo(nodo node, tipoelem elem)
{
assert(this->esistenodo(node));
node.etichetta = elem;
}

template<class tipoelem>
int grafoma<tipoelem>::leggiarco(nodo n1, nodo n2)
{
assert(this->esistearco(n1, n2));
typename listap<arco>::posizione p = archi.primolista();
bool trovato = false;
while(!trovato)
{
if((archi.leggilista(p).sorgente == n1) && (archi.leggilista(p).destinazione == n2))
trovato = true;
else
p = archi.suclista(p);
}

return(archi.leggilista(p));
}

template<class tipoelem>
void grafoma<tipoelem>::scriviarco(nodo n1, nodo n2, int pes)
{
assert(this->esistearco(n1, n2));
typename listap<arco>::posizione p = archi.primolista();
bool trovato = false;
while(!trovato)
{
if((archi.leggilista(p).sorgente == n1) && (archi.leggilista(p).destinazione == n2))
{
trovato = true;
archi.leggilista(p).peso = pes;
}
else
p = archi.suclista(p);
}
}

Loading