Construire le graphe d’accessibilité

1. Deux graphes à ne pas confondre

Le réseau de Pétri contient des places et des transitions. Son graphe d’accessibilité contient des marquages complets comme sommets ; chaque arc correspond au franchissement d’une transition. Un sommet de ce second graphe n’est donc pas une place du premier.

Pour une demande et un agent, les trois sommets sont M₀ = (1,1,0,0), M₁ = (0,0,1,0) et M₂ = (0,1,0,1). Deux arcs les relient : Commencer, puis Terminer. Le dernier sommet n’a pas de sortie.

2. Une exploration en largeur

1. Inscrire le marquage initial dans une file et dans l’ensemble des états déjà découverts.
2. Retirer le premier marquage de la file et examiner toutes les transitions.
3. Pour chaque transition activable, calculer le successeur et conserver l’arc étiqueté.
4. Si ce successeur est nouveau, l’ajouter à la file ; sinon, réutiliser son sommet.
5. Continuer jusqu’à ce que la file soit vide.

Conserver aussi les arcs vers un état déjà connu est essentiel : ce sont notamment eux qui révèlent les cycles. Le marquage doit être mémorisé comme un vecteur immuable afin de servir de clé fiable.

3. Fusionner les chemins équivalents

Le modèle A/B possède cinq états et cinq arcs. Les deux chemins A,B et B,A arrivent au même sommet (0,0,1,1,0). Le dupliquer produirait un arbre de chemins au lieu du graphe de marquages recherché.

Une exploration en largeur fournit aussi un chemin de longueur minimale en nombre de franchissements vers un état découvert. Cela ne signifie pas un temps réel minimal, puisque les transitions du cours ne possèdent pas de durées.

4. Connaître la limite de l’énumération

Un réseau borné avec un nombre fini de places possède un ensemble fini de marquages accessibles. L’exploration complète s’arrête alors. Si une place peut croître sans limite, le graphe peut être infini et la file ne se videra jamais.

Le programme Python fourni arrête volontairement l’exploration au-delà d’une limite et signale exploration incomplète. Atteindre cette limite ne prouve ni la bornitude ni la non-bornitude. À l’inverse, lorsqu’il termine sans limite atteinte, ses états et arcs constituent le graphe exact du modèle d’entrée.

Télécharger l’analyseur Python complet et les modèles. Lancer python analyse.py avec Python 3.10 ou ultérieur ; aucune bibliothèque externe n’est nécessaire.

Trois exercices corrigés