questo è il codice del grafo con alcuni aggiornamenti.
grafoma.h
codice:
#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);
}
}
Rispondi quotando
