(* ::Package:: *)

(************************************************************************)
(* This file was generated automatically by the Mathematica front end.  *)
(* It contains Initialization cells from a Notebook file, which         *)
(* typically will have the same name as this file except ending in      *)
(* ".nb" instead of ".m".                                               *)
(*                                                                      *)
(* This file is intended to be loaded into the Mathematica kernel using *)
(* the package loading commands Get or Needs.  Doing so is equivalent   *)
(* to using the Evaluate Initialization Cells menu command in the front *)
(* end.                                                                 *)
(*                                                                      *)
(* DO NOT EDIT THIS FILE.  This entire file is regenerated              *)
(* automatically each time the parent Notebook file is saved in the     *)
(* Mathematica front end.  Any changes you make to this file will be    *)
(* overwritten.                                                         *)
(************************************************************************)



BeginPackage["ExplorateurDeGraphes`"];


debut


debutDeclaration::usage=
	"debutDeclaration[] doit \[EHat]tre ex\[EAcute]cut\[EAcute] avant les d\[EAcute]clarations des arcs et des ar\[EHat]tes.";


arc::usage=
	"arc[ndDpt, ndArr] d\[EAcute]clare le nouvel arc\n     \!\(\*
StyleBox[\"ndDpt\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\" \",\nFontSlant->\"Italic\"]\)\[LongRightArrow] \!\(\*
StyleBox[\"ndArr\",\nFontSlant->\"Italic\"]\)\nou l'arc universel\n     \!\(\*
StyleBox[\"ndDpt\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\":\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"var\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\" \",\nFontSlant->\"Italic\"]\)\[LongRightArrow] \!\(\*
StyleBox[\"ndArr\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"(\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"ndDpt\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\")\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\".\",\nFontSlant->\"Italic\"]\)";


arcConditionnel::usage=
	"arcConditionnel[ndDpt, ndArr, condQ] d\[EAcute]clare l'arc universel conditionnel\n     \!\(\*
StyleBox[\"ndDpt\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\":\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"var\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\" \",\nFontSlant->\"Italic\"]\)\[LongRightArrow] \!\(\*
StyleBox[\"ndArr\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"(\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"ndDpt\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\")\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"   \",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"si\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"   \",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"condQ\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"(\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"ndDpt\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\")\",\nFontSlant->\"Italic\"]\).\narcConditionnel \[EAcute]value ses arguments de mani\[EGrave]re non standard.";


arete::usage=
	"arete[ndDpt, ndArr] d\[EAcute]clare les deux arcs\n     \!\(\*
StyleBox[\"ndDpt\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\" \",\nFontSlant->\"Italic\"]\)\[LongRightArrow] \!\(\*
StyleBox[\"ndArr\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"   \",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"et\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"    \",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\"ndArr\",\nFontSlant->\"Italic\"]\)\!\(\*
StyleBox[\" \",\nFontSlant->\"Italic\"]\)\[LongRightArrow] \!\(\*
StyleBox[\"ndDpt\",\nFontSlant->\"Italic\"]\)\no\[UGrave] ndDpt et ndArr sont des sommets factuels (c'est-\[AGrave]-dire des constantes).\nPour d\[EAcute]finir une ar\[EHat]te universelle, il faut d\[EAcute]clarer explicitement deux arcs :\n     arc[ndDpt, ndArr, cond1Q]; arc[ndArr, ndDpt, cond2Q].";


barriereQ::usage=
	"barriereQ est une fonction dont la valeur est True pour tous les sommets \[AGrave] exclure et False pour les sommets valides.\nAvant de d\[EAcute]finir une barri\[EGrave]re, il faut d'abord effacer la barri\[EGrave]re par d\[EAcute]faut\n     Clear[barriereQ]; barriereQ[nd_]:= ...\nbarriereQ est appliqu\[EAcute]e \[AGrave] tous les sommets.";


finDeclaration::usage=
	"finDeclaration[] doit \[EHat]tre ex\[EAcute]cut\[EAcute] avant la premi\[EGrave]re recherche.";


succ::usage=
	"succ[nd] produit la liste des successeurs directs du sommet nd.";


pred::usage=
	"pred[nd] produit la liste des pr\[EAcute]d\[EAcute]cesseurs directs du sommet nd. Cette fonction est restreinte aux sommets factuels (c'est-\[AGrave]-dire d\[EAcute]clar\[EAcute]s dans un arc ordinaire).";


sommetPropriete::usage=
	"ndDpt d\[EAcute]signant un sommet ou une liste de sommets, sommetPropriete[ndDpt, proprQ] retourne les descendants de ndDpt qui v\[EAcute]rifient la propri\[EAcute]t\[EAcute] proprQ \[AGrave] la profondeur d'arr\[EHat]t.";


ensembleSommetsPropriete::usage=
	"ndDpt d\[EAcute]signant un sommet ou une liste de sommets, ensembleSommetsPropriete[ndDpt, proprQ] retourne l'ensemble des descendants de ndDpt qui v\[EAcute]rifient la propri\[EAcute]t\[EAcute] proprQ.\nensembleSommetsPropriete[ndDpt, proprQ, prof] retourne l'ensemble des descendants de ndDpt qui v\[EAcute]rifient la propri\[EAcute]t\[EAcute] proprQ jusqu'\[AGrave] la profondeur de recherche prof.";


ensembleDescendants::usage=
	"ndDpt d\[EAcute]signant un sommet ou une liste de sommets, ensembleDescendants[ndDpt] retourne l'ensemble des descendants de ndDpt, y compris ndDpt.\nensembleDescendants[ndDpt, prof] retourne l'ensemble des descendants de ndDpt jusqu'\[AGrave] la profondeur de recherche prof, y compris ndDpt.";


cheminCourant::usage=
	"Si nd est un sommet, cheminCourant[nd] donne un chemin qui aboutit au sommet nd. Le chemin est d\[EAcute]termin\[EAcute] selon l'\[EAcute]tat courant de l'arbre de recherches apr\[EGrave]s sommetPropriete, ensembleSommetsPropriete ou ensembleDescendants. Si nd est une liste de sommets, cheminCourant est appliqu\[EAcute] \[AGrave] chaque sommet de la liste.";


cheminSimple::usage=
	"cheminSimple[r, butQ, longMax] retourne un chemin simple dont le d\[EAcute]but est r et qui est progressivement rallong\[EAcute] jusqu'\[AGrave] ce que le chemin r v\[EAcute]rifie la propri\[EAcute]t\[EAcute] butQ ou qu'il n'y ait plus de sommet disponible ou que la longueur maximale soit atteinte.\ncheminSimple[r, butQ] \[EAcute]quivaut \[AGrave] cheminSimple[r, butQ, Infinity].";


ensembleCheminsSimples::usage=
	"ensembleCheminsSimples[r, butQ, longMax] retourne l'ensemble des chemins dont le d\[EAcute]but est r, qui v\[EAcute]rifient la propri\[EAcute]t\[EAcute] butQ et dont la longueur est au plus longMax.\nensembleCheminsSimples[r, butQ] \[EAcute]quivaut \[AGrave] ensembleCheminsSimples[r, butQ, Infinity].";


cheminBalises::usage=
	"cheminBalises[ndDpt, buts] retourne un chemin qui part du sommet ndDpt. La premi\[EGrave]re \[EAcute]tape est un chemin vers le sommet le plus proche qui v\[EAcute]rifie la propri\[EAcute]t\[EAcute] buts[[1]]. Le chemin est prolong\[EAcute] vers le sommet le plus proche qui v\[EAcute]rifie la propri\[EAcute]t\[EAcute] buts[[2]]; etc. (chemin avec balises)";


descenteForte::usage=
	"descenteForte[ndDpt, dist] retourne un chemin qui part du sommet ndDpt et se rapproche progressivement du but (dist est une fonction qui mesure l'\[EAcute]loignement du sommet courant au but final). Le programme effectue une recherche locale jusqu'\[AGrave] ce qu'il trouve des sommets dont la distance au but est inf\[EAcute]rieure \[AGrave] la distance courante. Parmi eux, il choisit le sommet de distance minimale.";


descenteFaible::usage=
	"descenteFaible[ndDpt, dist] retourne un chemin qui part du sommet ndDpt et se rapproche progressivement du but (dist est une fonction qui mesure l'\[EAcute]loignement du sommet courant au but final). Le programme effectue une recherche locale jusqu'\[AGrave] ce qu'il trouve des sommets dont la distance au but est inf\[EAcute]rieure \[AGrave] la distance courante. Parmi eux, il choisit le sommet de distance maximale.";


terminalQ::usage=
	"terminalQ[nd] retourne la valeur True si le sommet nd est terminal (c'est-\[AGrave]-dire ne poss\[EGrave]de aucun successeur) et False dans les autres cas.";


racineQ::usage=
	"racineQ[nd] retourne la valeur est True si nd est une racine factuelle (c'est-\[AGrave]-dire d\[EAcute]clar\[EAcute]e dans un arc ordinaire) et False dans les autres cas.";


egalQ::usage=
	"egalQ[nd] est fonction d\[EAcute]finie pour chaque noeud et dont la valeur est True si le noeud est \[EAcute]gal \[AGrave] nd.";


membreQ::usage=
	"membreQ[{n1, ..., nk}] est fonction d\[EAcute]finie pour chaque sommet et dont la valeur est True si le sommet appartient \[AGrave] la liste {n1, ..., nk}.";


cycleQ::usage=
	"cycleQ[n] est fonction d\[EAcute]finie pour chaque chemin et dont la valeur est True si le chemin est un cycle de longueur n.";


longueurQ::usage=
	"longueurQ[n] est fonction d\[EAcute]finie pour chaque chemin et dont la valeur est True si la longueur du chemin est n.";


inclusQ::usage=
	"inclusQ[a, b] est fonction dont la valeur est True si l'ensemble a est inclus dans l'ensemble b.";


passeParQ::usage=
	"passeParQ[a] est fonction d\[EAcute]finie pour chaque chemin et dont la valeur est True si la liste a (form\[EAcute]e de sommets) est incluse dans le chemin.";


sousGrapheQ::usage=
	"sousGrapheQ[g] est fonction d\[EAcute]finie pour chaque chemin et dont la valeur est True si le chemin est inclus dans la liste de sommets g.";


racinesGraphe::usage=
	"racinesGraphe[] retourne la liste des racines factuelles (c'est-\[AGrave]-dire d\[EAcute]clar\[EAcute]es dans un arc ordinaire).";


dernierSommet::usage=
	"dernierSommet[fQ_] applique la fonction fQ au dernier sommet du chemin.";


chaqueSommet::usage=
	"chaqueSommet[fQ_] applique la fonction fQ \[AGrave] tous les sommets d'un chemin r: fQ[r[[1]]]\[And]fQ[r[[2]]]\[And]...\[And]fQ[r[[k]]].";


profondeur::usage=
	"profondeur[] retourne la profondeur dans l'arbre des visites lors de la derni\[EGrave]re recherche.\nprofondeur[p] fixe la profondeur maximale \[AGrave] p pour les recherches ult\[EAcute]rieures.\nLa profondeur maximale par d\[EAcute]faut est de 64.";


cout::usage=
	"cout[] retourne le nombre de sommets visit\[EAcute]s lors de la derni\[EGrave]re recherche.";


enLignes::usage=
	"enLignes[t] affiche la liste de listes t en un tableau.";


enColonnes::usage=
	"enColonnes[t] affiche la liste de listes t en un tableau transpos\[EAcute].";


maxFct::usage=
	"maxFct[d_List, f] retourne un maximum de la fonction f sur le domaine d.";


minFct::usage=
	"minFct[d_List, f] retourne un minimum de la fonction f sur le domaine d.";


Begin["`Private`"];


arc::liste="Un noeud ne peut pas \[EHat]tre de type List.";


arc::arg="Sont attendus deux arguments.";


arcConditionnel::arg="Sont attendus trois arguments.";


arcConditionnel::nonUniversel="Le premier argument doit contenir au moins une variable universelle x_.";


sommetPropriete::profMax=
	"La profondeur maximale de `1` a \[EAcute]t\[EAcute] atteinte.";


sommetPropriete::nonBooleen="Le but doit \[EHat]tre une fonction qui, lorsqu'elle est appliqu\[EAcute]e \[AGrave] un sommet, doit valoir True ou False.";


ensembleSommetsPropriete::nonEntier="Le troisi\[EGrave]me argument doit \[EHat]tre un entier ou Infinity.";


ensembleSommetsPropriete::arg="Sont attendus 2 ou 3 arguments.";


cheminSimple::arg="Sont attendus deux ou trois arguments dont le premier de type List.";


cheminSimple::nonEntier="Le troisi\[EGrave]me argument doit \[EHat]tre un entier ou Infinity.";


cheminSimple::nonBooleen="Le deuxi\[EGrave]me argument est une fonction qui, appliqu\[EAcute]e \[AGrave] un chemin, doit valoir True ou False.";


ensembleCheminsSimples::arg="Sont attendus deux ou trois arguments dont le premier de type List.";


ensembleCheminsSimples::nonEntier="Le troisi\[EGrave]me argument doit \[EHat]tre un entier ou Infinity.";


ensembleCheminsSimples::nonBooleen="Le deuxi\[EGrave]me argument est une fonction qui, appliqu\[EAcute]e \[AGrave] un chemin, doit valoir True ou False.";


descenteForte::nonNum="Le deuxi\[EGrave]me argument doit \[EHat]tre une fonction \[AGrave] valeur non n\[EAcute]gative."


descenteFaible::nonNum="Le deuxi\[EGrave]me argument doit \[EHat]tre une fonction \[AGrave] valeur non n\[EAcute]gative."


profondeur::nonEntier=
	"L'argument doit \[EHat]tre Infinity ou un entier non n\[EAcute]gatif.";


pred::nonDef=
	"L'argument n'est pas un sommet factuel.";


Unprotect[debutDeclaration,arc,arcConditionnel,arete,finDeclaration,succ,pred,sommetPropriete,  ensembleSommetsPropriete,ensembleDescendants,  cheminSimple,ensembleCheminsSimples,cheminBalises,descenteForte,descenteFaible,racinesGraphe,egalQ,membreQ,cycleQ,longueurQ,inclusQ,passeParQ,sousGrapheQ,dernierSommet,chaqueSommet,profondeur, cout, terminalQ, racineQ, enLignes, enColonnes,maxFct,minFct]


Clear[pred, succ]


debutDeclaration[]:=(Clear[trans,predecesseur,barriereQ,pereVisiteur];nbreRegles=0;niveau=0;barriereQ:=False&;ndDptFactuels={};niveauMax=64;$RecursionLimit=512;collectes={};nbreVisites=0;)


arc[ndDpt_List,___]:=Message[arc::liste]


arc[ndDpt_,ndArr_List,___]:=Message[arc::liste]


arc[noeudDpt_,noeudArr_]:=(Increment[nbreRegles];
trans[nbreRegles][noeudDpt]:=noeudArr;If[Not[universelQ[noeudDpt]],
AppendTo[ndDptFactuels,noeudDpt];
If[Head[predecesseur[noeudArr]]===predecesseur,predecesseur[noeudArr]={noeudDpt},predecesseur[noeudArr]=Union[predecesseur[noeudArr],{noeudDpt}]]
];)


arc[___]:=Message[arc::arg]


arete[x_,y_]:=(arc[x,y];arc[y,x];)


SetAttributes[arcConditionnel,HoldAll];


arcConditionnel[ndDpt_,___]:=Message[arcConditionnel::nonUniversel]/;Not[universelQ[ndDpt]]


arcConditionnel[ndDpt_List,___]:=Message[arc::liste]


arcConditionnel[ndDpt_,ndArr_List,___]:=Message[arc::liste]


arcConditionnel[noeudDpt_,noeudArr_, siQ_]:=(Increment[nbreRegles];
trans[nbreRegles][noeudDpt/;siQ]:=noeudArr;)


arcConditionnel[___]:=Message[arcConditionnel::arg]


finDeclaration[]:=Module[{i},
ndDptFactuels=Union[ndDptFactuels];
ndDptFactuels=Complement[ndDptFactuels,Flatten[Map[successeur[#]&,ndDptFactuels],1]];
Do[predecesseur[ndDptFactuels[[i]]]={},{i,1,Length[ndDptFactuels]}];]


pred[x_]:=Message[pred::nonDef]/;Head[predecesseur[x]]===predecesseur


pred[x_]:=predecesseur[x]


successeur[x_]:=Select[Select[Table[trans[j][x],{j,1,nbreRegles}],UnsameQ[Head[Head[#]],trans]&], Not[barriereQ[#]]\[And]UnsameQ[#,x]&]


succ[x_]:=successeur[x]


nonMarqueQ[nd_]:=SameQ[Head[pereVisiteur[nd]],pereVisiteur];


marquage[pere_,fils_]:=Module[{k},
Do[
pereVisiteur[fils[[k]]]=pere ;PreIncrement[nbreVisites],
{k,1,Length[fils]}]]


rechercheRecursiveSommet[niv_,but_]:=Module[{v,ns,suivants,j,aMarquer},
v=Select[niv,but];
If[UnsameQ[v,{}],Return[v]];
If[niveau>=niveauMax,Message[sommetPropriete::profMax, niveauMax];Return[{}]];
ns=Union[Flatten[
Table[
suivants=successeur[niv[[j]]];
aMarquer=Select[suivants,nonMarqueQ];
marquage[niv[[j]],aMarquer];
aMarquer,
{j,1,Length[niv]}]]];
If[SameQ[ns,{}],{},PreIncrement[niveau];rechercheRecursiveSommet[ns,but]]]


sommetPropriete[ndDpt_,butQ_,___]:=Message[sommetPropriete::nonBooleen]/;Not[MemberQ[{True,False},butQ[First[Flatten[{ndDpt}]]]]]


sommetPropriete[ndDpt_,butQ_]:=Module[{depart,j},
niveau=0;Clear[pereVisiteur];
depart=Flatten[{ndDpt}];
nbreVisites=0;marquage[nil,depart];
Union[rechercheRecursiveSommet[depart,butQ]]
]


rechercheRecursiveCollecte[niv_,butQ_, prof_]:=Module[{ns,suivants,j,aMarquer},
If[niveau>=prof,Throw[Null],
If[niveau>=niveauMax,Message[cheminPropriete::profMax, niveauMax];Return[collectes]];
ns=Union[Flatten[
Table[
suivants=successeur[niv[[j]]];
aMarquer=Select[suivants,nonMarqueQ];
marquage[niv[[j]],aMarquer];
collectes=Join[collectes,Select[aMarquer,butQ]];
aMarquer,
{j,1,Length[niv]}]]];
If[SameQ[ns,{}],{},PreIncrement[niveau];rechercheRecursiveCollecte[ns,butQ, prof]]]]


ensembleSommetsPropriete[ndDpt_,butQ_, prof_]:=Message[sommetPropriete::nonBooleen]/;Not[MemberQ[{True,False},butQ[First[Flatten[{ndDpt}]]]]]


ensembleSommetsPropriete[ndDpt_,butQ_, prof_]:=Message[ensembleSommetsPropriete::nonEntier]/;Not[IntegerQ[prof] \[Or] SameQ[prof,Infinity]]


ensembleSommetsPropriete[ndDpt_,butQ_, prof_]:=Module[{depart,parcours,j,nd,precedent, rep},
niveau=0;depart=Flatten[{ndDpt}];
collectes=Select[depart,butQ];Clear[pereVisiteur];
nbreVisites=Length[depart]; marquage[nil, depart];
Catch[rechercheRecursiveCollecte[depart,butQ,prof]];
collectes];


ensembleSommetsPropriete[ndDpt_,butQ_]:=ensembleSommetsPropriete[ndDpt, butQ, Infinity]


ensembleSommetsPropriete[___]:=Message[ensembleSommetsPropriete::arg]


ensembleDescendants[ndDpt_,prof_]:=ensembleSommetsPropriete[ndDpt, True&,prof];


ensembleDescendants[ndDpt_]:=ensembleSommetsPropriete[ndDpt, True&,Infinity];


cheminCourant[nd_List]:=Map[cheminCourant,nd]


cheminCourant[nd_]:={}/;SameQ[Head[pereVisiteur[nd]],pereVisiteur]


cheminCourant[nd_]:=Module[{c,r,p},r={nd};p=pereVisiteur[nd];
While[UnsameQ[p,nil],c=p;PrependTo[r,c];p=pereVisiteur[c]];
r]


iterCheminSimple[r_,butQ_,longMax_]:=Module[{c,i},
PreIncrement[nbreVisites];
If[butQ[r] ,Throw[r],
If[c=Complement[successeur[Last[r]],r];UnsameQ[c,{}]\[And]Length[r]<=longMax,
Do[
iterCheminSimple[Append[r,c[[i]]],butQ,longMax]
, {i,1,Length[c]}]]]]


cheminSimple[r_List,butQ_, longMax_]:=Message[cheminSimple::nonEntier]/;Not[IntegerQ[longMax] \[Or]SameQ[longMax,Infinity]]


cheminSimple[r_List,butQ_,___]:=Message[cheminSimple::nonBooleen]/;TrueQ[Not[MemberQ[{True,False},butQ[r]]]]


cheminSimple[r_List,butQ_, longMax_]:=Module[{ch},nbreVisites=0;ch=Catch[iterCheminSimple[r,butQ,longMax]];niveau=Length[ch]-1;
If[ch===Null,{},ch]]


cheminSimple[r_List,butQ_]:=cheminSimple[r,butQ,Infinity]


cheminSimple[___]:=Message[cheminSimple::arg]


iterCheminCollecte[r_,butQ_, longMax_]:=Module[{c,i},
PreIncrement[nbreVisites];
If[butQ[r] ,AppendTo[collectes,r]; If[niveau<Length[r]-1,niveau=Length[r]-1]];
If[c=Complement[successeur[Last[r]],r];UnsameQ[c,{}]\[And] Length[r]-1<longMax,
Do[
iterCheminCollecte[Append[r,c[[i]]],butQ, longMax]
, {i,1,Length[c]}]]]


ensembleCheminsSimples[r_List,butQ_, longMax_]:=Message[ensembleCheminsSimples::nonEntier]/;Not[IntegerQ[longMax] \[Or]SameQ[longMax,Infinity]]


ensembleCheminsSimples[r_List,butQ_, longMax_]:=(collectes={};nbreVisites=0;niveau=0;iterCheminCollecte[r, butQ, longMax];
collectes)


ensembleCheminsSimples[r_List,butQ_]:=ensembleCheminsSimples[r,butQ,Infinity]


ensembleCheminsSimples[r_List,butQ_,___]:=Message[ensembleCheminsSimples::nonBooleen]/;Not[MemberQ[{True,False},butQ[r]]]


ensembleCheminsSimples[___]:=Message[ensembleCheminsSimples::arg]


cheminBalises[ndDpt_,buts_List]:=Module[{ch,ndCrt,j,prix},
ndCrt=Last[Flatten[{ndDpt}]];
ch={ndCrt};
prix=0;
Do[
ndCrt=sommetPropriete[ndCrt,buts[[j]]];
prix+=nbreVisites;
If[ndCrt==={},Return[ch], ndCrt=First[ndCrt]];
ch=Join[ch, Delete[cheminCourant[ndCrt],1]]
,{j,1,Length[buts]}];
niveau=Length[ch]-1;
nbreVisites=prix;
ch]


descenteForte[ndDpt_, dist_]:=Message[descenteForte::nonNum]/;SameQ[Head[NonNegative[dist[ndDpt]]],NonNegative]\[Or]Not[NonNegative[dist[ndDpt]]]


descenteForte[ndDpt_, dist_]:=Module[{ndCrt,distCrt,ch,suiv,prix},
ndCrt=ndDpt;
distCrt=dist[ndCrt];
ch={ndCrt};
prix=0;
While[distCrt>0,
suiv=sommetPropriete[ndCrt,dist[#]<distCrt&];
prix+=nbreVisites;
If[Length[suiv]==0,Return[{}]];
{ndCrt,distCrt}=minFct[suiv,dist];
ch=Join[ch,Delete[cheminCourant[ndCrt],1]]
];
niveau=Length[ch]-1;
nbreVisites=prix;
ch]


descenteFaible[ndDpt_, dist_]:=Message[descenteFaible::nonNum]/;SameQ[Head[NonNegative[dist[ndDpt]]],NonNegative]\[Or]Not[NonNegative[dist[ndDpt]]]


descenteFaible[ndDpt_, dist_]:=Module[{ndCrt,distCrt,ch,suiv,prix},
ndCrt=ndDpt;
distCrt=dist[ndCrt];
ch={ndCrt};
prix=0;
While[distCrt>0,
suiv=sommetPropriete[ndCrt,dist[#]<distCrt&];
prix+=nbreVisites;
If[Length[suiv]==0,Return[{}]];
{ndCrt,distCrt}=maxFct[suiv,dist];
ch=Join[ch,Delete[cheminCourant[ndCrt],1]]
];
niveau=Length[ch]-1;
nbreVisites=prix;
ch]


terminalQ[nd_]:=successeur[nd]==={}


racineQ[nd_]:=predecesseur[nd]==={}


universelQ[nd_]:=StringMatchQ[ToString[nd],"*_*"]


membreQ[x_List]:=TrueQ[MemberQ[x,#]]&


egalQ[x_]:=SameQ[#,x]&


cycleQ[n_Integer][r_List]:=Length[r]-1===n \[And] MemberQ[successeur[Last[r]],First[r]]


longueurQ[n_Integer][r_List]:=Length[r]-1===n


passeParQ[a_List][r_List]:=Complement[a, r]==={}


inclusQ[a_List, b_List]:=Complement[a, b]==={}


sousGrapheQ[g_List][ r_List]:=Complement[r, g]==={}


racinesGraphe[]:=ndDptFactuels


profondeur[]:=niveau


profondeur[p_]:=Message[profondeur::nonEntier]/;Not[p===Infinity \[Or] (IntegerQ[p] \[And]NonNegative[p])]


profondeur[p_]:=($RecursionLimit=8*p;niveauMax=p)


cout[]:=nbreVisites


dernierSommet[fQ_][r_List]:=fQ[Last[r]]


chaqueSommet[fQ_][r_List]:=Apply[And,Map[fQ,r]]


enLignes[x_List]:={}/;Flatten[x]=={}


enLignes[x_List]:=TableForm[x]/;UnsameQ[Head[First[x]],List]


enLignes[x_List]:=Module[{m},
m=Max[Map[Length,x]];
TableForm[
Table[
Join[x[[i]],Table["",{m-Length[x[[i]]]}]],
{i,1,Length[x]}]]]


enColonnes[x___]:=x


enColonnes[x_List]:={}/;Flatten[x]==={}


enColonnes[x_List]:=TableForm[x]/;UnsameQ[Head[First[x]],List]


enColonnes[x_List]:=Module[{m},
m=Max[Map[Length,x]];
TableForm[Transpose[
Table[
Join[x[[i]],Table["",{m-Length[x[[i]]]}]],
{i,1,Length[x]}]]]]


enColonnes[x___]:=x


maxFct[domaine_List, f_]:=Module[{x,y,v,j},
x=domaine[[1]];
y=f[x];
Do[
v=f[domaine[[j]]];
If[v>y,x=domaine[[j]];y=v],
{j,2,Length[domaine]}];
{x,y}]


minFct[domaine_List, f_]:=Module[{x,y,v,j},
x=domaine[[1]];
y=f[x];
Do[
v=f[domaine[[j]]];
If[v<y,x=domaine[[j]];y=v],
{j,2,Length[domaine]}];
{x,y}]


nbreRegles=0;niveau=0;barriereQ:=False&;ndDptFactuels={};collectes={};niveauMax=64;nbreVisites=0;


End[];


Protect[debutDeclaration,arc,arcConditionnel,arete,finDeclaration,succ,pred,sommetPropriete,  ensembleSommetsPropriete,ensembleDescendants, cheminSimple,ensembleCheminsSimples,cheminBalises,descenteForte,descenteFaible,racinesGraphe,egalQ,membreQ,cycleQ,longueurQ,inclusQ,passeParQ,sousGrapheQ,dernierSommet, chaqueSommet,profondeur, cout, terminalQ, racineQ, enLignes, enColonnes,maxFct,minFct]


EndPackage[]