[haskell] Visita di un grafo

[guylmaster]

Salve,
ho realizzato la struttura di un grafo in haskell per l'università, il problema è che mi viene richiesto di sviluppare anche un algoritmo di visita (e mi è stato caldamente consigliato di sviluppare il dfs) ma non so davvero da dove cominciare.
Fare la struttura è stato abbastanza facile ma per la visita ad ogni passo dell'algoritmo mi blocco, forse perchè l'algoritmo che ho studiato io era orientato ai linguaggi imperativi (i vari marcalo come visitato, come faccio a marcarlo come visitato se non ho variabili?) e non a quelli funzionali.

Il tipo grafo l'ho dichiarato in questa maniera, vi allego anche la "firma" dei metodi realizzati:


type Nodo = Int
type Arco = (Nodo,Nodo)
type Grafo = ([Nodo],[Arco])

esisteArco :: Arco -> Grafo -> Bool
inserisciArco :: Arco -> Grafo -> Grafo
cancellaArco :: Arco -> Grafo -> Grafo
adiacente :: Nodo -> Grafo -> [Nodo]
esisteNodo :: Nodo -> Grafo -> Bool
grafoVuoto :: Grafo -> Bool


voi come la realizzereste la dfs? :fagiano:

Vi ringrazio in anticipo,
guylmaster.

[marco.r]

La cosa piu' semplice che mi viene in mente e' usare un Diff array dove tieni nota del colore e indicizzato sul numero del nodo... non molto diverso da come faresti in un linguaggio piu' tradizionale

qualcosa tipo

dfs :: Grafo -> Nodo -> [Nodo]
dfs graph initial =
fst $ dfs' graph initial visited
where
minNode = minimum (nodes graph)
maxNode = maximum (nodes graph)
visited :: DiffArray Bool
visited = listArray (minNode,maxNode) (repeat False)

dfs' :: Grafo -> Nodo -> DiffArray Bool -> ([Nodo],DiffArray Bool)

E poi in dfs' non fai che controllare: se visited ! initial e' True, hai gia' visitato e ritorni la lista vuota, altrimenti aggiorni l'array ponendo il valore a true e per ogni vicino ripeti l'operazione... di scomodo c'e' che devi passarti in giro l'array aggiornato man mano che fai gli update, e quindi anche ritornarlo dalle chiamate. Ci sono altre tecniche, ma questa mi sembra la piu' semplice.

[guylmaster]

Non riesco a capire queste tre istruzioni:


fst $ dfs' graph initial visited
minNode = minimum (nodes graph)
visited :: DiffArray Bool
visited = listArray (minNode,maxNode) (repeat False)


ovvero quell'istruzione cos'è? non la capisco per nulla, non so nemmeno cosa si intende per il dollaro;
graph poi da dove esce? e repeat False?

Se ti chiedessi il codice completo per capirci meglio qualcosa ti starei chiedendo troppo? :fagiano: Conta che parliamo di haskell a livello didattico quindi programmando con hugs.

[marco.r]

Non riesco a capire queste tre istruzioni:


fst $ dfs' graph initial visited
minNode = minimum (nodes graph)
visited :: DiffArray Bool
visited = listArray (minNode,maxNode) (repeat False)


ovvero quell'istruzione cos'è? non la capisco per nulla, non so nemmeno cosa si intende per il dollaro;
graph poi da dove esce? e repeat False?
[/code]
fst e' una delle istruzioni del preluidio, ritorna il primo argomento di una coppia

fst (x,y) = x

il $ server per scrivere meno parentesi :D.
f $ g x e' equivalente a f (g x)
graph e' uno degli argomenti della funzione, c' e' scritto nella riga sopra
minimum e' la funzione che ritorna il valore minimo di una lista
l'ultima riga invece costruisce un array partendo dai limiti inferiore e superiore dello stesso e la lista dei valori. Qualcuno di questo punti non li avete ancora studiati ?

[quote]
Se ti chiedessi il codice completo per capirci meglio qualcosa ti starei chiedendo troppo? :fagiano: Conta che parliamo di haskell a livello didattico quindi programmando con hugs.
Per ora niente da fare che non faccio in tempo. intanto tu pero' prova a vedere sopra e dimmi cos'altro non ti torna

[banryu79]

Ciao guylmaster, provo anche io ad aiutarti, ma fornendoti indicazioni su dove reperire le info che ti mancano.


fst $ dfs' graph initial visited
minNode = minimum (nodes graph)
visited :: DiffArray Bool
visited = listArray (minNode,maxNode) (repeat False)

ovvero quell'istruzione cos'è? non la capisco per nulla, non so nemmeno cosa si intende per il dollaro;
graph poi da dove esce? e repeat False?

Se fai riferimento al tutorial che ti avevo indicato in questo post (http://www.hwupgrade.it/forum/showpost.php?p=36158168&postcount=14), puoi tovare una spiegazione sulla "function application" ($), qui (http://learnyouahaskell.com/higher-order-functions#function-application).
Guardati anche il paragrafo immediatamente seguente, sulla "function composition" (.)


graph poi da dove esce? e repeat False?

Quello è pattern matching, dubito che tu non sappia cos'è, ma in caso lo trovi spiegato qui (http://learnyouahaskell.com/syntax-in-functions).

Invece "minimum" e "listArray" sono delle funzioni che fanno parte delle librerie di Haskell (io uso GHC, tu mi pare Hugs, immagino che le librerie base siano le stesse).

Quando incontri una nuova funzione di libreria che non avevi mai visto prima, oppure se vuoi vedere se nelle librerire esiste una funzione con un dato nome, usa Hoggle: (http://haskell.org/hoogle/) è uno strumento utilissimo (io l'ho aggiunto come uno dei motori di ricerca nella barra apposita per firefox) e ti fa risparmiare un sacco di tempo.

Inoltre, ti permette se vuoi di saltare ai sorgenti dove la definizione da te cercata è definita, così puoi sbirciare come vengono implementate (anche se i sorgenti, se non ho capito male, sono relativi a GHC).

[guylmaster]

Con le mie mani mi sono ritrovato a scrivere questo che ovviamente è incompleto ed anzi mi sono parecchio bloccato:


copia2 :: Grafo -> [(Nodo,Int)]
copia2 ([],[]) = ([])
copia2 ([],ys) = ([])
copia2 (x:xs,ys) = [(x,0)] ++ copia2 (xs,ys)

copia :: Grafo -> ([(Nodo,Int)],[Arco])
copia (xs,ys) = (copia2 (xs,ys), ys)

dfs:: Nodo -> Grafo -> [Nodo]
dfs u g = do xs <- copia g
return (dfsv u xs)

nododx :: [(Int,Int)] -> [Nodo]
nododx [] = []
nododx ((a,b):xs) = [b] ++ nododx xs

dfsv:: Nodo -> ([(Nodo,Int)],[Arco]) -> [Nodo] -> [Nodo]
dfsv u (xs,ys) fs = do ks <- [u]
os <- nododx (takeWhile (\(o,p) -> o == u) ys)
--INCOMPLETO
return ks


Ovvero la funzione dfs tramite copia e quindi di rimbalzo copia2 mi crea una "struttura di lavoro" del tipo ([(Nodo,Int],[Arco]), ovvero aggiungo un flag all'inizio settato a zero da avvalorare con 1 man mano che visito gli archi.
Questa struttura si fatta la passo a dfsv e quello che vorrei fargli fare (ma che non riesco a far fare) è il cuore dell'operazione ovvero visita il nodo u e mettimelo in ks se il flag è a zero, dopo metti in os tutti i suoi adiacenti, reitera l'operazione sugli adiacenti. Ecco questa parte qui non riesco a tradurla in haskell. Ci stiamo provando da più di un giorno in due ma nulla.

Tra l'altro a lezione più di un takeWhile, un pò di list comprension, le istruzioni con la do, e degli if non abbiamo fatto (ed essendo la parte di laboratorio finita non le faremo). Quindi volevo riuscire in qualche modo a farle con gli strumenti che ci sono stati dati, senza dover ricorrere a nuove funzioni che nemmeno conosco.

[marco.r]

Non avete fatto gli array, ma avete coperto l'uso del do con le liste ? :mbe:

[marco.r]

L'approccio che avevo proposto si puo' anche adattare ad un uso senza array (ma meno efficiente), provo a delineartelo.
L'idea e' la seguente:
parto con un nodo da cui voglio fare la visita, il grafo

dfs :: Grafo -> Nodo -> [Nodo]
dfs graph initial = dfs' graph initial []

dfs' prima cosa fa ?
dfs' avra' tipo

dfs' :: Grafo -> Nodo -> [Nodo] -> [Nodo]
dfs' grafo nodoIniziale visitati = ... ?

Ovvero prende come argomento il grafo da analizzare, il prossimo nodo da valutare, e i nodi gia' visitati (cioe' il risultato che sta costruendo).
Cosa deve fare ? Intanto guarda se nodoIniziale e' tra quelli visitati. Se e' cosi' allora non occorre procedere altro, e si "ritorna indietro" ritornando proprio "visitati".
Se invece nodoIniziale e' "nuovo", deve costruirsi una lista di tutti i nodi adiacenti (da grafo), e chiamare su ognuno di questi ricorsivamente dfs'.
Occhio pero' che al primo nodo adiacente devi passare "visitati" piu' il nodo corrente, al secondo il risultato della chiamata di dfs' al nodo precedente e cosi' via (e' piu' facile da scrivere con codice che a parole... ^_^).
Il risultato finale sara' il risultato dell'ultima chiamata a dfs'