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





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


type Sommet = Int
type Arete = (Int,Int)

depart :: Sommet
depart = 1

nbAretes :: Int
nbAretes = length listeAretes

listeAretes :: [Arete]
listeAretes = [(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)]


-- permet de retourner les arêtes partant du sommet x
aretesConnexes :: Sommet -> [Arete] -> [Arete]
aretesConnexes x l = aretesConnexesAux x l

aretesConnexesAux :: Sommet -> [Arete] -> [Arete]
aretesConnexesAux x [] = []
aretesConnexesAux x (arete@(c,d):xs)
	| x == c = arete : ( aretesConnexesAux x xs) 
	| x == d = arete : ( aretesConnexesAux x xs)
	| otherwise = aretesConnexesAux x xs

-- permet de retourner les sommets connexes à s
sommetsConnexes :: Sommet -> [Arete] -> [Sommet]
sommetsConnexes s [] = []
sommetsConnexes s (arete@(x,y):xs)
	| s == x  = y : (sommetsConnexes s xs)
	| otherwise = x : (sommetsConnexes s xs)


--permet de prendre le sommet avant s dans une pile
avantSommet :: Sommet -> [Sommet]-> Sommet
avantSommet _ (x:[]) = 0
avantSommet s (x:y:xs)
	|y == s = x
	|otherwise = avantSommet s (y:xs)

-- permet de retourner le deuxième sommet d'une arête connaissant un des deux.
autreSommetArete :: Sommet -> Arete -> Sommet
autreSommetArete s (x,y)
	| s == x  = y
	| otherwise = x

--permet de transformer une liste de sommets en une liste d'arêtes.
sommetEnArete :: [Sommet] -> [Arete]
sommetEnArete [] = []
sommetEnArete (x:[]) = []
sommetEnArete (x:y:xs) = (x,y):(sommetEnArete (y:xs))



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



euler :: [[Sommet]]
euler = (boucle [depart] 1 (aretesConnexes depart listeAretes))

nbSolutions = length euler



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

condition :: Int -> Arete -> [Sommet] -> Bool
condition i arete@(x1,y1) cycle@(x:xs) 
	|elem (x1,y1) (sommetEnArete cycle) || elem (y1,x1) (sommetEnArete cycle) = False
	|(i<nbAretes) && (elem autreSommet cycle) = x > avantSommet autreSommet cycle
	|(i<nbAretes) = True
	|otherwise = (head(tail(reverse cycle))) < x
		where autreSommet = (autreSommetArete x arete)



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



boucle :: [Sommet] -> Int -> [Arete] -> [[Sommet]]
boucle _ _ [] = []
boucle cycle@(y:ys) i delta@(x:xs) 				      
	|(condition i x cycle) &&  (i==nbAretes) = [(reverse cycle)]
	|(condition i x cycle) = (boucle (autreSommet:cycle) (i+1) (aretesConnexes autreSommet listeAretes)) ++ (boucle cycle i xs)
	|otherwise = boucle cycle i xs
		where  
		    autreSommet = (autreSommetArete y x)