--                        ****************************************************
--                        *               Cycles hamiltoniens                *
--                        * ________________________________________________ * 
--                        *     Julien Van Den Bossche / Benoît Moulin       *
--                        * cmoi@julienvdb.com / bmoulin@etu.info.unicaen.fr * 
--                        ****************************************************   



--                           ****************************************
--                           *     Représentations des données      *
--                           *          Fonctions utiles            * 
--                           ****************************************


--Un sommet sera définit par un entier
type Sommet = Int

--Le nombre de sommets de notre graphe G(S,A)
nbSommets :: Int
nbSommets = 20

--Le sommet que l'on considére comme point de départ de notre parcours
depart :: Sommet
depart = 1

--Domaine : on représente une liste contenant la liste des successeurs d'un sommet.
--La liste de successeurs du sommet n se trouve à la n-ième position dans la liste  
domaine :: [[Sommet]]
domaine = [[2,8,20],[1,3,15],[2,4,7],[3,5,14],[4,6,12],[5,7,10],[3,6,8],[1,7,9],[8,10,19],[6,9,11],[10,12,18],[5,11,13],[12,14,17],[4,13,15],[2,14,16],[15,17,20],[13,16,18],[11,17,19],[9,18,20],[1,16,19]]


--permet de renvoyer la liste des sommets connexes à un sommet
--connexe :: Sommet -> Int -> [Sommet]
connexe s = connexeAux s 1 domaine

--connexeAux :: Sommet -> Int -> [Sommet] -> [Sommet]
connexeAux s cpt (x:xs)
		|s == cpt = x
  		|otherwise = connexeAux s (cpt+1) xs





--                           ***************************
--                           *     Initialisation      * 
--                           ***************************


hamilton :: [[Sommet]]
hamilton = boucle [depart] 1 (connexe depart)

nbSolutions = length hamilton


--                           ***************************
--                           *       Condition Ci      * 
--                           ***************************

condition :: Int -> Sommet -> [Sommet] -> Bool
condition i sommet pile 
	|i+1 == nbSommets = not (elem sommet pile) && (elem sommet (connexe depart)) && (deuxiemeSommet < sommet)
	|otherwise = not(elem sommet pile)
		where connexeAuDepart = (connexe depart)
		      deuxiemeSommet = (head (tail (reverse pile)))



--                           ***************************
--                           *         Boucle          * 
--                           ***************************

boucle :: [Sommet] -> Int -> [Sommet] -> [[Sommet]]
boucle _ 0 _ = []
boucle cycle i [] = [] 
boucle cycle i (x:xs) 
	|condition i x cycle && i == nbSommets-1 = [reverse(x:cycle)]
	|condition i x cycle = (boucle (x:cycle) (i+1) (connexe x)) ++ (boucle cycle i xs)
	|otherwise = (boucle cycle i xs)