MMSTD_gen

I - INTRODUCTION

Cet outil est destiné aux calculs des patterns valides selon la notation MMSTD.

Il a été écrit rapidement en Python. Il est relativement primaire et peut aisément être étendu au besoin.
Pour l'utiliser vous n'aurez normalement pas besoin d'appréhender ce langage.
Cet outil utilise un algorithme d'exploration des descendances pour trouver les patterns valides.
Son fonctionnement est simple: pour un noeud donné, il parcourt la descendance de ce noeud, fils par fils jusqu'à tomber sur une condition d'arrêt.

Les conditions d'arrêt paramétrables sont :

• Le nombre de passages maximum par Etat : Vous pouvez fixer cette valeur à :

• 1: Le fait de fixer cette valeur à 1 n'empêche pas la découverte d'un pattern dont noeud terminal et noeud initial sont identiques mais impose simplement de ne passer qu'une seule fois par les autres états. Il permet ainsi de générer l'ensemble des patterns unitaires.
• 2 pour autoriser 2 passages par le même état.
• X (X>2) pour autoriser X passages par le même état et même X-2 passages par l'état initial/terminal au sein du pattern. Ainsi par exemple, pour trouver le pattern Du Gillson's Mess ( Ul -o-> Lr -+-> Ul -o-> Ur -o-> Rl -+-> Ur -o-> Ul), vous devrez le fixer à 3 si vous commencez de l'état UL ou à 2 simplement si vous commencez de l'état Lr.
• La longueur du pattern : Fixez cette valeur à -1 pour ne pas limiter l'exploration par la longueur du pattern. Dans ce cas là, si votre paramètre du nombre de passages maximum par état est trop important (>=3) vous risquez de ne pas avoir de condition d'arrêt suffisante; le problème devient infini ;-(.

II - Utiliser MMSTD_GEN

Il vous faut au minimum un interpréteur python ainsi que mmstd_gen.py bien sûr. Ensuite un prompt intéractif vous sera donné à la suite d'une simple commande du style:

A partir de cet instant vous pouvez commencer à entrer des fonctions de l'interpréteur Python ou celles décrites ci-après autour de la notation MMSTD. 
Vous pouvez utiliser dès à présent le mécanisme de complétion de Python pour afficher les différentes commandes valides.

Ce mécanisme est activé par une simple pression sur la touche TAB.

III - Représentations du graphe MMSTD, des transitions

Il est bien que vous ayez une idée sur le type Python du diagramme MMSTD.
Si ainsi, vous considerez des transitions invalides, vous pourrez les supprimer ou même en ajouter de nouvelles.
Le diagramme sera représenté par un dictionnaire d'états.
Les clés seront les états et les valeurs la liste des transitions sans l'état de départ (puisqu'on le connaît), partant de cet état.

Une transition sera un tuple ( Etat source, Etat destination, Type d'échange ). un pattern sera représenté par une liste de transitions.

IV - Les différentes fonctions possibles

1 - Génération de tous les patterns à partir d'un Etat donné : gen_patterns_from_state()

## Nom : gen_pattern_from_state (state, cpt, path_len_max)
##
## But : Donne l'ensemble des patterns valides pour un état donné avec pour contraintes :
## - cpt : Nombre de passages maximum par état autorisé.
## - path_len_max : longueur maximum du pattern. -1 pour n'importe quelle longueur.
##
## Paramètres :
## - state : L'état dont on veut générer les patterns.
## - cpt : Nombre de passages maximum par état autorisé.
## - path_len_max : longueur maximum du pattern. -1 pour n'importe quelle longueur.
##

Si vous voulez en récupérer un affichage formaté utilisez print_patterns_from_state

2 - Génération de tous les patterns possibles pour les états : gen_all_patterns_from_states()

##
## Nom : gen_all_patterns_from_states (cpt, path_len_max)
##
## But : Donne tous les patterns disponibles pour le diagramme MMSTD en partant
## des différents états avec pour contraintes :
## - cpt : Nombre de passages maximum par état autorisé.
## - path_len_max : longueur maximum du pattern. -1 pour n'importe quelle longueur.
##
## Paramètres :
## - cpt : Nombre de passages maximum par état autorisé.
## - path_len_max : longueur maximum du pattern. -1 pour n'importe quelle longueur.
##
## Retour : Une liste de pattern pour une ensemble d'états.
## L'ensemble d'états est un dictionnaire. Chaque clé est un état,
## chaque valeur est une liste de transitions valides selon le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type) .
##

Si vous voulez en récupérer un affichage formaté utilisez print_patterns_from_state_list

3 - Génération de tous les patterns possibles : gen_all_patterns()

Cette fonction est très proche de la précédente, avec la différence que cette fois-ci les redondances sont supprimées.

##
## Nom : gen_all_patterns (cpt, path_len_max)
##
## But : Donne tous les patterns disponibles pour le diagramme MMSTD avec pour contraintes :
## - cpt : Nombre de passages maximum par état autorisé.
## - path_len_max : longueur maximum du pattern. -1 pour n'importe quelle longueur.
## Contrairement à gen_all_pattern_from_states, ici les doublons et les patterns équivalents sont omis.
##
## Paramètres :
## - cpt : Nombre de passages maximum par état autorisé.
## - path_len_max : longueur maximum du pattern. -1 pour n'importe quelle longueur.
##
## Retour : Une liste de pattern pour une ensemble d'états.
## L'ensemble d'états est un dictionnaire. Chaque clé est un état,
## chaque valeur est une liste de transitions valides selon le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type) .
##

Si vous voulez en récupérer un affichage formaté utilisez print_patterns_from_list

4 - Affichage d'un pattern : print_pattern()

##
## Nom : print_pattern (pattern):
##
## But : Affichage d'un pattern.
##
## Paramètres :
## - pattern : un pattern.
## Un pattern est une liste de transitions valides selon le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type) .
##
## Retour : Non
##

5 - Affichage des patterns d'une liste de patterns : print_patterns_from_list()

## Nom : print_patterns_from_list (patterns_list)
##
## But : Affiche les patterns d'une liste de patterns
##
## Paramètres :
## - patterns_list : Une liste de patterns.
## Chaque pattern est une liste de transitions valides selon le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type).
##
## Retour : Non
##

6 - Affichage d'une liste de patterns pour un ensemble d'états : print_patterns_from_state_list()

## Nom : print_patterns_from_state_list (state_list)
##
## But : Afficher une liste de patterns pour un ensemble d'états.
##
## Paramètres :
## - state_list : une liste de patterns pour un ensemble d'états.
## L'ensemble d'états est un dictionnaire. Chaque clé est un état,
## chaque valeur est une liste de transitions valides selon le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type).
##
## Retour : Non
##

7 - Time Reversed Pattern d'un pattern donné : reverse_pattern()

##
## Nom : reverse_pattern (pattern)
##
## But : donne le Time Reversed pattern d'un pattern donné.
##
## Paramètre :
## - pattern : le pattern à inverser.
## Un pattern est une liste de transitions naturelles telles que définies par le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type).
##
## Retour : le pattern Time Reversed.
##

8 - Validité d'un pattern selon le diagramme MMSTD : is_pattern_valid()

##
## Nom : is_pattern_valid (pattern)
##
## But : Vérifie la validité d'un pattern selon le diagramme MMSTD.
##
## Paramètre :
## - pattern : le pattern à vérifier.
## Un pattern est une liste de transitions naturelles telles que définies par le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type).
##
## Retour : un couple (bool, transitions list)
## bool vaudra True si le pattern est valide selon le diagramme MMSTD;
## False sinon. S'il vaut False, la transitions list donnera les transitions invalides utilisées.
##

9 - Vérification de l'équivalence de deux patterns au sens MMSTD : is_equivalent()

##
## Nom : is_equivalent (pattern1, pattern2)
##
## But : Vérifie l'équivalence de deux patterns selon le graph MMSTD.
##
## Paramètres :
## - pattern1, pattern2 : les deux patterns à comparer.
## Un pattern est une liste de transitions naturelles telles que définies par le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type).
##
## Retour : un boolean
## True si les patterns sont équivalents selon le graph MMSTD;
## False sinon.
##

10 - Affichage du nom d'un pattern : print_name()

##
## Nom : print_name (pattern)
##
## But : Affiche le nom d'un pattern donné
##
## Paramètre :
## - pattern : Le pattern dont on veut obtenir le nom
## Un pattern est une liste de transitions naturelles telles que définies par le diagramme MMSTD.
## Une transition est un tuple (State src, State dst, exchange type).
##
## Retour : Aucun
##