[Python] Algoritmo ricerca cicli in un grafo, come stampare le informazioni?

[e-commerce84]

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

[cdimauro]

Non hai specificato quale versione di Python, per cui suppongo sia la 3.x:

1) print (z, u)
2) print ('Ecco qui E[z]:', E[z])
3) print (S, E, X, T)

[e-commerce84]

Originariamente inviato da cdimauro

Non hai specificato quale versione di Python, per cui suppongo sia la 3.x:

1) print (z, u)
2) print ('Ecco qui E[z]:', E[z])
3) print (S, E, X, T)

Grazie mille,
la versione non ci è stata specificata neanche a noi perchè come ti dicevo il proff lo usa solo al posto dello pseudocodice...

Scusa la domanda...rimango un po' sbalordito...ma mi stai dicendo che Python è così ad alto livello che posso passare come argomento della funzione print una coppia di variabili (z, u) così come un intero array ?!?!

Se è davvero così potrebbe essere veramente comodissimo per determinati scopi...

Grazie
Andrea

[cdimauro]

Sì, puoi passargli quello che vuoi e... verrà stampato.

E' comodissimo, tanto che è diventato uno dei migliori strumenti di prototipazione / modellazione.

Figurati che ci sono alcuni matematici che lo preferiscono pure a Matlab...

E la sintassi, beh, se viene definito pseudocodice eseguibile qualche motivo ci sarà.

[e-commerce84]

Originariamente inviato da cdimauro

Sì, puoi passargli quello che vuoi e... verrà stampato.

E' comodissimo, tanto che è diventato uno dei migliori strumenti di prototipazione / modellazione.

Figurati che ci sono alcuni matematici che lo preferiscono pure a Matlab...

E la sintassi, beh, se viene definito pseudocodice eseguibile qualche motivo ci sarà.

Mi ha piacevolmente stupito infatti...vabbè...con la scusa di algoritmi magari inizierò a dargli un'occhiata anche se al momento stò lavorando su tutt'altro (applicazioni web in Java)

[cdimauro]

Eventualmente avessi tempo, per il web c'è django che è molto quotato.

[e-commerce84]

Originariamente inviato da cdimauro

Eventualmente avessi tempo, per il web c'è django che è molto quotato.

Il problema è proprio il tempo...ed il fatto che la unit dove lavoro si chiama Java Factory...quindi almeno per ora vedrò sempre e solo Java al lavoro...

[banryu79]

Originariamente inviato da e-commerce84

Il problema è proprio il tempo...ed il fatto che la unit dove lavoro si chiama Java Factory...quindi almeno per ora vedrò sempre e solo Java al lavoro...

Scala potrebbe fare al caso vostro allora...

@Edit: scusate l'OT, era solo una considerazione per e-commerce84.

[cdimauro]

Naaah. Non distogliamolo dalla retta via.

Python + Java = Jython.

[e-commerce84]

ehehe ragazzi...io sono solo un povero stagista non pagato...faccio quello che mi dicono di fare da bravo code monkey...attualmente mi stò impiccando con i web services con Axis 2 :-P Fino a ieri mi stavo impiccando con una portlet fatta con IceFaces per il portale LifeRay