BlueLogo

Home Orange Blue Green Pink

Package CSPenumeresc

Met à disposition les outils et type nécessaire pour construire et resoudre des CSP
dont les variables sont liees par des contraintes mises sous la forme de tableaux de Booleens.

Author : Iver BAILLY-SALINS, Mehmet CELIKBAS

Date : 24.07.2002

Clauses

Quick access : Clauses - Generic part - Declarations - Subprograms

Context clauses
P_Lst_Gen est un package generique contenant les fonctions de base sur les listes.
for package ->	p_lst_gen
for package ->	ada.integer_text_io
for package ->	ada.text_io
for package ->	Ada.Numerics.Discrete_Random

Use clauses
for package ->	ada.text_io
for package ->	ada.integer_text_io
EnumCSP est le package Ada.Numerics.Discrete_Random instancie avec le type discret typeCSP
for package ->	EnumCSP
for package ->	ListeDindices

Generic Parameters

Quick access : Clauses - Generic part - Declarations - Subprograms

Types
*Name*	*Declaration*
Le type generique typeCSP est le type des valeurs des domaines sur lesquels on souhaite appliquer les algorithmes, ce type doit etre discret.
typeCSP	( <> )

Declarations

Quick access : Clauses - Generic part - Declarations - Subprograms

Types
*Name*	*Declaration*
Le type CSPenumere est la structure generale contenant les variables et les contraintes d'un reseau de contraintes.
CSPenumere	private
TableauDe01Contrainte	array ( Integer range <> , Integer range <> ) of Bool01
Le type etat garde en memoire les recherches AC PC faites sur la CSP.
etat	( NA , AC , AC_non_PC , non_AC , PC , non_PC )
CoupleDinteger	array ( Integer range 1..2 ) of Integer

Subtypes
*Name*	*Declaration*
Les variables sont identifiees par leur nom par l'utilisateur. Ces noms sont des mots de 8 caracteres:
Nom	String ( 1..8 )
Tableaux de Booleens mis sous forme Integer:
Bool01	Integer range 0..1

Subprograms

Quick access : Clauses - Generic part - Declarations - Subprograms

Afficherindice (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN	ind	Integer

AfficherListeIndice (procedure)

CreerCSP (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
La procedure CreerCSP sert a initialiser une CSP declaree au prealable.

AjouterVariableCSP (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
IN	NomVariable	Nom
La procedure AjouterVariableCSP sert a ajouter une Variable a une CSP existante. La variable ajoutee est reconnue par son nom. Ses autres attributs seronts initialises: domaine vide, pas de contraintes. On interdit d'ajouter une Variable a une CSP si cette variable a le meme nom qu'une variable existante dans cette CSP.

SupprimerVariableCSP (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
IN	NomVariable	Nom
La procedure SupprimerVariableCSP sert a Supprimer une Variable a une CSP existante. La variable Supprimee est reconnue par son nom. Toutes les contraintes liant cette variable sont supprimees avec la procedure SupprimerContrainteCSP.

AjouterContrainteCSP (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
IN	NomVariable1	Nom
IN	NomVariable2	Nom
La procedure AjouterContrainteCSP ajoute une contrainte a la CSP fournie en 1e paramatre entre les variables dont les noms sont fournis en 2e et 3e parametres. Cette contraintes est initialisee a un tableau de 1. Les 2 variables impliquees dans la contrainte sont modifiees: leur liste de contraintes reliees est mise a jour.

SupprimerContrainteCSP (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
IN	NomVariable1	Nom
IN	NomVariable2	Nom
La procedure SupprimerContrainteCSP Supprime une contrainte a la CSP fournie en 1e paramatre entre les variables dont les noms sont fournis en 2e et 3e parametres. On verifie que cette contrainte existe. Les 2 variables impliquees dans la contrainte sont modifiees: leur liste de contraintes reliees est mise a jour.

AjouterValeurADomaine (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN	Valeur	TypeCSP
IN OUT	CSP	CSPenumere
IN	NomVariable	Nom
La procedure AjouterValeurADomaine ajoute une valeur au domaine d' une variable presente dans une CSP. Le nom de la valeur a ajouter est fourni en 1e parametre, la CSP a modifier en 2e et le nom de la variable de cette CSP a modifier en 3e parametres. Toutes les contraintes existante impliquant la variable modifiee son reinitialisees a des tableaux de 1. Les possibilites du domaine modifie sont egalement reinitialisees.

AjouterValeursADomaine (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere
IN	NomVariable	Nom
IN	FirstValeur	Integer
IN	LastValeur	Integer
La procedure AjouterValeursADomaine a pour but de rendre plus facile l'ajout de multiples valeurs au domaine d'une variable. Cette procedure ajoute automatiquement les valeurs dont la position est comprises entre l'integer fourni en 3e parametre et celui fourni en 4e parametre dans le type generique typeCSP. On ajoute ensuite ces valeurs au domaine de la variable dont le nom est fourni en 2e parametre, dans la CSP fournie en 1e parametre.

SupprimerValeurADomaine (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN	Valeur	TypeCSP
IN OUT	CSP	CSPenumere
IN	NomVariable	Nom
La procedure SupprimerValeurADomaine est l'inverse de la procedure AjouterValeursADomaine Le nom de la valeur a supprimer est fourni en 1e parametre, la CSP a modifier en 2e et le nom de la variable de cette CSP a modifier en 3e parametres. Toutes les contraintes existante impliquant la variable modifiee son reinitialisees a des tableaux de 1. Les possibilites du domaine modifie sont egalement reinitialisees.

ReinitialiserPossibilitesCSP (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
La procedure ReinitialiserPossibilitesCSP reinitialise les possibilites de toutes les variables de la CSP fournie en parametre. Toutes les valeurs des domaines sont inserees dans la liste des valeurs possibles

ValeurImpossible (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN	Valeur	TypeCSP
IN OUT	CSP	CSPenumere
IN	NomVariable	Nom
La procedure ValeurImpossible a pour but de retirer une valeur aux valeurs possibles d'une variable, sans toutefois la supprimer du domaine.(On peut ainsi garder les contraintes predefinies). ATTENTION : Cette procedure n'est pas destinee a etre utilisee dans les algorithmes. Le nom de la valeur a declarer impossible est fourni en 1e parametre, la CSP impliquee en 2e parametre. La variable dont on declare une valeur du domaine impossible est identifiee par son nom fourni en 3e parametre.

RenommerVariable (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere
IN	AncienNom	Nom
IN	NouveauNom	Nom
La procedure RenommerVariable change le nom de la variable dont l'ancien nom est passe en 2e parametre. Le nouveau nom est passe en 3e parametre et la CSP modifiee en 1e parametre. Le nom d'une variable est important car il sert a designer les variables dans toute les procedures accessibles a l'utilisateur.

AfficherVariables (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN	CSP	cspenumere
IN	F	File_type
La procedure AfficherVariables affiche toute les variables d'une CSP passee en 1e parametre dans la sortie fournie en 2e parametre en utilisant la procedure AfficherVariable.

AfficherContraintes (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN	CSP	cspenumere
IN	F	File_type
La procedure AfficherContraintes affiche toute les contraintes d'une CSP passee en 1e parametre dans la sortie fournie en 2e parametre.

AfficherCSP (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN	CSP	cspenumere
IN	F	File_type
La procedure AfficherContraintes affiche toute les variables et les contraintes d'une CSP passee en 1e parametre dans la sortie fournie en 2e parametre en utilisant les procedure AfficherVariables et AfficherContraintes.

DefinirContrainteCSPauHazard (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
IN	NomVariable1	Nom
IN	NomVariable2	Nom
IN	ProportionTrue	Integer
IN	ProportionFalse	Integer
La procedure DefinirContrainteCSPauHazard sert a remplir le tableau de boolean d'une contrainte existante entre 2 variables. La CSP impliquee est fourni en 1e parametre, le nom des 2 variables entre lesquelles on definit la contraintes sont fournis en 2e et 3e parametres. Le tableau de la CSP sera rempli au hazard par des True, False dont les proportions sont fournies en 4e et 5e parametres. REMARQUE: Les deux contraintes symetriques definies entre Variable1 et Variable2 et entre Variable2 et Variable1 sont definies en meme temps.

EntrerTableauContrainteCSP (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
IN	NomVariable1	Nom
IN	NomVariable2	Nom
IN	Tab	TableauDe01Contrainte
La procedure EntrerTableauContrainteCSP sert a remplir le tableau de boolean d'une contrainte existante entre 2 variables en rentrant directement un tableau de 0 et de 1 de la bonne taille. La CSP impliquee est fourni en 1e parametre, le nom des 2 variables entre lesquelles on definit la contraintes sont fournis en 2e et 3e parametres, le tableau de 0/1 est fourni en 4e parametre. REMARQUE: Les deux contraintes symetriques definies entre Variable1 et Variable2 et entre Variable2 et Variable1 sont definies en meme temps.

AjouterToutesContraintesCSPauHazard (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere
IN	ProportionTrue	Integer
IN	ProportionFalse	Integer
La procedure AjouterToutesContraintesCSPauHazard ajoute toute les contraintes possibles a la CSP et les rempli au hazard En utilisant la procedure DefinirContrainteCSPauHazard avec les proportion de True et de False fournies en 2e et 3e parametre.

lireCSPenumeree (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN	NomFichier	string
IN OUT	CSP	CSPenumere
La procedure lireCSPenumeree permet de lire une CSP dans un fichier. Le format de ce fichier est stricte et doit etre respecte par l'utilisateur.

InstancierVariableIndice (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
IN	Variable	Integer
IN	Valeur	Integer
La procedure InstancierVariableIndice instancie une variable a une valeur de son domaine. La variable et la valeur dans le domaine sont reconnus par leurs indices fournis en 2e et 3e parametres. Cette procedure est utilisee dans des algorithmes de resolution.

InstancierVariableNom (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	CSPenumere
IN	Variable	Nom
IN	Valeur	typeCSP
La procedure InstancierVariableNom instancie une variable a une valeur de son domaine. La variable et la valeur dans le domaines sont reconnus par leurs noms fournis en 2e et 3e parametres. Cette procedure ne doit pas etre utilisee dans des algorithmes de resolution : pour cela utiliser la procedure InstancierVariableIndice.

TrouverVariable (function)
*Parameters*	*Name*	*Type*	*default value*
IN	NomVariable	Nom
IN	CSP	CSPenumere
*Return*		Integer
La fonction TrouverVariable renvoit l' indices (dans le tableau de variable d'une CSP fournie en 2e parametre) De la variable dont le nom est fournit en 1e parametre. Si ce nom n'est pas trouver dans le tableau de variable de la CSP, la fonction renvoit 0.

TrouverValeur (function)
*Parameters*	*Name*	*Type*	*default value*
IN	CSP	cspenumere
IN	Valeur	typeCSP
IN	Var	Integer
*Return*		Integer
La fonction TrouverValeur renvoit l' indice (dans le domaine d'une variable fournie en 2e parametre) De la valeur dont le nom est fournit en 1e parametre. Si ce nom n'est pas trouver dans le domaine de la variable, la fonction renvoit 0.

TrouverContrainte (function)
*Parameters*	*Name*	*Type*	*default value*
IN	CSP	cspenumere
IN	indice1	Integer
IN	indice2	Integer
*Return*		CoupleDinteger
La fonction TrouverContraine renvoit le couple d'indices (dans le tableau de contraintes d'une CSP fournie en 1e parametre) Des 2 contraintes symetriques reliant les variables qui nous interressent. Ces Variables sont identifiees par leur indice dans le tablea de variables de la CSP. Ces indices sont fournis en 2e et 3e parametres. Si ces contraintes ne sont pas trouvees, la fonction renvoit (0,0).

ValeursPossibles (function)
*Parameters*	*Name*	*Type*	*default value*
IN	CSP	cspenumere
IN	Var	nom
*Return*		ListeDindices.Lst
La fonction ValeursPossibles renvoit la liste des valeurs qui n'ont pas ete filtres lors de l'utilisation de la CSP. Ces valeurs sont identifiees par leurs indices dans le tableau de valeurs initiales de la variable consideree.La CSP est passee en 1e argument et le nom de la variable consideree est passe en 2e argument.

EtatCSP (function)
*Parameters*	*Name*	*Type*	*default value*
IN	CSP	cspenumere
*Return*		Etat
La fonction EtataCSP renvoit l'etat de la CSP vis a vis des filtrages effectues dessu (voir le type Etat).

copie (function)
*Parameters*	*Name*	*Type*	*default value*
IN	CSP	cspenumere
*Return*		cspenumere
La fonction copie renvoit une CSP qui est la copie de la CSP fournie en 1e argument. l'affectation CSP2:=CSP1 est a eviter car elle laisse des liens entre la CSP1 et la CSP2, a cause des listes et pointeurs utilises dans les structures de donnees.

AC3 (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere

AC2000 (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere

PC2 (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere
IN	initialisation	boolean

resolutionPC2TouteSolution (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere
IN	Fichier	string

resolutionPC2UneSolution (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere
IN	Fichier	string

resolutionAC2000TouteSolution (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere
IN	Fichier	string

resolutionAC2000UneSolution (procedure)
*Parameters*	*Name*	*Type*	*default value*
IN OUT	CSP	cspenumere
IN	Fichier	string

created by AdaDoc, 8. 23. 2002

Home Orange Blue Green Pink