member :: (Eq a) => a -> [a] -> Bool


member el [] = False
member el (x:xs) = (x == el) || (member el xs)


-- Costruiamo i nodi a partire da numeri interi

data Node = Node Int
     deriving Show

instance Eq Node where
   (Node n) == (Node m) = (n == m)

-- Costruiamo un grafo a partire dalla lista delle coppie dei nodi adiacenti.
-- Se N1 ed N2 sono adiacenti supponiamo basti avere (N1,N2) nella lista
-- se c'e' anche (N2,N1) non cambia nulla

data Graph = Graph [(Node,Node)]
       deriving Show

-- Un grafo da usare come test

myGraph = Graph [(Node 1,Node 2),(Node 2,Node 3),(Node 3,Node 4),(Node 1,Node 5),(Node 5, Node 2),(Node 1,Node 6),(Node 6, Node 7)]


-- Costruiamo un cammino a partire dalla lista dei nodi che lo definiscono

data Path = Path [Node]
      deriving Show


data Set a = Set [a]
      deriving Show

-- predicato su insiemi

isEmpty :: (Set a) -> Bool

isEmpty (Set []) = True
isEmpty s = False


-- funzione che restituisce la lista a partire dalla quale e' stato
-- costruito un insieme

makelist :: (Set a) -> [a]

makelist (Set l) = l


-- unione di insiemi

union :: (Set a) -> (Set a) -> (Set a)

union (Set l1) (Set l2) = Set (l1++l2) 


-- unione generalizzata (su lista di insiemi)

unionGen :: [(Set a)] -> (Set a)

unionGen [] = Set []
unionGen (st:sts) = union st (unionGen sts)


-- funzione che prende un nodo N, un path N1,N2,...Nm e restituisce il
-- path N,N1,N2,...Nm
-- Se il path e' vuoto allora restituisce il path vuoto (non N)

putOnHeadPath :: Node -> Path -> Path

putOnHeadPath el (Path []) = Path []
putOnHeadPath el (Path ns) = Path (el:ns)


-- funzione che restituisce, dato un grafo ed un nodo, l'insieme
-- dei nodi adiacenti al nodo in input

adiacentSet :: Graph -> Node -> (Set Node)

adiacentSet (Graph []) n = Set []
adiacentSet (Graph ((n1,n2):l)) n  | (n == n1)    =  (union (Set [n2]) (adiacentSet (Graph l) n) )
                                   | (n == n2)    =  (union (Set [n1]) (adiacentSet (Graph l) n) )
                                   | otherwise    =  (adiacentSet (Graph l) n)


-- funzione (a cui in realta' andrebbe dato un nome piu' significativo)
-- che restituisce un grafo simile a quello di input, ma in cui non e'
-- presente il nodo dato come secondo input

remove :: Graph -> Node -> Graph

remove (Graph l) n = Graph [ (n1,n2) | (n1,n2) <- l,  (n /= n1),  (n /= n2) ]


-- funzione che restituisce l'insieme dei cammini

findPaths :: Graph -> Node -> Node -> (Set Path)


findPaths g n m  |  (n == m)          = Set [Path [n]]
                 |  (isEmpty (adiacentSet g n)) = Set []
                 |  otherwise          = Set (map (putOnHeadPath n)
                                                  (makelist (unionGen [(findPaths (remove g n) nd m) | nd <- (makelist (adiacentSet g n)) ] ) )
                                             )