e-commerce84
03-04-2011, 10:57
Ciao,
stò seguendo un corso universitario di algoritmi, il professore quest'anno ha deciso di sostituire il buon vecchio caro pseudocodice con Python...essendo un linguaggio ad altissimo livello ciò non comporta grandi problemi di comprensione per quanto concerne l'algoritmo ma ovviamente le mie conoscienze di tale linguaggio sono molto basse (per ora lo ho usato solo come userei lo pseudocodice)
Ora mi trovo ad avere un dubbietto su come funziona un algoritmo per la RICERCA DI CICLI IN UN GRAFO DIRETTO
In pratica banalmente vorrei aggiungere degli output in alcune parti del mio codice per monitorare cosa stà succedendo ad ogni iterazione...solo che avendo sempre usato Python solo come pseudocodice non sò come fare...
Il mio algoritmo è il seguente:
# Algoritmo che se trova un ciclo in un grafo orientato G lo restituisce
def findcycle (G,s):
n = len(G) # n è il numero di nodi nel grafo G, s è il nodo di partenza da cui inizia l'espolorazione di G
S = [] # S è uno STACK
S.append((None,s)) # Inizialmente mette nello STACK l'arco (None, s): Il padre di s è un nodo fittizio
# E[u] può valere:
# A se ho iniziato a visitare il sottoalbero radicato in u ma se ancora la visita di tale sottoalbero non è stata ultimata.
# C se la visita del sottoalbero radicato in u è terminata.
# None se il nodo u non è ancora stato visitato dall'algoritmo.
E = [None]∗n
X = [False]∗n # X rappresenta l'insieme dei nodi visitati: X[u]= True, il nodo u è stato visitato
T = [None]∗n # T rappresenta l'albero di visita: T[u] = z significa che il nodo z è PADRE del nodo u nell'albero T
while len(S)>0: # Finchè lo STACK S contiene elementi
(z,u) = S.pop() # Estrai un elemento (un arco) dalla pila e metti il NODO DI PARTENZA in z ed il NODO DI DESTINAZIONE in u
if u == None: # Se il nodo di destinazione è None significa che il sottoalbero radicato nel nodo di partenza z è stato completato
E[z] = C # allora marco come CHIUSO il sottoalbero radicato nel nodo padre z
else: # Altrimenti se il nodo di destinazione non è None, il sottoalbero radicato in z potrebbe non essere completato
if X[u] == False: # Se il nodo di destinazione u non è mai stato visitato dall'algoritmo, lo visito:
X[u] = True # Marco come True la posizione X[u] che rappresenta i nodi visitati dall'algoritmo
E[u] = A # Marco come A la posizione E[u] perchè ho iniziato a visitare il sottoalbero radicato in u
T[u] = z # Il nodo z è PADRE del nodo u nell'ALBERO DI VISITA T
S.append((u, None)) # Metto l'arco (u, None) nello STACK S
for v in G[u]: # e poi metto nello STACK S tutti i nodi v vicini al nodo u
S.append((u,v))
# Se invece X[u] è diverso da False significherebbe che l'algoritmo è tornato su un nodo già visitato, se il sottoalbero radicato in u
# non è stato chiuso, allora significa che l'arco (z,u) è un ARCO ALL'INDIETRO e che quindi ho trovato un CICLO
elif E[u] == A:
L = path (T,u,z) # Metti in L il PERCORSO tra u e z che rappresenta il CICLO
return L # Ritorna L al chiamante
return None # Se l'algoritmo termina senza aver trovato cicli termina restituendo None
Il grafo G è rappresentato tramite lista di adiecenza:
G = [
[u1, u4 , u6 ],
[u0, u6],
[u1, u6],
[u5],
[u0],
[u3]
]
Semplicemente stà dicendo che il nodo u0 è collegato ai nodi u1, u4, u6. Il nodo u1 è collegato ai nodi u0 ed u6. E così via...
Ora il mio problema è che vorrei poter eseguire la mia funzione findcycle in modo che essa mi stampi sullo schermo degli output...
Più precisamente vorrei che mi stampasse le seguenti cose:
1) All'inizio del ciclo while, dopo l'istruzione (z,u) = S.pop() vorrei che mi stampasse i valori di z e di u
2) All'interno del primo if, dopo l'istruzione E[z] = C, vorrrei che mi stampasse un messaggio testuale seguito dal valore di E[z]
3) Dentro l'else e dentro il primo if, alla fine (dopo l'istruzione: S.append((u,v)) vorrei che mi stampasse le seguenti cose: il contenuto dello stack S, il contenuto di E, X e T
Qualcuno sà aiutarmi?
Grazie mille
stò seguendo un corso universitario di algoritmi, il professore quest'anno ha deciso di sostituire il buon vecchio caro pseudocodice con Python...essendo un linguaggio ad altissimo livello ciò non comporta grandi problemi di comprensione per quanto concerne l'algoritmo ma ovviamente le mie conoscienze di tale linguaggio sono molto basse (per ora lo ho usato solo come userei lo pseudocodice)
Ora mi trovo ad avere un dubbietto su come funziona un algoritmo per la RICERCA DI CICLI IN UN GRAFO DIRETTO
In pratica banalmente vorrei aggiungere degli output in alcune parti del mio codice per monitorare cosa stà succedendo ad ogni iterazione...solo che avendo sempre usato Python solo come pseudocodice non sò come fare...
Il mio algoritmo è il seguente:
# Algoritmo che se trova un ciclo in un grafo orientato G lo restituisce
def findcycle (G,s):
n = len(G) # n è il numero di nodi nel grafo G, s è il nodo di partenza da cui inizia l'espolorazione di G
S = [] # S è uno STACK
S.append((None,s)) # Inizialmente mette nello STACK l'arco (None, s): Il padre di s è un nodo fittizio
# E[u] può valere:
# A se ho iniziato a visitare il sottoalbero radicato in u ma se ancora la visita di tale sottoalbero non è stata ultimata.
# C se la visita del sottoalbero radicato in u è terminata.
# None se il nodo u non è ancora stato visitato dall'algoritmo.
E = [None]∗n
X = [False]∗n # X rappresenta l'insieme dei nodi visitati: X[u]= True, il nodo u è stato visitato
T = [None]∗n # T rappresenta l'albero di visita: T[u] = z significa che il nodo z è PADRE del nodo u nell'albero T
while len(S)>0: # Finchè lo STACK S contiene elementi
(z,u) = S.pop() # Estrai un elemento (un arco) dalla pila e metti il NODO DI PARTENZA in z ed il NODO DI DESTINAZIONE in u
if u == None: # Se il nodo di destinazione è None significa che il sottoalbero radicato nel nodo di partenza z è stato completato
E[z] = C # allora marco come CHIUSO il sottoalbero radicato nel nodo padre z
else: # Altrimenti se il nodo di destinazione non è None, il sottoalbero radicato in z potrebbe non essere completato
if X[u] == False: # Se il nodo di destinazione u non è mai stato visitato dall'algoritmo, lo visito:
X[u] = True # Marco come True la posizione X[u] che rappresenta i nodi visitati dall'algoritmo
E[u] = A # Marco come A la posizione E[u] perchè ho iniziato a visitare il sottoalbero radicato in u
T[u] = z # Il nodo z è PADRE del nodo u nell'ALBERO DI VISITA T
S.append((u, None)) # Metto l'arco (u, None) nello STACK S
for v in G[u]: # e poi metto nello STACK S tutti i nodi v vicini al nodo u
S.append((u,v))
# Se invece X[u] è diverso da False significherebbe che l'algoritmo è tornato su un nodo già visitato, se il sottoalbero radicato in u
# non è stato chiuso, allora significa che l'arco (z,u) è un ARCO ALL'INDIETRO e che quindi ho trovato un CICLO
elif E[u] == A:
L = path (T,u,z) # Metti in L il PERCORSO tra u e z che rappresenta il CICLO
return L # Ritorna L al chiamante
return None # Se l'algoritmo termina senza aver trovato cicli termina restituendo None
Il grafo G è rappresentato tramite lista di adiecenza:
G = [
[u1, u4 , u6 ],
[u0, u6],
[u1, u6],
[u5],
[u0],
[u3]
]
Semplicemente stà dicendo che il nodo u0 è collegato ai nodi u1, u4, u6. Il nodo u1 è collegato ai nodi u0 ed u6. E così via...
Ora il mio problema è che vorrei poter eseguire la mia funzione findcycle in modo che essa mi stampi sullo schermo degli output...
Più precisamente vorrei che mi stampasse le seguenti cose:
1) All'inizio del ciclo while, dopo l'istruzione (z,u) = S.pop() vorrei che mi stampasse i valori di z e di u
2) All'interno del primo if, dopo l'istruzione E[z] = C, vorrrei che mi stampasse un messaggio testuale seguito dal valore di E[z]
3) Dentro l'else e dentro il primo if, alla fine (dopo l'istruzione: S.append((u,v)) vorrei che mi stampasse le seguenti cose: il contenuto dello stack S, il contenuto di E, X e T
Qualcuno sà aiutarmi?
Grazie mille