[C-C++] Grafi...riconoscere nodi serie/parallelo..AIUTOOOO!!

[ANDREA_NET-_DSL]

Ciao a tutti!

Mi potete aiutare a svolgere questo programma in C(va benissimo pure in C++ )...

Dovrei fare in modo che chiesti in input: per prima cosa quanti archi dovranno formare il grafo e poi successivamente ogni arco con i suoi estremi(A-B B-C C-D ecc.. fino al numero scelto all'inizio).

Se ad es pero' scrivo B-C due volte ci saranno due archi in parallelo e cosi' via...

Cioè il programma deve riconoscere se gli archi sono in parallelo o in serie e scrivelo in output....

Grazie mille e vi prego aiutatemi è importante
:confused: :cry:


:)

[/\/\@®¢Ø]

visto che non hai specificato come implementare il grafo ti consiglio di utilizzare una matrice di adiacenza, ovvero una matrice (quadrata) M in cui l'elemento M(i,j) ti dice se c'e' (valore !=0) un arco tra l'i-esimo nodo e il j-esimo oppure no (valore ==0).
Se per la matrice usi un array di array, M(i,j) lo scrivi M[i][j] e quindi per "inserire" un arco basta scrivere M[i][j] = 1;
A questo punto il modo per controllare "archi doppi" dovresti averlo gia' capito ;).

[ANDREA_NET-_DSL]

Originariamente inviato da /\/\@®¢Ø
visto che non hai specificato come implementare il grafo ti consiglio di utilizzare una matrice di adiacenza, ovvero una matrice (quadrata) M in cui l'elemento M(i,j) ti dice se c'e' (valore !=0) un arco tra l'i-esimo nodo e il j-esimo oppure no (valore ==0).
Se per la matrice usi un array di array, M(i,j) lo scrivi M[i][j] e quindi per "inserire" un arco basta scrivere M[i][j] = 1;
A questo punto il modo per controllare "archi doppi" dovresti averlo gia' capito ;).
Grazie mille ma saresti cosi' gentile di scrivermi del codice (c o c++ è lo stesso) che faccia quanto mi hai detto??:confused: ti prego sarebbe molto importante dopo me lo studio e cerco di svilupparlo con altre cose in futuro...

ti prego

grazie mille:p :)

[/\/\@®¢Ø]

Originariamente inviato da ANDREA_NET-_DSL
Grazie mille ma saresti cosi' gentile di scrivermi del codice (c o c++ è lo stesso) che faccia quanto mi hai detto??:confused: ti prego sarebbe molto importante dopo me lo studio e cerco di svilupparlo con altre cose in futuro...

ti prego

grazie mille:p :)
Visto che suona un po' da esercizio per casa, e dato sono molto pigro, ti mostro una versione meta' C++ e meta' pseudo-codice :p :D.


const int MAX_SIZE=50;
int grafo[MAX_SIZE][MAX_SIZE];
for ( "ogni elemento di grafo" )
grafo[i][j] =0;

int nodi,archi;

cin >> nodi;
cin >> archi;
while( archi-- )
{
cin >> da >> a;
if ( grafo[da][a] == 1 )
{
cout << "arco parallelo da " da << " a" << a << endl;
}
grafo[da][a] = 1;
}

In questo modo finche' costruisci la matrice controlli la presenza di archi in parallelo. Per gli archi in serie dipende da come li vuoi trattare (a due a due o in altro modo ?)

[ANDREA_NET-_DSL]

ho cercato di completare il tuo prog cosi'..
#include <iostream.h>
#include<stdlib.h>

main(){
int da,a,i,j;
const int MAX_SIZE=50;

int grafo[MAX_SIZE][MAX_SIZE];

for (i=0; i<10; i++){

for (j=0; j<10; j++)
{
grafo[i][j] =0;
}
}

int nodi,archi;

cin >> nodi;
cin >> archi;
while( archi-- )
{
cin >> da >> a;
if ( grafo[da][a] == 1 )
{
cout << "arco parallelo da " << da << " a " << a << endl;

}
grafo[da][a] = 1;
}
system("pause");
}



viene compilato ma mi sembra nn fungere.... cioè non mi stampa mai il messaggio" arco in parallelo ecc " xchè??potresti correggerlo? :confused:

grazie mille:)

[/\/\@®¢Ø]

:confused:
questo e' l'input e l'output che ottengo io col tuo programma:
( occhio che i primi due 10 sono il numero di nodi e di archi )

10 10
1 2
2 3
3 2
1 2
arco parallelo da 1 a 2
1 2
arco parallelo da 1 a 2
1 3
1 3
arco parallelo da 1 a 3
2 1
3 2
arco parallelo da 3 a 2
5 1
1 5

[/\/\@®¢Ø]

ah, forse ho capito, guarda che le etichette per i nodi sono interi minori di N ( con N il numero di nodi), non puoi usare numeri piu' grandi o lettere, per fare quello devi complicare un po' di piu' il programma.

[ANDREA_NET-_DSL]

l'output è questo
10 10
1 2
2 3
3 2
1 2
arco parallelo da 1 a 2
1 2
arco parallelo da 1 a 2
1 3
1 3
arco parallelo da 1 a 3
2 1
3 2
arco parallelo da 3 a 2
5 1
Premere un tasto per continuare . . .

a me da cosi' l'output con gli stessi tuoi input ..senza l'ultimo 1 5..

Funge quindi cosi'?è corretto l'output?

Ma xchè devo scrivere quei numeri?che rappresentano i numeri dei nodi??non posso fare che inserisco A B B C C D ecc??come? :confused:

Cmq potresti aggiungerci anche il controllo x quelli che sono in serie??

Grazie mille:)

[/\/\@®¢Ø]

Originariamente inviato da ANDREA_NET-_DSL
l'output è questo
10 10
1 2
2 3
3 2
1 2
arco parallelo da 1 a 2
1 2
arco parallelo da 1 a 2
1 3
1 3
arco parallelo da 1 a 3
2 1
3 2
arco parallelo da 3 a 2
5 1
Premere un tasto per continuare . . .

a me da cosi' l'output con gli stessi tuoi input ..senza l'ultimo 1 5..

Funge quindi cosi'?è corretto l'output?

Ma xchè devo scrivere quei numeri?che rappresentano i numeri dei nodi??non posso fare che inserisco A B B C C D ecc??come? :confused:

Semplicemente devi scrivere 1,2,3, etc. al posto di A,B,C etc. In questo modo puoi usare direttamente il nome (ovvero il numero) del nodo come indice della matrice. Se tu potessi scrivere le lettere al posto dei numeri il risultato sarebbe il seguente:

10 10
A B
B C
C B
A B
arco parallelo da A a B
A B
arco parallelo da A a B
A C
A C
arco parallelo da A a C
B A
C B
arco parallelo da C a B
E A

Ti trovi ora come funziona ?
A dire il vero io sono partito dal presupposto che il grafo sia diretto... E' cosi' o e' non diretto ?

Se vuoi inserire le lettere al posto dei numeri puoi fare nel seguente modo:

...
char tabella_simboli[256];
char c = 'A'; int i=0;
while ( c <= 'Z' )
{
tabella_simboli[c] = i;
c++; i++;
}

e al posto di usare direttamente gli indici "passi" per la tabella dei simboli (e cambi 'da' e 'a' da int a char):

cin >> da >> a;
const char* t = tabella_simboli;
if ( grafo[ t[da] ][ t[a] ] == 1 )
{
cout << "arco parallelo da " da << " a" << a << endl;
}
grafo[ t[da] ][ t[a] ] = 1;

Per gli archi in serie dipende da come li devi individuare...

[ANDREA_NET-_DSL]

chiarissimo :)

Cmq per la serie nn so che intendi con come la devo trattare...non abbiamo fatto un modo particolare ma solo sapere ad es che se scrivo A_B B_C C_D sono in serie...

mi puoi aiutare??:)

ps mi sto studiano il codice intanto:)
ps2: VERSIONE MESSA APPOSTO CON LETTERE ECC #include <iostream.h>
#include <stdlib.h>
const int MAX_SIZE=50;

int i,j;
char da,a;

int grafo[MAX_SIZE][MAX_SIZE];

main(){

char tabella_simboli[256];
char c = 'A'; int i=0;
while ( c <= 'Z' )
{
tabella_simboli[c] = i;
c++; i++;
}



for (i=0; i<10; i++){

for (j=0; j<10; j++)
{
grafo[i][j] =0;
}
}

int nodi,archi;
cout << "Inserisci il numero dei nodi (n* elementi coppie)" << endl;
cin >> nodi;

cout << "Inserisci il numero degli archi(n* coppie nodi) "<< endl;
cin >> archi;


while( archi-- ){

cout << "Inserisci in successione,separati da spazio, il " << archi << " e il SECONDO" << endl;
cin >> da >> a;

const char* t = tabella_simboli;

if ( grafo[ t[da] ][ t[a] ] == 1 )
{
cout << "arco parallelo da " << da << " a " << a << endl;

}
grafo[ t[da] ][ t[a] ] = 1;


}
system("pause");
}

manca solo il fatto che riconosce la serie:)

[/\/\@®¢Ø]

Quello che intendevo dire e' che lo puoi fare in molti modi... ad esempio a te interessa che quando inserisci l'arco A-B ti dica "A-B e' in serie con B-C e B-D" o devi farlo alla fine ? E in questo caso basta farlo due a due o tutte le possibili combinazioni ? Dire ad esempio
"gli archi in serie sono:
A-B B-C
A-B B-D
B-D D-A
"
o devi trovarti anche la tripletta "A-B B-D D-A" ?
In ogni caso questa la lascio a te :p dopo un ultimo suggerimento:
se scegli (ad esempio) il nodo 'A', tutti gli archi che escono da 'A' sono sulla riga grafo[ tabella_simboli['A'] ][i], con i che varia tra 0 e il numero massimo. Quindi se ti basta trovare tutte le coppie in serie puoi adottare un approccio del genere:
cicli sulle tre variabili 'da' 'a' e 'per' e controlli se c'e' un arco che va da 'da' a 'per' e uno da 'per' ad 'a' :D
qualcosa come

int da,a,per;
for( "cicla sulle tre variabili, per comodita' lavoriamo direttamente sui numeri e non sui nomi dei nodi" )
if ( grafo[da][per] == 1 && grafo[per][a] == 1 )
"i due archi sono in serie"


Ciao e buon lavoro :)

[ANDREA_NET-_DSL]

il ciclo che mi hai proposto è il seguente int da,a,per;
for( "cicla sulle tre variabili, per comodita' lavoriamo direttamente sui numeri e non sui nomi dei nodi" )
if ( grafo[da][per] == 1 && grafo[per][a] == 1 )
"i due archi sono in serie"


si potrebbe tradurre cosi'??
int da,a,per;

for( da=0; da<n; da++ ){
for( a=0; a<n; a++ ){
for( per=0; per<n; per++ ){

if ( grafo[da][per] == 1 && grafo[per][a] == 1 )
cout << "i due archi sono in serie" << endl;
}
}
}

con tre for in questo modo è ok?:confused:
va nel ciclo while do ?? 'per' è una var nuova no? come opera?
:)

GRAZIE!
ps non mi servono le triplette ma solo le coppie per la serie dico...:)

[ANDREA_NET-_DSL]

up

aiutatemi...:confused:

grazie:)