--                        ****************************************************
--                        *               Arbres de recouvrements            *
--                        * ________________________________________________ * 
--                        *     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)

nbSommets :: Int
nbSommets = 5

nbAretes :: Int
nbAretes = length listeAretes

depart :: Sommet
depart = 1


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

--permet d'inverser les élements des arêtes
areteInverse :: [Arete] -> [Arete] -> [Arete]
areteInverse [] res = reverse res
areteInverse ((x,y):ls) res = areteInverse ls ((y,x):res)

--permet de prendre le premier sommet d'une arête
premierSommet :: Arete -> Sommet
premierSommet (x,y) = x

--retourne la liste de toutes les arêtes
listeToutesAretes :: [Arete]
listeToutesAretes = listeAretes ++ (areteInverse listeAretes [])

-- trouve le nouveau sommet de référence
nouveauSommet l (x,y) 
	|(elem x l) = y
	|otherwise = x



--permet d'enlever les aretes qui forment un cycle ou qui ne sont pas acceptables à partir d'une liste de sommets deja vus
supprimeMauvaisesAretes :: [Sommet] -> [Arete] -> [Arete]
supprimeMauvaisesAretes _ [] = []
supprimeMauvaisesAretes l ((x,y):xs)  
	|(elem x l) && (elem y l) = (supprimeMauvaisesAretes l xs) --pour éviter les cycles
	|(elem x l) = (x,y) : (supprimeMauvaisesAretes l xs) -- on prend les éléments qui sont accéptables comme suite
	|otherwise = supprimeMauvaisesAretes l xs



--supprime les arêtes déjà vues dans une liste d'arêtes quelconques. 
supprimeAretesDejaVues :: [Arete] -> [Arete] -> [Arete]
supprimeAretesDejaVues l [] = []
supprimeAretesDejaVues l ((x,y):xs)
	|(elem (x,y) l) || (elem (y,x) l) = supprimeAretesDejaVues l xs
	|otherwise = (x,y) : supprimeAretesDejaVues l xs





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

-- calcule les chemins passant par toutes les aretes
arbre :: [[Arete]]
arbre = map reverse (boucle [depart] [] 1 (supprimeMauvaisesAretes [depart] listeAretes))

nbSolutions = length arbre



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


condition :: Int -> Arete -> [Arete] -> Bool
condition i a@(x,y) [] = True --arbre en construction est vide, on peut mettre n'importe quelle arête
condition i a@(x,y) arbre@((c,d):xs)
	| x == d = True
	| x < c  && (x==d) = True
	| x < c = False
	| x == c &&  y > d = (condition i a xs) --verifie si l'on repart du noeud la dernière arête de l'arbre. Si c'est le cas alors la feuille de la derniere arête doit être < à la feuille de l'arête proposé
	|x == c = False 
	| otherwise =  (condition i a xs)



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

boucle :: [Sommet] -> [Arete] -> Int -> [Arete] -> [[Arete]]
boucle _ [] i [] =  []
boucle _ arbre@(x:xs) i [] 
	|(i==nbSommets)&&(condition i x xs) = [arbre]
	|otherwise = []
boucle l arbre i delta@((x,y):xs) 
	|(condition i (x,y) arbre) && (i==nbSommets) = [arbre]
	|(condition i (x,y) arbre) = (boucle (sommetRef:l) ((x,y):arbre) (i+1) (supprimeMauvaisesAretes (sommetRef:l) (supprimeAretesDejaVues ((x,y):arbre) listeToutesAretes))) ++ (boucle l arbre i xs)
	|otherwise = (boucle l arbre i xs)
		where  sommetRef = nouveauSommet l (x,y)