2563 lines
70 KiB
C++
2563 lines
70 KiB
C++
/***************************************************************************
|
|
ma.C
|
|
-------------------
|
|
begin : Tue Jul 16 2002
|
|
copyright : (C) 2002 by Yann Esposito
|
|
email : esposito@cmi.univ-mrs.fr
|
|
***************************************************************************/
|
|
|
|
/*
|
|
Pour les notes, voir le fichier "ffa.h".
|
|
See "ffa.h" file to view notes.
|
|
*/
|
|
|
|
#include "ma.H"
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
#include <sstream>
|
|
#include <algorithm>
|
|
#include "simplex.H"
|
|
|
|
RESULT MA::save_dot (const string Filename, int precision, bool noms_etats,
|
|
bool multiple_trans) const
|
|
{
|
|
return save_dot (Filename.c_str (), precision, noms_etats, multiple_trans);
|
|
}
|
|
|
|
|
|
/// ------- MÈthodes internes ---------
|
|
float
|
|
MA::random (float min, float max) const
|
|
{
|
|
if (PFA_SAFE)
|
|
{
|
|
assert (min <= max);
|
|
}
|
|
return ((((float) rand () + 1) / INT_MAX) * (max - min)) +
|
|
min;
|
|
}
|
|
|
|
/// --------------------- Constructeurs et Destructeurs ----------------------
|
|
// Constructeur par dÈfaut
|
|
MA::MA (int nb_lettres, int nb_etats)
|
|
{
|
|
// Initialisation de l'alphabet
|
|
int i;
|
|
for (i = 0; i < nb_lettres; ++i)
|
|
{
|
|
Sigma.insert ('a' + i);
|
|
}
|
|
|
|
// Initialisation de l'ensemble d'Ètats
|
|
for (i = 0; i < nb_etats; ++i)
|
|
Q.insert (i);
|
|
|
|
// Initialisation de iota
|
|
StateSet::iterator q;
|
|
for (q = Q.begin (); q != Q.end (); ++q)
|
|
iota[*q] = 0;
|
|
if (nb_etats != 0)
|
|
iota[*(Q.begin ())] = 1;
|
|
|
|
// Initialisation de tau
|
|
for (q = Q.begin (); q != Q.end (); ++q)
|
|
tau[*q] = 1;
|
|
|
|
// Initialisation de phi
|
|
// On laise phi complËtement vide, l'automate n'a pas d'arÍte ‡ l'initialisation.
|
|
}
|
|
|
|
// Destructeur par dÈfaut
|
|
MA::~MA ()
|
|
{}
|
|
|
|
|
|
/// -------------------------- Affichage ----------------------------------
|
|
|
|
// Fonction d'affichage d'automate
|
|
string MA::message (void) const
|
|
{
|
|
string
|
|
mesg; // La variable qui va contenir le message a afficher.
|
|
char
|
|
flottant[3 * (sizeof (float)) + 1]; // un tableau suffisamment grand pour Ècrire un flottant en dÈcimal.
|
|
mesg = "--- AFFICHAGE de " + name + " ---\n";
|
|
|
|
if (PFA_VERBOSE)
|
|
{
|
|
// Affichage du dictionnaire
|
|
for (Dictionnaire::const_iterator d = alph.begin ();
|
|
d != alph.end (); ++d)
|
|
{
|
|
mesg += "alph[";
|
|
mesg += d->first;
|
|
mesg += "]=" + d->second + " ; ";
|
|
}
|
|
mesg += "\n";
|
|
}
|
|
|
|
// Affichage de l'alphabet
|
|
Alphabet::const_iterator l;
|
|
mesg += "Sigma = {";
|
|
if (Sigma.empty ())
|
|
{
|
|
mesg += "}\n";
|
|
}
|
|
else
|
|
{
|
|
for (l = Sigma.begin (); l != Sigma.end ();)
|
|
{
|
|
if (alph.find (*l) == alph.end ())
|
|
{
|
|
mesg += *l;
|
|
}
|
|
else
|
|
{
|
|
mesg += (alph.find (*l))->second;
|
|
}
|
|
|
|
if (++l != Sigma.end ())
|
|
{
|
|
mesg += ", ";
|
|
}
|
|
else
|
|
{
|
|
mesg += "}\n";
|
|
}
|
|
}
|
|
}
|
|
|
|
// Affichage des Ètats
|
|
StateSet::const_iterator e;
|
|
mesg += "Q = {";
|
|
e = Q.begin ();
|
|
if (e == Q.end ())
|
|
{
|
|
mesg += "}\n";
|
|
}
|
|
while (e != Q.end ())
|
|
{
|
|
sprintf (flottant, "%d", *e);
|
|
mesg += flottant;
|
|
e++;
|
|
if (e != Q.end ())
|
|
{
|
|
mesg += ", ";
|
|
}
|
|
else
|
|
{
|
|
mesg += "}\n";
|
|
}
|
|
}
|
|
|
|
// Affichage de iota
|
|
SFunc::const_iterator s;
|
|
stringstream convert;
|
|
string nombre;
|
|
mesg += "iota : ";
|
|
for (s = iota.begin (); s != iota.end (); ++s)
|
|
{
|
|
mesg += "(";
|
|
sprintf (flottant, "%d", s->first);
|
|
mesg += flottant;
|
|
mesg += ", ";
|
|
//convert << s->second;
|
|
//convert >> nombre;
|
|
//mesg += nombre;
|
|
sprintf (flottant, "%f", s->second);
|
|
mesg += flottant;
|
|
mesg += ") ";
|
|
}
|
|
mesg += "\n";
|
|
|
|
// Affichage de tau
|
|
mesg += "tau : ";
|
|
int i=0;
|
|
for (s = tau.begin (); s != tau.end (); ++s)
|
|
{
|
|
mesg += "(";
|
|
sprintf (flottant, "%d", s->first);
|
|
mesg += flottant;
|
|
mesg += ", ";
|
|
sprintf (flottant, "%f", s->second);
|
|
mesg += flottant;
|
|
mesg += ") ";
|
|
if (i++%5 == 0) {
|
|
mesg += "\n";
|
|
}
|
|
}
|
|
mesg += "\n";
|
|
|
|
// Affichage de phi
|
|
mesg += "phi : ";
|
|
if (phi.empty ())
|
|
mesg += "vide";
|
|
else
|
|
{
|
|
LettreSFunc::const_iterator a;
|
|
Graph::const_iterator q;
|
|
for (q = phi.begin (); q != phi.end (); q++)
|
|
{
|
|
for (a = q->second.begin ();
|
|
a != q->second.end (); a++)
|
|
{
|
|
for (s = a->second.begin ();
|
|
s != a->second.end (); s++)
|
|
{
|
|
mesg += "(";
|
|
sprintf (flottant, "%d",
|
|
q->first);
|
|
mesg += flottant;
|
|
mesg += ",";
|
|
|
|
// on Ècrit la bonne lettre
|
|
if (alph.find (a->first) ==
|
|
alph.end ())
|
|
mesg += a->first;
|
|
else
|
|
mesg += alph.find (a->first)->second;
|
|
|
|
mesg += ",";
|
|
sprintf (flottant, "%d", s->first);
|
|
mesg += flottant;
|
|
mesg += ") = ";
|
|
sprintf (flottant, "%f", s->second);
|
|
mesg += flottant;
|
|
mesg += " ; ";
|
|
}
|
|
}
|
|
mesg+="\n";
|
|
}
|
|
}
|
|
mesg += "\n";
|
|
|
|
return mesg;
|
|
}
|
|
|
|
// Chargement d'un fichier dot pour l'affichage de graphe
|
|
RESULT
|
|
MA::save_dot (const char *Filename,
|
|
const int precision,
|
|
const bool noms_etats,
|
|
const bool multiples_trans) const
|
|
{
|
|
try
|
|
{
|
|
if (Filename == NULL)
|
|
{
|
|
throw 0;
|
|
}
|
|
|
|
ofstream fp (Filename);
|
|
if (!fp)
|
|
{
|
|
throw 1;
|
|
}
|
|
fp.precision (precision); //fp.flags(ios::scientific);
|
|
|
|
if (!name.empty ())
|
|
fp << "digraph \"" << name << "\" {" << endl;
|
|
else
|
|
fp << "digraph G {" << endl;
|
|
|
|
// On met le graphe en mode horizontal (Left to Right)
|
|
fp << "graph [rankdir=LR]" << endl;
|
|
|
|
Graph::const_iterator q;
|
|
StateSet::const_iterator e;
|
|
LettreSFunc::const_iterator a, b;
|
|
SFunc::const_iterator s, r;
|
|
StateSet W;
|
|
Dictionnaire::const_iterator tl;
|
|
|
|
for (e = Q.begin (); e != Q.end (); ++e)
|
|
{
|
|
// On crÈe la flÍche d'initialisation si il y a lieu
|
|
if ((iota.find (*e) != iota.end ()) && (iota.find (*e)->second != 0))
|
|
{
|
|
fp << "iota" << *e << "[shape=plaintext, label = ";
|
|
fp << (iota.find (*e))->
|
|
second << " psfrag = \"$";
|
|
fp << (iota.find (*e))->
|
|
second << "$\", height=.15]" <<
|
|
endl;
|
|
fp << "iota" << *e << " -> " << *e <<
|
|
"[minlen=1]" << endl;
|
|
}
|
|
|
|
// on cree l'etat avec ses attributs
|
|
fp << *e;
|
|
fp << " [ label = \"";
|
|
if (noms_etats)
|
|
{
|
|
fp << *e << "\\n";
|
|
}
|
|
// if ((iota.find(*e) != iota.end()) &&
|
|
// (iota.find(*e)->second != 0)) {
|
|
//fp << "i=" << (iota.find(*e))->second << "\\n";
|
|
//
|
|
if ((tau.find (*e) != tau.end ())
|
|
&& (tau.find (*e)->second != 0))
|
|
{
|
|
fp << (tau.find (*e))->second;
|
|
fp << "\",peripheries=2";
|
|
}
|
|
else
|
|
{
|
|
fp << "\"";
|
|
}
|
|
fp << "]" << endl;
|
|
|
|
// on ecrit ses successeurs
|
|
q = phi.find (*e);
|
|
if (q != phi.end ())
|
|
{
|
|
if (multiples_trans)
|
|
{
|
|
for (a = q->second.begin ();a != q->second.end (); a++)
|
|
{
|
|
for (s =(a->second).begin ();s !=(a->second).end ();s++)
|
|
{
|
|
if (s->second !=0)
|
|
fp << "\t" << q->first;
|
|
fp << " -> " << s->first;
|
|
fp << "[label=\"";
|
|
tl = alph.find(a->first);
|
|
if (tl == alph.end()) {
|
|
throw 3;
|
|
}
|
|
fp << tl->second;
|
|
fp << "," << s->second;
|
|
fp << "\"]" << endl;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
// le W sert a ne pas s'occuper plusieurs fois de l'etat d'arrive
|
|
W.clear();
|
|
for (a = q->second.begin (); a != q->second.end (); a++)
|
|
{
|
|
for (s =(a->second).begin ();s !=(a->second).end ();s++)
|
|
{
|
|
if (s->second !=0)
|
|
{
|
|
if (W.find(s->first)==W.end())
|
|
{
|
|
W.insert (s->first);
|
|
fp << "\t" << q->first << " -> " << s->first;
|
|
fp << "[label=\"";
|
|
tl=alph.find(a->first);
|
|
if (tl == alph.end())
|
|
throw 3;
|
|
fp << tl->second << "," << s->second;
|
|
for (b = a; ++b != q->second.end ();)
|
|
{
|
|
r = b->second.find (s->first);
|
|
if (r != b->second.end ())
|
|
{
|
|
fp << "\\n";
|
|
tl = alph.find (b->first);
|
|
if (tl == alph.end())
|
|
throw 3;
|
|
fp << tl->second << "," << r->second;
|
|
}
|
|
}
|
|
fp << "\"]" << endl;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
fp << "}" << endl;
|
|
return VAL (0);
|
|
}
|
|
catch (int erreur)
|
|
{
|
|
if (PFA_VERBOSE)
|
|
{
|
|
cerr << "ERREUR MA::save_dot" << endl;
|
|
switch (erreur)
|
|
{
|
|
case 0:
|
|
cerr << "\tFilename == NULL !!!" << endl;
|
|
break;
|
|
case 1:
|
|
cerr << "\tErreur d'ouverture du fichier " << Filename << endl;
|
|
break;
|
|
case 3:
|
|
cerr << "\tErreur du dictionnaire toutes les lettres ne sont pas definies" << endl;
|
|
default:
|
|
cerr << "Erreur n∞" << erreur << endl;
|
|
break;
|
|
}
|
|
}
|
|
return ERR (erreur);
|
|
}
|
|
}
|
|
|
|
// Fonction d'affichage d'automate sur la sortie standart
|
|
RESULT MA::affiche (void) const
|
|
{
|
|
cout << message ();
|
|
return VAL (0);
|
|
}
|
|
|
|
/// --------------------- Entree sortie su fichier ------------------------------
|
|
|
|
RESULT MA::save (ofstream &fp, const FormatSauvegarde c_format) const
|
|
{
|
|
try
|
|
{
|
|
// les itÈrateur pour la structure
|
|
Graph::const_iterator q;
|
|
LettreSFunc::const_iterator a;
|
|
SFunc::const_iterator s;
|
|
StateSet::const_iterator e;
|
|
Dictionnaire::const_iterator l;
|
|
|
|
// la precision de sortie est maximale
|
|
fp.precision (20);
|
|
// first case format ffa or mdi
|
|
switch (c_format)
|
|
{
|
|
case paffa:
|
|
// calculation of the number of edges
|
|
// Entete writing
|
|
fp << "% MA file generated" << "\n";
|
|
fp << "name \t" << name << "\n";
|
|
|
|
fp << "alph\n";
|
|
for (l=alph.begin() ; l != alph.end() ; ++l) {
|
|
fp << l->first << " \t" << l->second << "\n";
|
|
}
|
|
fp << ".\n";
|
|
|
|
fp << "iota\n";
|
|
for (s=iota.begin() ;s != iota.end() ; ++s) {
|
|
fp << s->first << " \t" << s->second << "\n";
|
|
}
|
|
fp << ".\n";
|
|
|
|
fp << "tau\n";
|
|
for (s=tau.begin() ; s != tau.end() ;++s) {
|
|
fp << s->first << " \t" << s->second << "\n";
|
|
}
|
|
fp << ".\n";
|
|
|
|
fp << "phi\n";
|
|
for (q=phi.begin() ; q != phi.end() ; ++q) {
|
|
for (a = q->second.begin() ; a != q->second.end() ; ++a) {
|
|
for (s=a->second.begin() ; s != a->second.end() ; ++s) {
|
|
fp << q->first << " \t";
|
|
fp << a->first << " \t";
|
|
fp << s->first << " \t";
|
|
fp << s->second << "\n";
|
|
}
|
|
}
|
|
}
|
|
fp << ".\n";
|
|
|
|
return 0;
|
|
break;
|
|
|
|
case paalergia:
|
|
// =========== Format alergia !!! format avec perte d'information !!! ====
|
|
// =========== il faut travailler avec des PDFAs !!!!!!!!!! ==============
|
|
if (phi.find (0) == phi.end ())
|
|
throw - 3;
|
|
|
|
for (q = phi.begin (); q != phi.end (); ++q)
|
|
{
|
|
for (a = q->second.begin ();
|
|
a != q->second.end (); ++a)
|
|
{
|
|
for (s = a->second.begin ();
|
|
s != a->second.end (); ++s)
|
|
{
|
|
fp << q->first << " ";
|
|
fp << alph.find (a->first)->second;
|
|
fp << " " << s->first;
|
|
fp << " " << s->second << endl;
|
|
}
|
|
}
|
|
}
|
|
return 0;
|
|
break;
|
|
default:
|
|
throw - 4;
|
|
}
|
|
}
|
|
catch (int e)
|
|
{
|
|
if (PFA_VERBOSE)
|
|
{
|
|
cerr << "ERROR in MA::Save !!!!" << endl;
|
|
cerr << " \t";
|
|
switch (e)
|
|
{
|
|
case -3:
|
|
cerr << "There is no initial state" <<
|
|
endl;
|
|
case -4:
|
|
cerr << "unrecognized format : " <<
|
|
c_format << endl;
|
|
default:
|
|
cerr << "Erreur non prise en compte !" <<
|
|
endl;
|
|
}
|
|
}
|
|
return e;
|
|
}
|
|
catch (...)
|
|
{
|
|
if (PFA_VERBOSE)
|
|
{
|
|
cerr << "ERROR in MA::Save !!!" << endl;
|
|
cerr << "Unexpected error *!#@???" << endl;
|
|
}
|
|
return ERR (0);
|
|
}
|
|
}
|
|
|
|
// Sauvegarde le MA dans Filename
|
|
RESULT
|
|
MA::save (const char *Filename, const FormatSauvegarde c_format) const
|
|
{
|
|
try {
|
|
// On ouvre le fichier
|
|
if (Filename == NULL)
|
|
throw -1;
|
|
ofstream fp (Filename);
|
|
if (!fp.good ())
|
|
throw -2;
|
|
|
|
return MA::save(fp, c_format);
|
|
}
|
|
catch (int e) {
|
|
if (PFA_VERBOSE)
|
|
{
|
|
cerr << "ERROR in MA::Save !!!!" << endl;
|
|
cerr << " \t";
|
|
switch (e)
|
|
{
|
|
case -1:
|
|
cerr << "Filename == NULL !!!" << endl;
|
|
case -2:
|
|
cerr << "I can't open the file" <<
|
|
Filename << endl;
|
|
default:
|
|
cerr << "Erreur non prise en compte !" <<
|
|
endl;
|
|
}
|
|
}
|
|
return e;
|
|
}
|
|
}
|
|
|
|
// erase cleanly all transitions with parameter between minval and maxval
|
|
RESULT MA::erase_transitions (const double maxval, const double minval)
|
|
{
|
|
Graph::iterator q, qtmp;
|
|
LettreSFunc::iterator a, atmp;
|
|
SFunc::iterator s, stmp;
|
|
|
|
// erase for iota
|
|
for (s=iota.begin() ; s != iota.end() ; ) {
|
|
if ((s->second >= minval) && (s->second <= maxval)) {
|
|
stmp = s;
|
|
++stmp;
|
|
iota.erase (s);
|
|
s = stmp;
|
|
}
|
|
else {
|
|
++s;
|
|
}
|
|
}
|
|
|
|
// erase for tau
|
|
for (s=tau.begin() ; s != tau.end() ; ) {
|
|
if ((s->second >= minval)&& (s->second <= maxval)) {
|
|
stmp = s;
|
|
++stmp;
|
|
tau.erase (s);
|
|
s = stmp;
|
|
}
|
|
else {
|
|
++s;
|
|
}
|
|
}
|
|
|
|
// erase for transitions
|
|
for (q = phi.begin (); q != phi.end ();) {
|
|
for (a = q->second.begin (); a != q->second.end ();) {
|
|
for (s = a->second.begin (); s != a->second.end ();) {
|
|
if ((s->second >= minval) && (s->second <= maxval)) {
|
|
stmp = s;
|
|
++stmp;
|
|
a->second.erase (s);
|
|
s = stmp;
|
|
}
|
|
else {
|
|
++s;
|
|
}
|
|
}
|
|
if (a->second.empty ()) {
|
|
atmp = a;
|
|
++atmp;
|
|
q->second.erase (a);
|
|
a = atmp;
|
|
}
|
|
else {
|
|
++a;
|
|
}
|
|
}
|
|
if (q->second.empty ()) {
|
|
qtmp = q;
|
|
++qtmp;
|
|
phi.erase (q);
|
|
q = qtmp;
|
|
}
|
|
else {
|
|
++q;
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
|
|
// erase cleanly the transition phi(qbeg,l,qend)
|
|
RESULT MA::eraseTransition(const State qbeg, const Lettre l, const State qend) {
|
|
Graph::iterator q;
|
|
LettreSFunc::iterator a;
|
|
SFunc::iterator s;
|
|
|
|
q = phi.find(qbeg);
|
|
if (q != phi.end ())
|
|
{
|
|
a = q->second.find(l);
|
|
if (a != q->second.end ())
|
|
{
|
|
s = a->second.find(qend);
|
|
if (s != a->second.end ())
|
|
{
|
|
a->second.erase (s);
|
|
}
|
|
|
|
if (a->second.empty ())
|
|
{
|
|
q->second.erase (a);
|
|
}
|
|
}
|
|
if (q->second.empty ())
|
|
{
|
|
phi.erase (q);
|
|
}
|
|
}
|
|
return VAL(0);
|
|
}
|
|
|
|
|
|
// emmonde l'automate
|
|
RESULT MA::emmonde(void) {
|
|
// --- Explication de l'algorithme ------
|
|
// On fait un parcour en profondeur en notant tous les Ètats atteint en partant
|
|
// des sources (les Ètats initiaux)
|
|
// Puis on inverse le graphe et on refait un parcours en profondeur en partant
|
|
// des Ètats terminaux.
|
|
// Les Ètat atteignables par les Ètats initiaux et qui ne sont pas atteint
|
|
// par les Ètats terminaux du graphe inverse sont des Ètats ‡ supprimer.
|
|
// --- Fin de l'explication de l'algorithme ---
|
|
|
|
// d'abord le parcours inverse
|
|
// 1 - On crÈe le graphe inverse
|
|
Graph Inv; // The inverse graph
|
|
Graph::iterator q; // some state
|
|
LettreSFunc::iterator a; // some letter
|
|
SFunc::iterator s, r;
|
|
StateSet Qir; // set of states from which we can reach a terminal state
|
|
StateSet Q2; // set of reachable states
|
|
StateSet W; // set for algorithm
|
|
StateSet BadStates; // set of bad states
|
|
State etat_cour; // current state
|
|
|
|
// On inverse le graphe Inv(r,a,q) = phi (q,a,r)
|
|
for (q = phi.begin (); q != phi.end (); ++q)
|
|
{
|
|
for (a = q->second.begin (); a != q->second.end (); ++a)
|
|
{
|
|
for (s = a->second.begin (); s != a->second.end (); ++s)
|
|
{
|
|
Inv[s->first][a->first][q->first] = s->second;
|
|
}
|
|
}
|
|
}
|
|
|
|
// Pour chaque Ètat terminal, on regarde l'ensemble des Ètats que
|
|
// l'on atteint
|
|
for (r = tau.begin (); r != tau.end (); ++r)
|
|
{
|
|
W.insert (r->first);
|
|
Qir.insert (r->first);
|
|
}
|
|
|
|
while (!W.empty ())
|
|
{
|
|
etat_cour = *(W.begin ());
|
|
W.erase (W.begin ());
|
|
q = Inv.find (etat_cour);
|
|
if (q != Inv.end ())
|
|
{
|
|
for (a = q->second.begin (); a != q->second.end (); ++a)
|
|
{
|
|
for (s = a->second.begin (); s != a->second.end (); ++s)
|
|
{
|
|
if (Qir.find (s->first) == Qir.end ())
|
|
{
|
|
Qir.insert (s->first);
|
|
W.insert (s->first);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
// Qir contient tous les Ètats atteignables dans le graphe inverse
|
|
|
|
// Pour chaque Ètat initial on regarde si on tombe bien dans
|
|
// l'ensemble des Ètats qui atteignent un Ètat terminal.
|
|
W.clear() ; // inutile mais au cas o˘
|
|
for (r = iota.begin (); r != iota.end (); ++r)
|
|
{
|
|
W.insert (r->first);
|
|
Q2.insert (r->first);
|
|
}
|
|
|
|
while (!W.empty ())
|
|
{
|
|
etat_cour = *W.begin ();
|
|
W.erase (W.begin ());
|
|
q = phi.find (etat_cour);
|
|
if (q != phi.end ())
|
|
{
|
|
for (a = q->second.begin (); a != q->second.end (); ++a)
|
|
{
|
|
for (s = a->second.begin (); s != a->second.end (); ++s)
|
|
{
|
|
if (Q2.find (s->first) == Q2.end ())
|
|
{
|
|
Q2.insert (s->first);
|
|
W.insert (s->first);
|
|
}
|
|
|
|
if (Qir.find (s->first) == Qir.end ())
|
|
{
|
|
BadStates.insert (s->first);
|
|
}
|
|
|
|
}
|
|
}
|
|
}
|
|
}
|
|
// Q2 contient l'ensemble des Ètats atteignables
|
|
// BadStates contient l'ensemble des Ètats accessibles ‡ partir
|
|
// desquels on ne peut atteindre un Ètat non terminal
|
|
|
|
// Suppressions de tous les Ètats de BadStates
|
|
StateSet::iterator bs;
|
|
for (bs = BadStates.begin (); bs != BadStates.end (); ++bs)
|
|
{
|
|
erase (*bs);
|
|
}
|
|
|
|
// suppression des Ètats non accessibles
|
|
BadStates=Q;
|
|
for (bs = BadStates.begin() ; bs != BadStates.end() ; ++bs)
|
|
{
|
|
if (Q2.find(*bs) == Q2.end())
|
|
{
|
|
erase(*bs);
|
|
}
|
|
}
|
|
return VAL(0);
|
|
}
|
|
|
|
|
|
// Charge le MA de Filename
|
|
RESULT MA::load (const char *Filename)
|
|
{
|
|
try
|
|
{
|
|
// on modifie le ffa donc on perd l'attribution du ffa
|
|
if (Filename == NULL)
|
|
throw - 1;
|
|
ifstream fp (Filename);
|
|
if (!fp)
|
|
throw - 2;
|
|
fp.precision (30);
|
|
string buf;
|
|
char tmp[64];
|
|
char c;
|
|
bool finfichier;
|
|
State q, r, s;
|
|
Lettre a;
|
|
Dictionnaire::iterator l;
|
|
float proba;
|
|
|
|
vide (); // on vide le MA
|
|
fp >> buf;
|
|
if (buf == "%Alergia")
|
|
{ // ================= cas format alergia =============
|
|
while (fp.good ())
|
|
{ // jusqu'‡ la fin du fichier
|
|
fp >> q; // on lit l'Ètat de dÈpart
|
|
addState (q);
|
|
fp >> buf; // on lit la lettre de la transition
|
|
a = addLettre (buf);
|
|
fp >> r; // on lit l'Ètat d'arrivÈ
|
|
addState (r);
|
|
fp >> proba; // on lit la probabilitÈ de la transition
|
|
addTransition (q, a, r, proba);
|
|
}
|
|
|
|
// L'Ètat 0 est le seul Ètat initial
|
|
iota[0] = 1;
|
|
|
|
// On met ‡ jour tau
|
|
StateSet::const_iterator iq;
|
|
Graph::const_iterator ie;
|
|
LettreSFunc::const_iterator ia;
|
|
SFunc::const_iterator ir;
|
|
|
|
for (iq = Q.begin (); iq != Q.end (); ++iq)
|
|
{
|
|
proba = 0; // we use proba to make the sum
|
|
ie = phi.find (*iq);
|
|
if (ie != phi.end ())
|
|
{
|
|
for (ia = ie->second.begin ();
|
|
ia != ie->second.end (); ++ia)
|
|
{
|
|
for (ir = ia->second.begin ();
|
|
ir != ia->second.end ();
|
|
++ir)
|
|
{
|
|
proba += ir->second;
|
|
}
|
|
}
|
|
}
|
|
tau[*iq] = 1 - proba;
|
|
}
|
|
}
|
|
else if (buf == "%MDI")
|
|
{ // ========================== cas format MDI ==================
|
|
float f1, f2;
|
|
int numstates;
|
|
char cbuf[20];
|
|
while (fp.good()) {
|
|
if (*(buf.begin()) == '%') { // =========================== commentaire =====================
|
|
finfichier = ((fp >> c) == NULL);
|
|
while ((!finfichier) && (c != '\n'))
|
|
{
|
|
finfichier = ((fp.get (c)) == NULL);
|
|
}
|
|
finfichier = ((fp >> buf) == NULL);
|
|
}
|
|
else if (buf == "Name") {
|
|
getline(fp,name);
|
|
fp >> buf;
|
|
}
|
|
else if (buf == "NumStates") {
|
|
fp >> numstates;
|
|
for (int i=0 ; i< numstates ; ++i) {
|
|
addState(i);
|
|
}
|
|
fp >> buf;
|
|
}
|
|
else if (buf == "NumEdges") {
|
|
fp >> buf;
|
|
fp >> buf;
|
|
}
|
|
else if (buf == "State") {
|
|
fp >> q; // on lit l'etat courant
|
|
fp.getline(cbuf,20,'=');
|
|
buf = cbuf;
|
|
if (buf == " initial") {
|
|
fp >> iota[q];
|
|
fp.getline(cbuf,20,'=');
|
|
buf = cbuf;
|
|
}
|
|
if (buf == " final") {
|
|
fp >> f1;
|
|
fp.get(c);
|
|
fp >> f2;
|
|
tau[q]=f1/f2;
|
|
}
|
|
else {
|
|
cerr << "PARSE ERROR final : q=" << q << endl;
|
|
}
|
|
fp >> buf; // on recupere le %Ci=0.xxxxxxx
|
|
fp >> buf; // on recupere le numero de l'etat
|
|
// on commence a lire les transition sortantes
|
|
while ((buf != "State") && (fp.good())) {
|
|
fp >> s; // on lit l'etat d'arrive
|
|
fp >> buf; // on lit la lettre
|
|
// on efface les guillemets
|
|
buf.erase(buf.begin());
|
|
buf.erase(--buf.end());
|
|
fp.getline(cbuf,20,'=');
|
|
fp >> f1;
|
|
fp.get(c);
|
|
fp >> f2;
|
|
if (buf.empty()) {
|
|
tau[q]+=f1/f2;
|
|
}
|
|
else {
|
|
a=addLettre(buf);
|
|
addTransition(q,a,s,f1/f2);
|
|
//phi[q][a][s]=f1/f2;
|
|
}
|
|
fp >> buf; // on lit le %Ci=0.xxxxxxx
|
|
fp >> buf;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
else if (buf == "%OLDMA")
|
|
{ // ================= cas format ffa interne =============
|
|
while (fp.good ())
|
|
{ // Tand que l'on est pas ‡ la fin du fichier
|
|
if (*(buf.begin()) == '%')
|
|
{ // =========================== commentaire =====================
|
|
finfichier = ((fp >> c) == NULL);
|
|
while ((!finfichier) && (c != '\n'))
|
|
{
|
|
finfichier =
|
|
((fp.get (c)) ==
|
|
NULL);
|
|
}
|
|
finfichier = ((fp >> buf) == NULL);
|
|
}
|
|
// ============================== State ========================
|
|
else if (buf == "State")
|
|
{
|
|
// --------------- Lecture de la ligne initiale ----------------
|
|
fp >> q; // on lit l'Ètat de dÈpart
|
|
Q.insert (q); // on ajoute l'etat q
|
|
sprintf (tmp, "%d", q);
|
|
finfichier = ((fp >> buf) == NULL); // on lit la suite
|
|
while ((buf != "State")
|
|
&& (buf != tmp)
|
|
&& (!finfichier))
|
|
{
|
|
if (buf == "c")
|
|
{
|
|
fp >> buf; // on lit le =
|
|
fp >> buf; // on lit le chiffre mais on en fait rien
|
|
}
|
|
else if (buf == "i")
|
|
{ // on lit la probabilitÈ d'Ítre initial
|
|
fp >> buf; // on lit le =
|
|
fp >> proba; // on lit la probabilitÈ
|
|
if (proba != 0)
|
|
iota[q] =
|
|
proba;
|
|
}
|
|
else if (buf == "f")
|
|
{ // on lit la probabilitÈ d'Ítre terminal
|
|
fp >> buf; // on lit le =
|
|
fp >> proba; // on lit la probabilitÈ
|
|
if (proba != 1)
|
|
tau[q] = 1 -
|
|
proba;
|
|
}
|
|
finfichier = ((fp >> buf) == NULL); // on lit la suite
|
|
}
|
|
// ---------------- Lecture des transitions sortantes ----------------
|
|
r = q;
|
|
while ((buf != "State")
|
|
&& (!finfichier))
|
|
{
|
|
if (PFA_VERBOSE)
|
|
{
|
|
if (buf != tmp)
|
|
{
|
|
cerr << "load WARNING !" << endl;
|
|
cerr << "La premiËre lettre d'une colone ne correspond pas ‡ l'Ètat" << endl;
|
|
}
|
|
}
|
|
fp >> s; // on lit l'Ètat d'arrivÈ
|
|
fp >> buf; // on lit la lettre
|
|
|
|
a = addLettre(buf);
|
|
//~ // on cherche la lettre correspondante
|
|
//~ for (l = alph.begin ();
|
|
//~ (l != alph.end ())
|
|
//~ && (l->second != buf);
|
|
//~ l++)
|
|
//~ ;
|
|
//~ if (l == alph.end ())
|
|
//~ { // si on ne retrouve pas la lettre
|
|
//~ a = addLettre (); // on ajoute une lettre
|
|
//~ alph[a] = buf; // ‡ laquelle on fait correspondre la bonne chaine de caractËre
|
|
//~ }
|
|
//~ else // sinon
|
|
//~ a = l->first; // on attribu la lettre en cours.
|
|
|
|
fp >> buf; // on lit 'p'
|
|
fp >> buf; // on lit '='
|
|
fp >> proba; // on lit la proba de l'arÍte
|
|
|
|
phi[q][a][s] = proba; // on insËre l'arÍte
|
|
finfichier = ((fp >> buf) == NULL); // on lit la lettre suivante.
|
|
}
|
|
}
|
|
else
|
|
{ // Autres cas, on ne fait rien d'autre qu'avancer
|
|
fp >> buf;
|
|
}
|
|
}
|
|
{ // ================= cas format ffa interne =============
|
|
while (fp.good ())
|
|
{ // Tand que l'on est pas ‡ la fin du fichier
|
|
if (*(buf.begin()) == '%')
|
|
{ // =========================== commentaire =====================
|
|
finfichier = ((fp >> c) == NULL);
|
|
while ((!finfichier) && (c != '\n'))
|
|
{
|
|
finfichier =
|
|
((fp.get (c)) ==
|
|
NULL);
|
|
}
|
|
finfichier = ((fp >> buf) == NULL);
|
|
}
|
|
// ============================== State ========================
|
|
else if (buf == "State")
|
|
{
|
|
// --------------- Lecture de la ligne initiale ----------------
|
|
fp >> q; // on lit l'Ètat de dÈpart
|
|
Q.insert (q); // on ajoute l'etat q
|
|
sprintf (tmp, "%d", q);
|
|
finfichier = ((fp >> buf) == NULL); // on lit la suite
|
|
while ((buf != "State")
|
|
&& (buf != tmp)
|
|
&& (!finfichier))
|
|
{
|
|
if (buf == "c")
|
|
{
|
|
fp >> buf; // on lit le =
|
|
fp >> buf; // on lit le chiffre mais on en fait rien
|
|
}
|
|
else if (buf == "i")
|
|
{ // on lit la probabilitÈ d'Ítre initial
|
|
fp >> buf; // on lit le =
|
|
fp >> proba; // on lit la probabilitÈ
|
|
if (proba != 0)
|
|
iota[q] =
|
|
proba;
|
|
}
|
|
else if (buf == "f")
|
|
{ // on lit la probabilitÈ d'Ítre terminal
|
|
fp >> buf; // on lit le =
|
|
fp >> proba; // on lit la probabilitÈ
|
|
if (proba != 1)
|
|
tau[q] = 1 -
|
|
proba;
|
|
}
|
|
finfichier = ((fp >> buf) == NULL); // on lit la suite
|
|
}
|
|
// ---------------- Lecture des transitions sortantes ----------------
|
|
r = q;
|
|
while ((buf != "State")
|
|
&& (!finfichier))
|
|
{
|
|
if (PFA_VERBOSE)
|
|
{
|
|
if (buf != tmp)
|
|
{
|
|
cerr << "load WARNING !" << endl;
|
|
cerr << "La premiËre lettre d'une colone ne correspond pas ‡ l'Ètat" << endl;
|
|
}
|
|
}
|
|
fp >> s; // on lit l'Ètat d'arrivÈ
|
|
fp >> buf; // on lit la lettre
|
|
|
|
a = addLettre(buf);
|
|
//~ // on cherche la lettre correspondante
|
|
//~ for (l = alph.begin ();
|
|
//~ (l != alph.end ())
|
|
//~ && (l->second != buf);
|
|
//~ l++)
|
|
//~ ;
|
|
//~ if (l == alph.end ())
|
|
//~ { // si on ne retrouve pas la lettre
|
|
//~ a = addLettre (); // on ajoute une lettre
|
|
//~ alph[a] = buf; // ‡ laquelle on fait correspondre la bonne chaine de caractËre
|
|
//~ }
|
|
//~ else // sinon
|
|
//~ a = l->first; // on attribu la lettre en cours.
|
|
|
|
fp >> buf; // on lit 'p'
|
|
fp >> buf; // on lit '='
|
|
fp >> proba; // on lit la proba de l'arÍte
|
|
|
|
phi[q][a][s] = proba; // on insËre l'arÍte
|
|
finfichier = ((fp >> buf) == NULL); // on lit la lettre suivante.
|
|
}
|
|
}
|
|
else
|
|
{ // Autres cas, on ne fait rien d'autre qu'avancer
|
|
fp >> buf;
|
|
}
|
|
}
|
|
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
|
|
|
|
else {
|
|
stringstream str;
|
|
Lettre a;
|
|
TrueLettre b;
|
|
while (fp.good ())
|
|
{ // Tand que l'on est pas ‡ la fin du fichier
|
|
if (*(buf.begin()) == '%')
|
|
{ // =========================== commentaire =====================
|
|
fp.get(c);
|
|
while ((fp.good()) && (c != '\n')) {
|
|
fp.get (c);
|
|
}
|
|
fp >> buf;
|
|
}
|
|
else if (buf == "name") {
|
|
fp.get(c);
|
|
name+=c;
|
|
while ((fp.good()) && (c != '\n')) {
|
|
fp.get (c);
|
|
name+=c;
|
|
}
|
|
fp >> buf;
|
|
}
|
|
else if (buf == "alph")
|
|
{ // dictionnaire
|
|
fp >> buf;
|
|
while ((buf != ".") && (fp.good())) {
|
|
if (*(buf.begin()) == '%')
|
|
{ // --- commentaire ---
|
|
fp.get(c);
|
|
while ((fp.good()) && (c != '\n')) {
|
|
fp.get (c);
|
|
}
|
|
fp >> buf;
|
|
}
|
|
str << buf;
|
|
str >> a;
|
|
fp >> b;
|
|
Sigma.insert(a);
|
|
alph[a]=b;
|
|
fp >> buf;
|
|
}
|
|
fp >> buf;
|
|
}
|
|
else if (buf == "iota")
|
|
{ // iota
|
|
fp >> buf;
|
|
while ((buf != ".") && (fp.good())) {
|
|
|
|
if (*(buf.begin()) == '%')
|
|
{ // --- commentaire ---
|
|
fp.get(c);
|
|
while ((fp.good()) && (c != '\n')) {
|
|
fp.get (c);
|
|
}
|
|
fp >> buf;
|
|
}
|
|
|
|
q=atoi(buf.c_str());
|
|
fp >> proba;
|
|
Q.insert(q);
|
|
iota[q]=proba;
|
|
fp >> buf;
|
|
}
|
|
fp >> buf;
|
|
}
|
|
else if (buf == "tau")
|
|
{ // iota
|
|
fp >> buf;
|
|
while ((buf != ".") && (fp.good())) {
|
|
|
|
if (*(buf.begin()) == '%')
|
|
{ // --- commentaire ---
|
|
fp.get(c);
|
|
while ((fp.good()) && (c != '\n')) {
|
|
fp.get (c);
|
|
}
|
|
fp >> buf;
|
|
}
|
|
|
|
q=atoi(buf.c_str());
|
|
fp >> proba;
|
|
Q.insert(q);
|
|
tau[q]=proba;
|
|
fp >> buf;
|
|
}
|
|
fp >> buf;
|
|
}
|
|
else if (buf == "phi") {
|
|
fp >> buf;
|
|
while ((buf != ".") && (fp.good())) {
|
|
|
|
if (*(buf.begin()) == '%')
|
|
{ // --- commentaire ---
|
|
fp.get(c);
|
|
while ((fp.good()) && (c != '\n')) {
|
|
fp.get (c);
|
|
}
|
|
fp >> buf;
|
|
}
|
|
|
|
q=atoi(buf.c_str());
|
|
fp >> a;
|
|
fp >> s;
|
|
fp >> proba;
|
|
|
|
if (alph.find(a) == alph.end()) {
|
|
cerr << "!!! Lettre : " << a << endl;
|
|
throw -3;
|
|
}
|
|
|
|
Q.insert(q);
|
|
Q.insert(s);
|
|
phi[q][a][s]=proba;
|
|
|
|
fp >> buf;
|
|
}
|
|
fp >> buf;
|
|
}
|
|
else
|
|
{ // Autres cas, on ne fait rien d'autre qu'avancer
|
|
fp >> buf;
|
|
}
|
|
}
|
|
}
|
|
return VAL(0);
|
|
}
|
|
catch (int erreur)
|
|
{
|
|
if (PFA_VERBOSE)
|
|
{
|
|
cerr << "MA::load" << endl;
|
|
switch (erreur)
|
|
{
|
|
case -1:
|
|
cerr << "ERROR in MA::Save !!!!" << endl;
|
|
cerr << " \tFilename == NULL !!!" << endl;
|
|
break;
|
|
case -2:
|
|
cerr << "Erreur lors de l'ouverture du fichier : " << Filename << endl;
|
|
break;
|
|
case -3:
|
|
cerr << "Erreur alph n'est pas bien defini, des lettres manques !" << endl;
|
|
default:
|
|
cerr << "Erreur inconnue ?" << endl;
|
|
}
|
|
}
|
|
return erreur;
|
|
}
|
|
catch (...)
|
|
{
|
|
if (PFA_VERBOSE)
|
|
{
|
|
cout << "MA::load(" << Filename << ")" << endl;
|
|
cout << "Erreur inexplicable ?" << endl;
|
|
}
|
|
return ERR (0);
|
|
}
|
|
}
|
|
|
|
|
|
/// ----------------------- Modifieurs -------------------------------
|
|
|
|
// Fonction qui ajoute une transition
|
|
RESULT MA::addTransition (const Transition & t, const float val)
|
|
{
|
|
if (PFA_SAFE)
|
|
{
|
|
assert (Q.find (t.qdep) != Q.end ());
|
|
assert (Sigma.find (t.a) != Sigma.end ());
|
|
assert (Q.find (t.qarr) != Q.end ());
|
|
}
|
|
|
|
if (val != 0)
|
|
{
|
|
phi[t.qdep][t.a][t.qarr] = val;
|
|
}
|
|
else {
|
|
Graph::const_iterator q;
|
|
q = phi.find(t.qdep);
|
|
if ( q != phi.end()) {
|
|
LettreSFunc::const_iterator a = q->second.find(t.a);
|
|
if (a != q->second.end()) {
|
|
SFunc::const_iterator s = a->second.find(t.qarr);
|
|
if (s != a->second.end()) {
|
|
phi[t.qdep][t.a][t.qarr] = val;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (PFA_SAFE)
|
|
{
|
|
assert (coherent ());
|
|
}
|
|
return VAL (0);
|
|
}
|
|
|
|
|
|
// Ajout une lettre par defaut ‡ l'alphabet
|
|
Lettre MA::addLettre (void)
|
|
{
|
|
Lettre
|
|
a;
|
|
if (!Sigma.empty ())
|
|
{
|
|
a = *(--(Sigma.end ())) + 1;
|
|
}
|
|
else
|
|
{
|
|
a = 'a';
|
|
}
|
|
|
|
Sigma.insert (a);
|
|
alph[a] = a;
|
|
return a;
|
|
}
|
|
|
|
// Ajout de la lettre buf
|
|
Lettre MA::addLettre (const TrueLettre & buf)
|
|
{
|
|
// search whether buf is a new letter
|
|
Lettre a;
|
|
Dictionnaire::iterator l;
|
|
for (l = alph.begin (); (l != alph.end ()) && (l->second != buf); ++l)
|
|
;
|
|
if (l == alph.end ())
|
|
{ // if buf is new then
|
|
a = addLettre (); // we add the letter
|
|
alph[a] = buf; // and we associate it with buf
|
|
}
|
|
else {
|
|
a = l->first;
|
|
}
|
|
return a;
|
|
}
|
|
|
|
|
|
// Ajoute un Ètat
|
|
State MA::addNewState (const float init, const float term)
|
|
{
|
|
State q;
|
|
if (!Q.empty ())
|
|
{
|
|
q = *(--Q.end()) + 1;
|
|
while (Q.find(q) != Q.end())
|
|
++q;
|
|
}
|
|
else
|
|
{
|
|
q = 1;
|
|
}
|
|
addState(q,init,term);
|
|
return q;
|
|
}
|
|
|
|
|
|
// Ajoute l'Ètat q s'il n'existe pas
|
|
State MA::addState (const State q, const float init, const float term)
|
|
{
|
|
if (Q.find (q) == Q.end ())
|
|
{
|
|
Q.insert (q);
|
|
}
|
|
if (init != 0)
|
|
iota[q]=init;
|
|
if (term != 0)
|
|
tau[q]=term;
|
|
return q;
|
|
if (PFA_SAFE)
|
|
assert(coherent());
|
|
}
|
|
|
|
|
|
// Ajout d'une transition
|
|
RESULT MA::addTransition (const State qdep, const Lettre a, const State qarr, const float val)
|
|
{
|
|
if (PFA_SAFE)
|
|
{
|
|
assert (Q.find (qdep) != Q.end ());
|
|
assert (Sigma.find (a) != Sigma.end ());
|
|
assert (Q.find (qarr) != Q.end ());
|
|
}
|
|
if (val != 0)
|
|
{
|
|
phi[qdep][a][qarr] = val;
|
|
}
|
|
|
|
if (PFA_SAFE)
|
|
{
|
|
assert (coherent ());
|
|
}
|
|
return VAL (0);
|
|
}
|
|
|
|
// Cree un MA aleatoire
|
|
RESULT MA::becomeRandom (const int nb_etats, const int nb_lettres,
|
|
const int num_graphe, const float densite,
|
|
const float prob_init, const float prob_term,
|
|
const float min_trans, const float max_trans)
|
|
{
|
|
float init, term;
|
|
int i;
|
|
StateSet::const_iterator q, s;
|
|
Alphabet::const_iterator a;
|
|
|
|
// on vide le MA
|
|
vide ();
|
|
// on initialise la variable aleatoire
|
|
if (num_graphe != 0)
|
|
srand (num_graphe);
|
|
|
|
// on ajoute les états
|
|
for (i = 0; i < nb_etats; i++)
|
|
{
|
|
if (random () < prob_init)
|
|
init = random (min_trans, max_trans);
|
|
else
|
|
init = 0;
|
|
|
|
if (random () < prob_term)
|
|
term = random (min_trans, max_trans);
|
|
else
|
|
term = 0;
|
|
|
|
addNewState (init, term);
|
|
}
|
|
|
|
// on ajoute les lettres
|
|
for (i = 0; i < nb_lettres; i++)
|
|
{
|
|
addLettre ();
|
|
}
|
|
|
|
// on cree les transitions avec des distributions uniformes
|
|
for (q = Q.begin (); q != Q.end (); q++)
|
|
{ // pour tous les Ètats
|
|
for (a = Sigma.begin (); a != Sigma.end (); a++)
|
|
{
|
|
for (s = Q.begin (); s != Q.end (); s++)
|
|
{
|
|
if (random () < densite)
|
|
{ // si on tire un nombre inferieur ‡ la densitÈ, on cree une arete
|
|
phi[*q][*a][*s] =
|
|
random (min_trans, max_trans);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return VAL (0);
|
|
}
|
|
|
|
// Cree un MA aleatoire
|
|
RESULT MA::becomeRandomMax (const int nb_etats, const int nb_lettres,
|
|
const int num_graphe, const int nb_succ,
|
|
const int nb_init, const int nb_term,
|
|
const float min_trans, const float max_trans)
|
|
{
|
|
int i;
|
|
StateSet::const_iterator q, s;
|
|
Alphabet::const_iterator a;
|
|
|
|
// on vide le MA
|
|
vide ();
|
|
// on initialise la variable aleatoire
|
|
if (num_graphe != 0)
|
|
srand (num_graphe);
|
|
|
|
// on ajoute les Ètats
|
|
for (i = 0; i < nb_etats; ++i)
|
|
{
|
|
addState(i,0,0);
|
|
}
|
|
|
|
// on ajoute les lettres
|
|
for (i = 0; i < nb_lettres; i++)
|
|
{
|
|
addLettre ();
|
|
}
|
|
|
|
for (i=0 ; i< nb_init ; ++i)
|
|
{
|
|
iota[rand()%nb_etats]=random(min_trans,max_trans);
|
|
}
|
|
|
|
for (i=0 ; i<nb_term ; ++i)
|
|
{
|
|
tau[rand() % nb_etats]= random(min_trans,max_trans);
|
|
}
|
|
|
|
// on cree les transitions avec des distributions uniformes
|
|
for (q = Q.begin (); q != Q.end (); ++q)
|
|
{ // pour tous les Ètats
|
|
for (a = Sigma.begin (); a != Sigma.end (); ++a)
|
|
{
|
|
for (i=0 ; i<nb_succ ; ++i)
|
|
{
|
|
phi[*q][*a][rand()%nb_etats] = random (min_trans, max_trans);
|
|
}
|
|
}
|
|
}
|
|
return VAL (0);
|
|
}
|
|
|
|
|
|
RESULT MA::renormalize_state(const State q, const float normalization, const float min_tau, const float max_tau, const float min, const float max) {
|
|
const int ERR_INPUT=-1023;
|
|
if (min_tau > max_tau) {
|
|
cerr << "MA::renormalize_state : ";
|
|
cerr << "min_tau > max_tau" << endl;
|
|
throw ERR_INPUT;
|
|
}
|
|
if (min > max) {
|
|
cerr << "MA::renormalize_state : ";
|
|
cerr << "min > max" << endl;
|
|
throw ERR_INPUT;
|
|
}
|
|
|
|
Graph::iterator r;
|
|
LettreSFunc::iterator a;
|
|
SFunc::iterator s;
|
|
float sum, x;
|
|
bool taumodif=true;
|
|
sum=tau[q];
|
|
r=phi.find(q);
|
|
if (r != phi.end()) {
|
|
for (a=r->second.begin() ; a != r->second.end() ; a++) {
|
|
for (s=a->second.begin() ; s!=a->second.end() ; s++) {
|
|
sum+=s->second;
|
|
}
|
|
}
|
|
}
|
|
bool good=false;
|
|
StateSet BadStates;
|
|
while ( !good ) {
|
|
good=true;
|
|
x=normalization/sum;
|
|
if (tau[q]*x > max_tau) {
|
|
tau[q]=max_tau;
|
|
if (taumodif) {
|
|
taumodif=false;
|
|
good=false;
|
|
}
|
|
} else if (tau[q]*x < min_tau) {
|
|
tau[q]=min_tau;
|
|
if (taumodif) {
|
|
taumodif=false;
|
|
good=false;
|
|
}
|
|
} else {
|
|
tau[q]=x*tau[q];
|
|
}
|
|
sum=tau[q];
|
|
if (r != phi.end()) {
|
|
for (a=r->second.begin() ; a != r->second.end() ; a++) {
|
|
for (s=a->second.begin() ; s!=a->second.end() ; s++) {
|
|
if (x*s->second > max) {
|
|
s->second = max;
|
|
if (BadStates.find(s->first) == BadStates.end()) {
|
|
BadStates.insert(s->first);
|
|
good=false;
|
|
}
|
|
}
|
|
else if (x*s->second < min) {
|
|
s->second=min;
|
|
if (BadStates.find(s->first) == BadStates.end()) {
|
|
BadStates.insert(s->first);
|
|
good=false;
|
|
}
|
|
}
|
|
else {
|
|
s->second=x*s->second;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return VAL(0);
|
|
}
|
|
|
|
// Cree un MA aleatoire avec le maximum de controle
|
|
// nb_etats : number of states of the MA
|
|
// nb_lettres : number of letters of the alphabet of the MA
|
|
// num_graphe : if different of 0, the same number gives always the same MA
|
|
// max_nb_init : the maximal number of initial states
|
|
// max_nb_succ : the maximal number of successors by states-letter
|
|
// max_nb_term : the maximal number of terminal states
|
|
// min_trans : minimal value of transitions
|
|
// max_trans : maximal value of transitions
|
|
// min_iota : minimal value for iota(q)
|
|
// max_iota : maximal value for iota(q)
|
|
// min_tau : minimal value for tau(q)
|
|
// max_tau : maximal value for tau(q)
|
|
// nomalize : if different of 0, normalize sum of iota and sum of tau + successor transitions
|
|
RESULT MA::becomeRandomControl (const int nb_etats,
|
|
const int nb_lettres,
|
|
const int num_graphe,
|
|
const int max_nb_succ,
|
|
const int max_nb_init,
|
|
const int max_nb_term,
|
|
const float min_trans,
|
|
const float max_trans,
|
|
const float min_iota,
|
|
const float max_iota,
|
|
const float min_tau,
|
|
const float max_tau,
|
|
const float normalization,
|
|
const float prob_init,
|
|
const float prob_trans,
|
|
const float prob_term)
|
|
{
|
|
|
|
int i;
|
|
StateSet::const_iterator q, s;
|
|
SFunc::iterator r;
|
|
Alphabet::const_iterator a;
|
|
|
|
const int ERR_INPUT=-1023;
|
|
if (min_iota > max_iota) {
|
|
cerr << "min_iota > max_iota !!!" << endl;
|
|
throw ERR_INPUT;
|
|
}
|
|
if (min_trans > max_trans) {
|
|
cerr << "min_trans > max_trans !!!" << endl;
|
|
throw ERR_INPUT;
|
|
}
|
|
if (min_tau > max_tau) {
|
|
cerr << "min_tau > max_tau !!!" << endl;
|
|
throw ERR_INPUT;
|
|
}
|
|
|
|
// on vide le MA
|
|
vide ();
|
|
// on initialise la variable aleatoire
|
|
if (num_graphe != 0)
|
|
srand (num_graphe);
|
|
|
|
// on ajoute les Ètats
|
|
for (i = 0; i < nb_etats; i++)
|
|
{
|
|
addState(i,0,0);
|
|
}
|
|
|
|
// on ajoute les lettres
|
|
for (i = 0; i < nb_lettres; i++) {
|
|
addLettre ();
|
|
}
|
|
|
|
/// --- iota ---
|
|
i=0;
|
|
for (i=0 ; i<max_nb_init ; i++) {
|
|
if (float(rand())/RAND_MAX < prob_init) {
|
|
iota[rand()%nb_etats]=random(min_iota, max_iota);
|
|
}
|
|
}
|
|
// en mode normalization
|
|
if (normalization != 0) {
|
|
/// renormalization
|
|
// calculus of the sum of iota
|
|
float sum;
|
|
for (sum=0, r=iota.begin() ; r != iota.end() ; r++) {
|
|
sum+=r->second;
|
|
}
|
|
float x;
|
|
bool good=false;
|
|
StateSet BadStates;
|
|
while ( !good ) {
|
|
x=normalization/sum;
|
|
good=true;
|
|
for (r=iota.begin() ; r != iota.end() ; r++) {
|
|
if (x * r->second > max_iota) {
|
|
sum+=r->second=max_iota;
|
|
if (BadStates.find(r->first) == BadStates.end()) {
|
|
BadStates.insert(r->first);
|
|
good=false;
|
|
}
|
|
}
|
|
else if (x * r->second < min_iota) {
|
|
sum+=r->second=min_iota;
|
|
if (BadStates.find(r->first) == BadStates.end()) {
|
|
BadStates.insert(r->first);
|
|
good=false;
|
|
}
|
|
}
|
|
else {
|
|
sum+=r->second = x*r->second;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/// --- Tau + Transitions ---
|
|
i=0;
|
|
for (i=0 ; i<max_nb_term ; i++) {
|
|
if (float(rand())/RAND_MAX < prob_term) {
|
|
tau[rand()%nb_etats]=random(min_tau, max_tau);
|
|
}
|
|
}
|
|
|
|
// on cree les transitions avec des distributions uniformes
|
|
for (q = Q.begin (); q != Q.end (); ++q)
|
|
{ // pour tous les Ètats
|
|
for (a = Sigma.begin (); a != Sigma.end (); ++a)
|
|
{
|
|
for (i=0 ; i<max_nb_succ ; ++i)
|
|
{
|
|
if (float(rand())/RAND_MAX < prob_trans) {
|
|
phi[*q][*a][rand()%nb_etats] = random (min_trans, max_trans);
|
|
}
|
|
}
|
|
}
|
|
if (normalization != 0) {
|
|
renormalize_state(*q,normalization,min_tau, max_tau, min_trans,max_trans);
|
|
}
|
|
}
|
|
return VAL (0);
|
|
}
|
|
|
|
|
|
RESULT MA::becomeRandomPrefix (const int nb_etats,
|
|
const int nb_lettres,
|
|
const int num_graphe,
|
|
const float densite,
|
|
const float prob_init,
|
|
const float prob_term,
|
|
const float min_trans,
|
|
const float max_trans)
|
|
{
|
|
float
|
|
term;
|
|
int
|
|
i;
|
|
StateSet
|
|
R,
|
|
S; // l'ensemble des Ètats restants
|
|
StateSet::const_iterator q, s;
|
|
Alphabet::const_iterator a;
|
|
|
|
// on vide le MA
|
|
vide ();
|
|
// on initialise la variable aleatoire
|
|
if (num_graphe != 0)
|
|
srand (num_graphe);
|
|
|
|
// on ajoute les Ètats
|
|
for (i = 0; i < nb_etats; i++)
|
|
{
|
|
if (random () < prob_term)
|
|
term = random (min_trans, max_trans);
|
|
else
|
|
term = 0;
|
|
addState (0, term);
|
|
}
|
|
// on ajoute l'unique Ètat terminal
|
|
iota[*Q.begin ()] = random (min_trans, max_trans);
|
|
|
|
R = Q;
|
|
S.clear (); // on initialise R et S
|
|
|
|
// on ajoute les lettres
|
|
for (i = 0; i < nb_lettres; i++)
|
|
{
|
|
addLettre ();
|
|
}
|
|
|
|
// on supprime l'Ètat correspondant ‡ epsilon de R et on l'ajoute ‡ S
|
|
R.erase (R.begin ());
|
|
S.insert (*Q.begin ());
|
|
// on cree les transitions avec des distributions uniformes
|
|
for (q = Q.begin (); q != Q.end (); q++)
|
|
{ // pour tous les Ètats
|
|
for (a = Sigma.begin (); a != Sigma.end (); a++)
|
|
{
|
|
if ((random () < densite) || (R.empty ()))
|
|
{ // on rabat les arÍtes sur les Ètats dÈja affectÈs
|
|
for (s = S.begin (); s != S.end (); s++)
|
|
{
|
|
if (random () < densite)
|
|
{ // si on tire un nombre inferieur ‡ la densitÈ, on cree une arete
|
|
phi[*q][*a][*s] =
|
|
random (min_trans,
|
|
max_trans);
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
s = R.begin ();
|
|
R.erase (s);
|
|
S.insert (*s);
|
|
phi[*q][*a][*s] =
|
|
random (min_trans, max_trans);
|
|
}
|
|
}
|
|
}
|
|
|
|
return VAL (0);
|
|
}
|
|
|
|
/// --------------------- Methodes ------------------------------
|
|
void MA::normaliseVecteur(SFunc &V) const {
|
|
SFunc::iterator q;
|
|
double sum;
|
|
sum = 0;
|
|
for (q=V.begin() ; q != V.end() ; q++) {
|
|
sum += q->second>0?q->second:-q->second;
|
|
}
|
|
sum = 1/sum;
|
|
for (q=V.begin() ; q != V.end() ; q++) {
|
|
q->second *= sum;
|
|
if (q->second == 0) {
|
|
V.erase(q);
|
|
}
|
|
}
|
|
// // Affichage de debogage
|
|
// cout << "\tMA::normaliseVecteur\n";
|
|
// for (q=V.begin() ; q != V.end() ; q++) {
|
|
// cout << "\tV[" << q->first << "]=" << q->second << endl;
|
|
// }
|
|
// cout << "\t---\n";
|
|
}
|
|
|
|
|
|
// genere un mot en fonction du modèle. En particulier, il faut récupérer
|
|
// la valeur des P_q(\Se) pour tous les états q.
|
|
// Description de l'algorithme :
|
|
// Soit r un langage rationnel, on construit P_r de la façon suivante ;
|
|
// Neg(u)=\sum_{x \in \Sigma}r(ux\Se)<0?r(ux\Se):0 + r(u)<0?r(u):0
|
|
// P_r(ux\Se) = r(ux\Se)/Neg(u) si r(a\Se)>0 et 0 sinon
|
|
// P_r(\eps) = r(\eps)/Neg(u)
|
|
|
|
RESULT MA::genere_mot(Word &w, const bool safe){
|
|
// Dans un premier temps, on rÈcupËre les valeurs des
|
|
// P_q(\Se)
|
|
SFunc PSe; // contiendra la valeur des P_q(\Se)
|
|
|
|
if (val_PSe(PSe) != VAL(0)) {
|
|
if ( safe ) {
|
|
return ERR(0);
|
|
}
|
|
}
|
|
|
|
// on a w donnÈ, on calcule P(w), P(wx\Se) pour tout x et on conserve
|
|
// les w^-1P(\eps) et w^-1P(x\Se) positifs
|
|
w=""; // le mot courant initialisÈ ‡ epsilon
|
|
Lettre c; // la lettre courante
|
|
bool termine=false;
|
|
double Negw, Posw;
|
|
Alphabet::const_iterator x;
|
|
SFunc V, Vtmp;
|
|
SFunc::const_iterator q;
|
|
LettreSFunc::const_iterator a;
|
|
SFunc::const_iterator s;
|
|
Graph::const_iterator r;
|
|
map<Lettre,double> px; // va contenir px[0] = P(w), px[1] = P(wx_1\Se), ... , px[n] = P(wx_n\Se)
|
|
map<Lettre,double>::const_iterator l;
|
|
bool lettreTrouve;
|
|
double val;
|
|
double sum;
|
|
|
|
V = iota;
|
|
|
|
while (!termine) {
|
|
// normaliser le vecteur V, fait en sorte de mettre
|
|
// la somme de ses valeurs ‡ 1 et supprimes les entrÈes
|
|
// nulles (qui sont inutiles)
|
|
normaliseVecteur(V);
|
|
Negw=0; Posw=0;
|
|
// calcul de w^-1P(\eps)
|
|
px[0] = 0;
|
|
for (q = V.begin() ; q != V.end() ; q++) {
|
|
px[0]+= q->second * val_tau(q->first);
|
|
}
|
|
// on met ‡ jour Neg(w) et Pos(w)
|
|
if (px[0] < 0)
|
|
Negw += px[0];
|
|
else
|
|
Posw += px[0];
|
|
|
|
// // AFFICHAGE DEBUG
|
|
// cout << "px[.]:" << endl;
|
|
// for (l=px.begin() ; l != px.end() ; l++) {
|
|
// cout << "px[";
|
|
// cout << l->first==0?'0':l->first;
|
|
// cout << "]=";
|
|
// cout << l->second << endl;
|
|
// }
|
|
// cout << "Negw=" << Negw << ", Posw=" << Posw << endl;
|
|
// cout << " -- px[.]" << endl;
|
|
// // END AFFICHAGE DEBUG
|
|
|
|
// initialisation de px
|
|
for (x=Sigma.begin() ; x != Sigma.end() ; x++)
|
|
px[*x]=0;
|
|
// calcul de w^-1P(x\Se)
|
|
for (q = V.begin() ; q != V.end() ; q++) {
|
|
r=phi.find(q->first);
|
|
if (r != phi.end()) {
|
|
for (a=r->second.begin() ; a != r->second.end() ; a++) {
|
|
for (s=a->second.begin() ; s != a->second.end() ; s++) {
|
|
// // AFFICHAGE DEBUG
|
|
// cout << "\t\t**********" << endl;
|
|
// cout << "q->first=" << q->first << endl;
|
|
// cout << "q->second=" << q->second << endl;
|
|
// cout << "r->first=" << r->first << endl;
|
|
// cout << "a->first=" << a->first << endl;
|
|
// cout << "s->first=" << s->first << endl;
|
|
// cout << "s->second=" << s->second << endl;
|
|
// cout << "PSe[s->first]=" << PSe[s->first] << endl;
|
|
// cout << "\t\t**********" << endl;
|
|
// // FIN AFFICHAGE DEBUG
|
|
px[a->first] += q->second * s->second * PSe[s->first];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
for (x=Sigma.begin() ; x != Sigma.end() ; x++) {
|
|
// mise ‡ jour de Neg(w) et Pos(w)
|
|
if (px[*x] < 0)
|
|
Negw += px[*x];
|
|
else
|
|
Posw += px[*x];
|
|
}
|
|
|
|
// // AFFICHAGE DEBUG
|
|
// cout << "px[.]: " << endl;
|
|
// for (l=px.begin() ; l != px.end() ; l++) {
|
|
// cout << "px[";
|
|
// cout << l->first==0?'0':l->first ;
|
|
// cout << "]=";
|
|
// cout << l->second ;
|
|
// cout << endl;
|
|
// }
|
|
// cout << "Negw=" << Negw << ", Posw=" << Posw << endl;
|
|
// cout << " -- px[.]" << endl;
|
|
// // END AFFICHAGE DEBUG
|
|
|
|
// on a fini de calculer les valeurs possibles. On choisit seulement
|
|
// parmis les valeurs positives
|
|
if (Posw == 0) {
|
|
cerr << "ERREUR !!! MA::genere_mot" << endl;
|
|
cerr << "prefixe = ";
|
|
cerr << affiche(w) << endl;
|
|
cerr << "Impossible d'utiliser cette methode avec ce prefixe dans ce MA" << endl;
|
|
cerr << "Pos(\\epsilon)=0 !!!" << endl;
|
|
throw ERR(21);
|
|
}
|
|
val = random(0,Posw);
|
|
sum = 0;
|
|
lettreTrouve=false;
|
|
for (l=px.begin() ; l != px.end() && !lettreTrouve ; l++) {
|
|
// // AFFICHAGE DE DEBUG
|
|
// cout << "\tval=" << val;
|
|
// cout << ", sum=" << sum;
|
|
// cout << ", Posw=" << Posw;
|
|
// cout << ", Negw=" << Negw;
|
|
// cout << "\tpx[";
|
|
// cout << l->first==0?'0':l->first;
|
|
// cout << "]=";
|
|
// cout << l->second << endl;
|
|
// // AFFICHAGE DE DEBUG
|
|
if (l->second > 0) {
|
|
sum+= l->second;
|
|
if (sum >= val) {
|
|
if (l->first != 0) {
|
|
c = l->first;
|
|
w += c;
|
|
// // AFFICHAGE DEBUG
|
|
// cout << "c=";
|
|
// cout << c;
|
|
// cout << ", w=" ;
|
|
// cout << affiche(w);
|
|
// cout << endl;
|
|
// // AFFICHAGE DEBUG
|
|
}
|
|
else {
|
|
termine=true;
|
|
// // AFFICHAGE DEBUG
|
|
// cout << "termine" << endl ;
|
|
// // AFFICHAGE DEBUG
|
|
}
|
|
lettreTrouve=true;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (!termine) {
|
|
Vtmp.clear();
|
|
// Mise ‡ jour du vecteur d'initialisation
|
|
for (q=V.begin() ; q != V.end() ; q++) {
|
|
r=phi.find(q->first);
|
|
if (r != phi.end()) {
|
|
a = r->second.find(c);
|
|
if (a != r->second.end()) {
|
|
for (s=a->second.begin() ; s != a->second.end() ; s++) {
|
|
Vtmp[s->first] += q->second * s->second;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
V = Vtmp;
|
|
}
|
|
}
|
|
return VAL(0);
|
|
}
|
|
|
|
// genere un Èchantillon de mots
|
|
RESULT MA::genere_echantillon ( int taille,
|
|
Sample & S,
|
|
const int num_echantillon)
|
|
{
|
|
int i;
|
|
Word w;
|
|
if (num_echantillon != 0)
|
|
{
|
|
srand (num_echantillon);
|
|
}
|
|
|
|
S = Sample (Sigma, alph, false);
|
|
for (i = 0; i < taille; i++)
|
|
{
|
|
genere_mot (w, false);
|
|
S.insert (w);
|
|
}
|
|
return VAL (0);
|
|
}
|
|
|
|
// genere un Èchantillon de mots : l'echantillon reste identique si lot est identique
|
|
RESULT MA::genere_echantillon (const int taille,
|
|
Sample & S,
|
|
const char *Filename,
|
|
const int num_echantillon)
|
|
{
|
|
if (PFA_DEBUG)
|
|
{
|
|
if (Filename == NULL)
|
|
{
|
|
cerr << " PFA::echantillon(int taille, char *Filename) : Filename = NULL !!!" << endl;
|
|
}
|
|
}
|
|
genere_echantillon (taille, S, num_echantillon);
|
|
return S.save (Filename);
|
|
}
|
|
|
|
|
|
// Calcule les valeurs de P_q(\S_e) pour
|
|
// tous les Ètats q
|
|
RESULT MA::val_PSe(SFunc &PSe) const {
|
|
Simplex simplex;
|
|
StateSet::const_iterator q,r;
|
|
Alphabet::const_iterator a;
|
|
int j;
|
|
float tmp;
|
|
|
|
simplex.set_number_of_unknown_to(Q.size());
|
|
|
|
for (q=Q.begin() ; q != Q.end() ; q++) {
|
|
simplex.setval(-val_tau(*q));
|
|
for (r=Q.begin(), j=1 ; r != Q.end() ; r++, j++) {
|
|
if (*r == *q) {
|
|
tmp=-1;
|
|
}
|
|
else {
|
|
tmp=0;
|
|
}
|
|
for (a=Sigma.begin() ; a != Sigma.end() ; a++) {
|
|
tmp += val_phi(*q,*a,*r);
|
|
}
|
|
simplex.setparam(j,tmp);
|
|
}
|
|
simplex.add_equality_constraint();
|
|
}
|
|
|
|
simplex.set_mode(realNotBounded); // on utilise des réels pouvant êtres négatifs
|
|
|
|
float epsilon;
|
|
if (! simplex.has_solution(PSe,epsilon) ) {
|
|
PSe.clear();
|
|
simplex.affiche();
|
|
cerr << "ERREUR INEXPLICABLE !!!!\n";
|
|
cerr << "Le système d'équation doit être mal posé !\n";
|
|
throw ERR(0);
|
|
} else {
|
|
return VAL(0);
|
|
}
|
|
}
|
|
|
|
/// --------------------- Testeurs ------------------------------
|
|
|
|
// Teste la cohÈrence de la structure de donnÈe.
|
|
bool MA::coherent (void) const
|
|
{
|
|
bool
|
|
res = true;
|
|
// on cherche une transition contenant un Ètat n'appartenant pas
|
|
// ‡ l'ensemble des Ètats.
|
|
Graph::const_iterator q;
|
|
LettreSFunc::const_iterator a;
|
|
SFunc::const_iterator s;
|
|
for (q = phi.begin (); q != phi.end (); ++q)
|
|
{
|
|
for (a = q->second.begin (); a != q->second.end (); ++a)
|
|
{
|
|
for (s = a->second.begin (); s != a->second.end (); ++s)
|
|
{
|
|
if ( (Q.find(q->first) == Q.end ())
|
|
|| (Q.find (s->first) == Q.end ()))
|
|
{
|
|
res = false;
|
|
if (PFA_VERBOSE)
|
|
{
|
|
cerr << "Erreur de coherence (phi) : (";
|
|
cerr << q->first << "," << a->first << ",";
|
|
cerr << s->first << ") = " << s->second << " !!! " << endl;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return res;
|
|
}
|
|
|
|
// Teste si le MA est coherent et est un SPFA. valeur de iota, tau et phi dans [0,1]
|
|
bool MA::isSPFA (void) const
|
|
{
|
|
|
|
if (!coherent ())
|
|
{ // si le ffa n'est pas coherent
|
|
return false;
|
|
}
|
|
// si le ffa est coherent
|
|
// Test de iota
|
|
SFunc::const_iterator s;
|
|
float sum = 0;
|
|
// cerr.precision(30);
|
|
for (s = iota.begin (); s != iota.end (); ++s)
|
|
{
|
|
if ((s->second < 0) || (s->second > 1))
|
|
{
|
|
//~ cerr << "iota " << s->first << "<0 ou >1 !!! : " << s->second << endl;
|
|
return false;
|
|
}
|
|
sum += s->second;
|
|
}
|
|
if (!simeqone (sum))
|
|
{
|
|
return false;
|
|
}
|
|
//cerr << "iota OK" << endl;
|
|
|
|
// Test de tau
|
|
for (s = tau.begin (); s != tau.end (); ++s)
|
|
{
|
|
if ((s->second < 0) || (s->second > 1))
|
|
{
|
|
//~ cerr << "tau " << s->first << "<0 ou >1 : " << s->second << endl;
|
|
return false;
|
|
}
|
|
}
|
|
|
|
// Test of phi and
|
|
// of the property : \forall q \in Q and \forall a \in \Sigma
|
|
// tau(q) + \sum_{s\in Q} phi(q,a,s)=1
|
|
Graph::const_iterator q;
|
|
LettreSFunc::const_iterator a;
|
|
for (q = phi.begin (); q != phi.end (); ++q)
|
|
{
|
|
sum = val_tau (q->first);
|
|
for (a = q->second.begin (); a != q->second.end (); ++a)
|
|
{
|
|
for (s = a->second.begin (); s != a->second.end (); ++s)
|
|
{
|
|
if ((s->second < 0) || (s->second > 1))
|
|
{
|
|
//~ cerr << "phi(" << q->first << ",";
|
|
//~ cerr << a->first << ",";
|
|
//~ cerr << s->first << ")=";
|
|
//~ cerr << s->second << " FALSE !!!" << endl;
|
|
return false;
|
|
}
|
|
//cerr << "phi(" << q->first << "," << a->first << "," << s->first << ")=" << s->second << endl;
|
|
//cerr << "sum = " << sum << endl;
|
|
sum += s->second;
|
|
}
|
|
}
|
|
if (!simeqone (sum))
|
|
{
|
|
//cerr << "phi(" << q->first << ",*,*)=" << sum << " FALSE !!!" << endl;
|
|
return false;
|
|
}
|
|
}
|
|
// on a passÈ toutes les Èpreuves
|
|
return true;
|
|
}
|
|
|
|
// Fonction qui rend le MA vide (pas d'Ètats pas de lettre)
|
|
void
|
|
MA::vide ()
|
|
{
|
|
name.clear ();
|
|
Q.clear ();
|
|
Sigma.clear ();
|
|
iota.clear ();
|
|
tau.clear ();
|
|
phi.clear ();
|
|
alph.clear ();
|
|
}
|
|
|
|
// renvoi vrai si le MA est un PFA
|
|
bool MA::isPFA () const
|
|
{
|
|
if (!isSPFA ())
|
|
return false;
|
|
|
|
// --- Explication de l'algorithme ------
|
|
// On fait un parcour en profondeur en notant tous les Ètats atteint en partant
|
|
// des sources (les Ètats initiaux)
|
|
// Puis on inverse le graphe et on refait un parcours en profondeur en partant
|
|
// des Ètats terminaux.
|
|
// Si l'ensemble des Ètats atteint par les Ètats terminaux dans le graphe
|
|
// inverse contient l'ensemble des Ètats atteint en partant des Ètats initiaux
|
|
// alors le SPFA considÈrÈ est un PFA.
|
|
// --- Fin de l'explication de l'algorithme ---
|
|
|
|
// d'abord le parcours inverse
|
|
// 1 - On crÈe le graphe inverse
|
|
Graph
|
|
Inv;
|
|
Graph::const_iterator q;
|
|
LettreSFunc::const_iterator a;
|
|
SFunc::const_iterator s, r;
|
|
StateSet
|
|
Qir,
|
|
Q2,
|
|
W;
|
|
State
|
|
etat_cour;
|
|
|
|
// On inverse le graphe Inv(r,a,q) = phi (q,a,r)
|
|
|
|
for (q = phi.begin (); q != phi.end (); q++)
|
|
{
|
|
for (a = (q->second).begin (); a != (q->second).end (); a++)
|
|
{
|
|
for (s = (a->second).begin ();
|
|
s != (a->second).end (); s++)
|
|
{
|
|
Inv[s->first][a->first][q->first] = s->second;
|
|
}
|
|
}
|
|
}
|
|
|
|
// Pour chaque Ètat terminal, on regarde l'ensemble des Ètats que
|
|
// l'on atteint
|
|
for (r = tau.begin (); r != tau.end (); r++)
|
|
{
|
|
W.insert (r->first);
|
|
Qir.insert (r->first);
|
|
}
|
|
|
|
while (!W.empty ())
|
|
{
|
|
etat_cour = *(W.begin ());
|
|
W.erase (W.begin ());
|
|
q = Inv.find (etat_cour);
|
|
if (q != Inv.end ())
|
|
{
|
|
for (a = (q->second).begin ();
|
|
a != (q->second).end (); a++)
|
|
{
|
|
for (s = (a->second).begin ();
|
|
s != (a->second).end (); s++)
|
|
{
|
|
if (Qir.find (s->first) == Qir.end ())
|
|
{
|
|
Qir.insert (s->first);
|
|
W.insert (s->first);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// Pour chaque Ètat initial on regarde si on tombe bien dans
|
|
// l'ensemble des Ètats qui atteignent un Ètat terminal.
|
|
for (r = iota.begin (); r != iota.end (); ++r)
|
|
{
|
|
W.insert (r->first);
|
|
Q2.insert (r->first);
|
|
}
|
|
|
|
while (!W.empty ())
|
|
{
|
|
etat_cour = *W.begin ();
|
|
W.erase (W.begin ());
|
|
q = phi.find (etat_cour);
|
|
if (q != phi.end ())
|
|
{
|
|
for (a = (q->second).begin ();
|
|
a != (q->second).end (); ++a)
|
|
{
|
|
for (s = (a->second).begin ();
|
|
s != (a->second).end (); ++s)
|
|
{
|
|
if (Q2.find (a->first) == Q2.end ())
|
|
{
|
|
Q2.insert (a->first);
|
|
W.insert (a->first);
|
|
}
|
|
if (Qir.find (s->first) == Qir.end ())
|
|
{
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
|
|
string MA::affiche (const Word & w) const
|
|
{
|
|
Word::const_iterator a;
|
|
string res;
|
|
Dictionnaire::const_iterator x;
|
|
for (a = w.begin() ; a != w.end () ; ++a)
|
|
{
|
|
x=alph.find(*a);
|
|
if (x == alph.end()) {
|
|
res = "Dictionnaire ERROR ";
|
|
res += *a;
|
|
return res;
|
|
}
|
|
res += x->second;
|
|
res += ' ';
|
|
}
|
|
return res;
|
|
}
|
|
|
|
void MA::next (Word & w) const
|
|
{
|
|
Word::reverse_iterator ll; // last letter
|
|
Word::iterator z;
|
|
Lettre a;
|
|
Lettre first = *Sigma.begin ();
|
|
int i;
|
|
int level = w.size ();
|
|
bool end = false;
|
|
while ((w.size () > 0) && (!end))
|
|
{
|
|
ll = w.rbegin ();
|
|
a = *ll;
|
|
++a;
|
|
if (Sigma.find (a) != Sigma.end ())
|
|
{
|
|
++(*ll);
|
|
end = true;
|
|
}
|
|
else
|
|
{
|
|
z=w.end();
|
|
--z;
|
|
w.erase(z); // w.pop_back ();
|
|
}
|
|
}
|
|
if (!end)
|
|
++level;
|
|
for (i = w.size (); i < level; ++i)
|
|
{
|
|
w += first; // w.push_back (first);
|
|
}
|
|
|
|
}
|
|
|
|
|
|
// erase the state badstate and all transitions from and to it
|
|
RESULT MA::erase (State badstate)
|
|
{
|
|
Graph::iterator q, qtmp;
|
|
LettreSFunc::iterator a, atmp;
|
|
SFunc::iterator s, stmp;
|
|
StateSet::iterator r;
|
|
|
|
// Suppression dans l'ensemble d'Ètats
|
|
r=Q.find (badstate);
|
|
if ( r == Q.end () )
|
|
{
|
|
cerr << "MA::erase (State badstate) : demande de suppression d'un etat inexistant" << endl;
|
|
exit (-1);
|
|
}
|
|
Q.erase (r);
|
|
// Suppression dans iota
|
|
s = iota.find(badstate);
|
|
if (s != iota.end ())
|
|
iota.erase (s);
|
|
// Suppression dans tau
|
|
s = tau.find(badstate);
|
|
if (s != tau.end ())
|
|
tau.erase (s);
|
|
// Suppression dans phi
|
|
if (phi.find (badstate) != phi.end ())
|
|
phi.erase (phi.find (badstate));
|
|
|
|
for (q = phi.begin (); q != phi.end ();)
|
|
{
|
|
for (a = q->second.begin (); a != q->second.end ();)
|
|
{
|
|
for (s = a->second.begin (); s != a->second.end ();)
|
|
{
|
|
if (s->first == badstate)
|
|
{
|
|
stmp = s;
|
|
++stmp;
|
|
a->second.erase (s);
|
|
s = stmp;
|
|
}
|
|
else
|
|
++s;
|
|
}
|
|
if (a->second.empty ())
|
|
{
|
|
atmp = a;
|
|
++atmp;
|
|
q->second.erase (a);
|
|
a = atmp;
|
|
}
|
|
else
|
|
++a;
|
|
}
|
|
if (q->second.empty ())
|
|
{
|
|
qtmp = q;
|
|
++qtmp;
|
|
phi.erase (q);
|
|
q = qtmp;
|
|
}
|
|
else
|
|
++q;
|
|
}
|
|
|
|
return VAL (0);
|
|
}
|
|
|
|
StateSet MA::delta (const State q, const Word &w) const
|
|
{
|
|
StateSet R;
|
|
R.insert(q);
|
|
return delta(R,w);
|
|
}
|
|
|
|
StateSet MA::delta (const StateSet &R, const Word &w) const
|
|
{
|
|
StateSet V; // le vecteur correspondant aux Ètats atteints
|
|
StateSet X; // un vecteur temporaire
|
|
StateSet::iterator xi;
|
|
Graph::const_iterator q;
|
|
LettreSFunc::const_iterator b;
|
|
SFunc::const_iterator r;
|
|
Word::const_iterator a;
|
|
|
|
//~ cout << endl;
|
|
V=R;
|
|
for (a=w.begin() ;a != w.end() ; a++)
|
|
{
|
|
X.clear();
|
|
for (xi=V.begin() ; xi != V.end() ; ++xi)
|
|
{
|
|
q=phi.find(*xi);
|
|
if (q != phi.end())
|
|
{
|
|
b=q->second.find(*a);
|
|
if (b != q->second.end())
|
|
{
|
|
for (r = b->second.begin() ; r != b->second.end() ; ++r)
|
|
{
|
|
X.insert(r->first);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
V=X;
|
|
}
|
|
return V;
|
|
}
|
|
|
|
|
|
void MA::allTransitions(TransitionFunction &T) const {
|
|
T.clear();
|
|
Graph::const_iterator q;
|
|
LettreSFunc::const_iterator a;
|
|
SFunc::const_iterator r;
|
|
Transition t;
|
|
for (q=phi.begin() ; q != phi.end() ; ++q) {
|
|
t.qdep= q->first;
|
|
for (a=q->second.begin() ; a!=q->second.end() ; ++a) {
|
|
t.a=a->first;
|
|
for (r=a->second.begin() ; r != a->second.end() ; ++r) {
|
|
t.qarr=r->first;
|
|
T[t]=0;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void MA::allStates(SFunc &S) const {
|
|
StateSet::const_iterator q;
|
|
S.clear();
|
|
for (q=Q.begin() ; q!=Q.end() ;++q) {
|
|
S[*q]=0;
|
|
}
|
|
}
|
|
|
|
// Become the MA with maximum number of transitions
|
|
RESULT MA::becomeComplete (const int nb_etats, const int nb_lettres) {
|
|
clear();
|
|
float valinit = 1/ float(nb_etats);
|
|
float val = 1/float(nb_etats + 1);
|
|
int i;
|
|
|
|
for (i=0 ; i<nb_lettres ; i++) {
|
|
addLettre();
|
|
}
|
|
|
|
for (i=0 ; i<nb_etats ; i++) {
|
|
addNewState(valinit, val);
|
|
}
|
|
|
|
StateSet::const_iterator q1,q2;
|
|
Alphabet::const_iterator a;
|
|
|
|
for (q1=Q.begin() ; q1 != Q.end() ; q1++) {
|
|
for (a=Sigma.begin() ; a != Sigma.end() ; a++) {
|
|
for (q2=Q.begin() ; q2 != Q.end() ; q2++) {
|
|
addTransition(*q1,*a,*q2,val);
|
|
}
|
|
}
|
|
}
|
|
return VAL(0);
|
|
}
|