Grafo : contare gli archi tra due nodi
Salve ragazzi..vorrei un aiuto su come realizzare un metodo che mi faccia contare gli archi tra due nodi di un grafo passati come parametro , sto impazzendo e non riesco proprio ..
questa è la mia realizzazione di grafo, realizzato con matrice di adiacenza
questa è la mia realizzazione di grafo, realizzato con matrice di adiacenza
static const int maxnodi = 50;
int const NULLO = -1;
template<class T>
class grafo
{
public:
typedef int peso;
typedef int nodo ;
typedef T tipoelem;
grafo();
~grafo();
void creagrafo();
bool grafovuoto();
void insnodo(nodo);
void insarco(nodo,nodo,peso);
bool esistenodo(nodo);
bool esistearco(nodo,nodo);
peso pesoArco(nodo,nodo);
lista<int> adiacenti(nodo);
void cancnodo(nodo);
void cancarco(nodo,nodo);
void scrivinodo(tipoelem,nodo);
tipoelem legginodo(nodo);
void setvisited(nodo, bool); //introduco questi 2 operatori per settare
bool getvisited(nodo ); //e recuperare il flag visited dei nodi
//necessario per le visite del grafo
void falsa_visited(); //reimposta il flag visited a tutti false
void DFS(nodo); // esplorazione del grafo in profondità
int find(tipoelem);
int contaNodiEtichettati(tipoelem);
int archiUscenti(nodo);
int archiEntranti(nodo);
void popola();
int LunghezzaCammino(nodo,nodo);
private:
tipoelem label[maxnodi]; //etichetta del nodo
bool mark[maxnodi]; //indica se un nodo e' attivo o meno
bool visited[maxnodi]; //utile per le visite
int arc[maxnodi][maxnodi]; //matrice di adiacenza
int totale_nodi;
int totale_archi;
};
template<class T>
grafo<T>::grafo() { creagrafo(); }
template<class T>
grafo<T>::~grafo() {}
template<class T>
void grafo<T>::creagrafo()
{
totale_archi=0;
totale_nodi=0;
for(int i = 0 ; i<maxnodi ; i++ ){
label[i] = '\0' ;
mark[i] = false ;
visited[i] = false ;
for( int j = 0 ; j < maxnodi ; j++) {
arc[i][j] = NULLO ;
}
}
}
template<class T>
bool grafo<T>::grafovuoto()
{
for(int i = 0 ; i <maxnodi; i++) {
if( mark[i]) return false ;
}
return true;
}
template<class T>
void grafo<T>::insnodo(grafo<T>::nodo u)
{
totale_nodi++;
if(u>=0 && u<maxnodi )
if(!mark) mark = true;
}
template<class T>
void grafo<T>::insarco(grafo<T>::nodo u, grafo<T>::nodo v, grafo<T>::peso p)
{
totale_archi++;
if(u>=0 && u<maxnodi && v>=0 && v<maxnodi ) {
if( mark && mark[v] && !esistearco(u,v) && !esistearco(v,u) ) {
arc[v] = p; // indicando così che sussiste l'arco
}
}
}
template<class T>
typename grafo<T>::peso grafo<T>::pesoArco(grafo<T>::nodo n , grafo<T>::nodo m)
{
if(esistearco(n,m))
return arc[n][m];
}
template<class T>
bool grafo<T>::esistenodo(grafo<T>::nodo u)
{
if(u>=0 && u<maxnodi)
return mark;
}
template<class T>
bool grafo<T>::esistearco(grafo<T>::nodo n ,grafo<T>:: nodo v)
{
if(n>0 && n<=maxnodi && v>0 && v<=maxnodi)
if(arc[n][v]==NULLO)
return false;
else return true;
}
template<class T>
lista<int> grafo<T>::adiacenti(grafo<T>::nodo u)
{
lista<int> L;
cella<int>* p = L.primoLista();
for(int i = 0 ; i<maxnodi; i++) {
if(arc[i] != NULLO) {
L.insLista(i,p);
p = L.succLista(p);
}
}
return L;
}
template<class T>
void grafo<T>::cancnodo(grafo<T>::nodo u)
{
if(u>=0 && u<=maxnodi && esistenodo(u) && adiacenti(u).listaVuota() )
mark = false;
totale_nodi--;
}
template<class T>
void grafo<T>::cancarco(grafo<T>::nodo u ,grafo<T>:: nodo n)
{
if( u>=0 && u<=maxnodi && n>=0 && n<=maxnodi && esistearco(u,n) && esistearco(n,u)){
arc[n] = NULLO;
arc[n] = NULLO;
}
totale_archi--;
}
template<class T>
void grafo<T>::scrivinodo(grafo<T>::tipoelem el , grafo<T>::nodo n)
{
if(n>=0&&n<=maxnodi && esistenodo(n))
label[n] = el;
}
template<class T>
typename grafo<T>::tipoelem grafo<T>::legginodo(grafo<T>::nodo n)
{
if(n>=0 && n<= maxnodi && esistenodo(n))
return(label[n]);
}
template<class T>
void grafo<T>::setvisited(grafo<T>::nodo n , bool vis)
{
if(n>=0 && n<maxnodi && esistenodo(n))
visited[n] = vis;
}
template<class T>
bool grafo<T>::getvisited(grafo<T>::nodo n)
{
if(n>=0 && n<maxnodi && esistenodo(n))
return visited[n];
}
template<class T>
void grafo<T>::DFS(grafo<T>::nodo n)
{
if(esistenodo(n)){
setvisited(n,true);
cout<<"["<<legginodo(n)<<"]"<<"-->";
lista<int> L = adiacenti(n) ;
if(!L.listaVuota()) {
cella<int> * p = L.primoLista();
while(!L.fineLista(p)) {
nodo v= L.leggiLista(p);
if(esistearco(n,v)){
cout << "(" << n << "," << v <<")";
if (getvisited(v)==false)
DFS(v);
}
p = L.succLista(p);
}
}
}
}
template<class T>
int grafo<T>::find(grafo<T>::tipoelem el)
{
int trovato = 0 ;
int i = 0 ;
while(label[i]!=el && i< maxnodi-1){
i++;
if(label[i]==el)
trovato = 1;
}
return trovato;
}
template<class T>
int grafo<T>::contaNodiEtichettati(grafo<T>::tipoelem el)
{
int n = 0 ;
for(int i = 0 ; i<maxnodi-1 ; i++){
if(label[i]==el)
n++ ;
}
return n;
}
template<class T>
int grafo<T>::archiUscenti(grafo<T>::nodo n)
{
int L = 0 ;
for(int j =1 ; j<maxnodi-1;j++){
if(esistearco(n,j)){
L++;
}
}
return L;
}
template<class T>
int grafo<T>::archiEntranti(grafo<T>::nodo n)
{
int L = 0 ;
for(int j =1 ; j<maxnodi-1;j++){
if(esistearco(j,n)){
L++;
}
}
return L;
}
Risposte
"slevyn":
Salve ragazzi..vorrei un aiuto su come realizzare un metodo che mi faccia contare gli archi tra due nodi di un grafo passati come parametro , sto impazzendo e non riesco proprio ..
questa è la mia realizzazione di grafo, realizzato con matrice di adiacenza
Scusa, ma se hai la matrice di adiacenza non basta prendere la entry relativa?
O forse intendi i cammini (quindi composti da piu' archi)? (In questo caso devi prendere le potenze della matrice di adiacenza).
Nella entry dovrebbe esserci il numero di cammini da-a, se non mi sbaglio, no?
Se voglio calcolare il cammino dal nodo i al nodo j , devo effettuare la potenza della matrice e prendere l'elemento i,j. L'elemento i,j sarà il valore del cammino . Ma come faccio ad effettuare la potenza della matrice ..e soprattutto a cosa và elevata ?
ho fatto così :
template<class T>
int grafo<T>::LunghezzaCammino(grafo<T>::nodo n , grafo<T>::nodo m)
{
int i ,j;
double arc2[maxnodi][maxnodi];
for(int i=1;i<maxnodi-1;i++){
for(int j=1;j<maxnodi-1;j++){
arc2[i][j]= pow(arc[i][j],maxnodi);
}
}
return arc2[n][m];
}
"slevyn":
ho fatto così :
template<class T> int grafo<T>::LunghezzaCammino(grafo<T>::nodo n , grafo<T>::nodo m) { int i ,j; double arc2[maxnodi][maxnodi]; for(int i=1;i<maxnodi-1;i++){ for(int j=1;j<maxnodi-1;j++){ arc2[i][j]= pow(arc[i][j],maxnodi); } } return arc2[n][m]; }
Ferma le macchine!
Anzitutto avevo capito male la domanda (my fault): tu vuoi sapere quanto e' lungo il cammino tra un nodo e l'altro, io avevo capito tutt'altro (in effetti mi sembrava troppo semplice...).
Allora, per potenza di una matrice si intende la matrice moltiplicata per se stessa, non la potenza di ogni singola entry come fai tu nello stralcio qui sopra.
Ma ad ogni modo, per risolvere il tuo problema ci sono algoritmi migliori computazionalmente parlando, per esempio puoi implementare un algoritmo tipo A*, che costa sicuramente molto meno di una potenza di matrice, e soprattutto scala sicuramente meglio per grafi grandi.
E come effettuo il prodotto di una matrice per se stessa? E poi non ho capito quante volte si dovrebbe moltiplicare per se stessa la matrice...io non ho mai visto un prodotto di una matrice per se stessa...io ho elevato apposta le entry...
Scusa ma il tuo problema è:
avendo due nodi, contare gli archi passanti da tutti i cammini validi (togliendo gli archi uguali)?
avendo due nodi, contare gli archi passanti da tutti i cammini validi (togliendo gli archi uguali)?
Il mio problema è trovare la lunghezza del cammino tra due nodi (ovvero quanti sono gli archi che li separano)
"slevyn":
Il mio problema è trovare la lunghezza del cammino tra due nodi (ovvero quanti sono gli archi che li separano)
Quale cammino, l'articolo "del" è il fucro:
uno qualsiasi? il minimo, il massimo?
Penso tu sappia che un cammino non è unico (dipende dal grafo ovviamente), devi specificare che cammino cerchi, se uno qualunque o una tipologia in particolare.
Un cammino qualsiasi
"slevyn":
Un cammino qualsiasi
Devi specificare un cammino, perche' altrimenti l'output della funzione non e' univocamente determinato.
In genere si cerca quello piu' corto. Per questo consigliavo A*, nel post prima.
"slevyn":
E come effettuo il prodotto di una matrice per se stessa?
Scusa, avevo dato per scontato che conoscessi il prodotto righe per colonne.
Si tratta di questo:
[tex](a\cdot b)_{mn} = \sum_i a_{mi} b_{in}[/tex]
laddove ho indicato il prodotto delle matrici $a$ e $b$ con $a\cdot b$.
E poi non ho capito quante volte si dovrebbe moltiplicare per se stessa la matrice...
A questo punto ho capito di cosa hai bisogno, quindi non ti serve questo "trucco".
Comunque la faccenda e' questa:
data la matrice di adiacenza $A$, il numero di cammini di lunghezza $n$ che partono dal nodo $i$-esimo e arrivano al nodo $j$-esimo e' la componente [tex](A^n)_{ij}[/tex], cioe' la componente relativa ai due nodi, della potenza $n$-esima della matrice di adiacenza.
Comunque ripeto: non hai bisogno di elevare a potenza la matrice di adiacenza per quello che devi fare, devi semplicemente implementare un algoritmo di ricerca sul grafo. Ma prima devi decidere di che tipo di cammino hai bisogno.
Solo per: A* è un algoritmo piuttosto complesso da implementare, utilizza euristiche, e anche il metodo delle potenze è costoso (anche se si va di iterazioni).
Come dici gli basta un algoritmo di visita (DFS o BFS) o un semplice MST (tipo Prim).
un cammino trovato vale l'altro.
"yoshiharu":
Comunque ripeto: non hai bisogno di elevare a potenza la matrice di adiacenza per quello che devi fare, devi semplicemente implementare un algoritmo di ricerca sul grafo. Ma prima devi decidere di che tipo di cammino hai bisogno.
Come dici gli basta un algoritmo di visita (DFS o BFS) o un semplice MST (tipo Prim).
un cammino trovato vale l'altro.
Se un cammino trovato vale l'altro allora direi uno tra DFS o BFS. Difficilmente si riesce infatti a scrivere un codice più semplice. Alternativamente, se si vuole il cammino minimo ma non si hanno abbastanza informazioni per scegliere una euristica, si può usare Dijkstra.
Questa è la mia DFS..come andrebbe modificata affinchè conti gli archi tra DUE nodi ?
template<class T>
void grafo<T>::DFS(grafo<T>::nodo n)
{
if(esistenodo(n)){
setvisited(n,true);
cout<<"["<<legginodo(n)<<"]"<<"-->";
lista<int> L = adiacenti(n) ;
if(!L.listaVuota()) {
cella<int> * p = L.primoLista();
while(!L.fineLista(p)) {
nodo v= L.leggiLista(p);
if(esistearco(n,v)){
cout << "(" << n << "," << v <<")";
if (getvisited(v)==false)
DFS(v);
}
p = L.succLista(p);
}
}
}
}
È sufficiente sommare il costo di ogni arco visitato nel percorso che ti ha portato al nodo.
Ho fatto così..penso stia bene però non mi ritorna la giusta somma degli archi attraversati :
template<class T>
typename grafo<T>::peso grafo<T>::cammino(grafo<T>::nodo n,grafo<T>::nodo m)
{
peso costo=0;
while(getvisited(m)==false){
if(esistenodo(n)){
setvisited(n,true);
cout<<"["<<legginodo(n)<<"]"<<"-->";
lista<int> L = adiacenti(n) ;
if(!L.listaVuota()) {
cella<int> * p = L.primoLista();
while(!L.fineLista(p)) {
nodo v= L.leggiLista(p);
if(esistearco(n,v)){
cout << "(" << n << "," << v <<")";
costo=costo + pesoArco(n,v);
if (getvisited(v)==false)
costo = cammino(v,m);
}
p = L.succLista(p);
}
}
}
}
return costo;
}
Probabilmente perché quello che cerchi non è un cammino qualsiasi, ma uno particolare. Come ti abbiamo già detto, non esiste, in generale, un singolo cammino che collega due nodi, ma tanti.
Mettiamo il caso che io voglia trovare il cammino minimo , riuscirei a trovarlo con questa DFS ?...l'algoritmo di Dijkstra non l'ho studiato purtroppo
"slevyn":
Mettiamo il caso che io voglia trovare il cammino minimo , riuscirei a trovarlo con questa DFS ?...l'algoritmo di Dijkstra non l'ho studiato purtroppo
non disturbiamo Dijkstra
No, con la DFS non trovi il minimo, trovi UN cammino, che può essere il minimo, dipende da come viene visitato il grafo e con che ordine è scelto il nodo successivo di visita.
Se vuoi il minimo puoi usare la BFS.
Un'applicazione simpatica della BFS, che risolve il tuo problema (con cammini minimi), è "il numero di Erdòs" prova a cercarlo con guugle, vedrai è molto semplice
@hamming_burst: Ma il grafo sembrerebbe pesato per cui il percorso con peso minimo non è necessariamente quello con il numero inferiore di archi. Per cui non sono certo che la ricerca in ampiezza sia sufficiente. Vista l'importanza degli algoritmi come Dijkstra o A* io gli farei implementare uno di questi algoritmi. Anche perché, una volta scelte le strutture dati adatte, non è complicato implementare questi algoritmi (sono anzi praticamente tutti identici). Ma forse BFS è sufficiente e io mi sto complicando la vita.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo