Développement d'une bibliothèque Java pour la manipulation ...deptinfo.unice.fr/twiki/pub/Minfo05/DepotDesRapports/Rapport_TER... · Comme on peut le voir sur l'exemple (Fig 1.1),

Université de Nice-Sophia Antipolis Master Informatique

Développement d'une bibliothèque Java

pour la manipulation graphique d'automates

étudiantsFlorent BICHE

Yann DAMERON

Max DUCA

Dimitre KOSTOV

EncadrantMme Laurence PIERRE

2005�2006

Table des matières

1 Introduction 2

2 Le Problème du dessin d'automates 5

2.1 Classi�cation des algorithmes - Applications . . . . . . . . . . . . . . . . . . . . . . 52.1.1 Straight line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1.2 Graphes hiérarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.3 Graphes Orthogonaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.4 Circulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1.5 Algorithme des ressorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Quelques Outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2.1 GraphViz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2.2 The Vaucanson Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2.3 Virtual Automator Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Organisation et calendrier prévisionnel 13

3.1 Organisation en groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Diagramme de Gant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Algorithme de placement 15

4.1 Algorithme de Fruchterman et Reingold . . . . . . . . . . . . . . . . . . . . . . . . 154.1.1 Fonctions d'attraction et de répulsion . . . . . . . . . . . . . . . . . . . . . 17

4.2 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5 Conception Graphique 21

5.1 Adaptation du diagramme de classes . . . . . . . . . . . . . . . . . . . . . . . . . . 215.1.1 AutomatonGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.1.2 StateGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.1.3 TransitionGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.1.4 ParserXMLGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.2 Dessin des composants de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.2.1 Représentation d'un état . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.2.2 Représentation d'une transition . . . . . . . . . . . . . . . . . . . . . . . . . 235.2.3 A�chage des étiquettes de transitions . . . . . . . . . . . . . . . . . . . . . 25

5.3 Edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.3.1 Création/Edition des états . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.3.2 Création/édition des transitions . . . . . . . . . . . . . . . . . . . . . . . . 265.3.3 Déplacement d'un objet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.3.4 Paramétrage des couleurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.3.5 Choix des algorithmes de placement . . . . . . . . . . . . . . . . . . . . . . 28

5.4 Sauvegarde/restauration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.4.1 Sauvegarde XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.4.2 Restauration XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2

5.4.3 Sauvegarde et Restauration par sérialisation . . . . . . . . . . . . . . . . . 305.4.4 Sauvegarde de l'image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

6 Conclusion 31

7 Annexe 33

7.1 Format de la DTD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337.2 Diagramme de Classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347.3 Tableaux comparatifs des applications . . . . . . . . . . . . . . . . . . . . . . . . . 35

8 Bibliographie 38

1

Chapitre 1

Introduction

Ce TER se place dans le cadre du développement en cours d'un environnement d'aide à laconception de systèmes matériels spéci�és à un haut niveau d'abstraction (comportemental). Cetenvironnement, appelé PepperMint, doit intégrer des outils pour la spéci�cation, la simulation etla véri�cation formelle.

Les systèmes y sont spéci�és par des automates dont les états sont nommés et les transitionssont étiquetées comme suit : condition / a�ectation(s). Les conditions et les a�ectations fontintervenir les entrées et sorties du système, ainsi que des éléments de mémorisation.

Fig. 1.1 � Exemple d'automate à représenter

Comme on peut le voir sur l'exemple (Fig 1.1), les variables din, xi et yi sont les entrées dusystème ; dout et res sont les sorties et x, y, a, b sont des éléments de mémorisation. Par exemple,la transition de S2 a S3 est conditionnée par x = y et les a�ectations e�ectuées sur cette transitionsont res ← x et dout ← true.

L'objectif de notre TER est de développer une bibliothèque Java à partir d'une applicationexistante appellée PepperMint, pour créer et représenter graphiquement des automates d'une cen-taine d'états, les sauvegarder et les restaurer, mais aussi pour déplacer les états et les transitions.Le problème du dessin des automates s'apparente à celui de la représentation des graphes. Ene�et, ce problème concerne la minimisation des croisements de transitions. Il fallait choisir judi-cieusement d'une part, la position des états à l'écran et d'autre part les courbes dé�nissant lestransitions a�n de minimiser ces croisements. C'est pourquoi nous avons e�ectué un travail de

2

recherche sur les di�érents algorithmes existant comme nous l'expliquerons dans le Chapitre 2.

Ces algorithmes étant complexes, un groupe s'est chargé d'implémenter celui qui est le mieuxadapté à nos contraintes pendant que l'autre groupe s'est chargé de réaliser une bibliothèque gra-phique par dessus l'application existante. La répartition des taches sera abordée dans le Chapitre 3.

L'application existante possède déjà un format d'entrée textuel (XML), le parseur existantParseXML génère une représentation de l'automate en Java : objet Automaton (Fig 1.2)

Le sujet nous demandait de ne pas modi�er le code existant, nous avons donc tiré parti dulanguage objet Java en utilisant l'héritage.Sur le schéma (Fig 1.3) on peut voir le fonctionnement de notre application. Nous pouvons partird'un �chier Xml que l'on parse, à l'aide de ParseXMLGraph qui hérite du parseur existant, pourobtenir un objet AutomatonGraph.

A partir de cet objet nous devons placer les états pour représenter l'automate en respectantdes contraintes d'esthétisme. Ceci correspond à la partie Placement de l'automate que nous dé-taillerons dans le chapitre 4.

C'est également cet objet qui nous permettra de modi�er l'automate, en lui ajoutant des étatset des transitions, ou en modi�ant ceux déja existant. C'est la partie éditeur de notre application,elle sera expliquée dans le chapitre 5.

3

Fig. 1.2 � Vue partielle de l'existant

Fig. 1.3 � Fonctionnement prévu de notre application

4

Chapitre 2

Le Problème du dessin d'automates

Le problème du dessin de graphes ou d'automates consiste à placer de manière automatique lessommets d'un graphe donné et à déterminer la forme de chaque arête en respectant des contraintesd'esthétisme.Pour cela il faut éviter que les états se chevauchent, mais aussi les placer de façon à minimiser lenombre d'intersections entre les arêtes.

Ce problème a conduit à de nombreux algorithmes dont nous allons donner un bref aperçudans la suite.

2.1 Classi�cation des algorithmes - Applications

Dans ce domaine, nous pouvons observer divers algorithmes liés à des applications di�érentes[3] :

2.1.1 Straight line

Cet algorithme permet de dessiner des graphes avec les arêtes représentées par des lignesdroites. Le résultat obtenu est un graphe planaire qui ne comporte pas d'intersections entre lesarêtes.On peut retrouver cette représentation par exemple dans le problème du plus court chemin.Nous n'avons pas retenu cet algorithme car il ne permet pas de représenter des graphes comportantdes boucles, ni d'avoir plusieurs transitions entre deux états car avec cette représentation lestransitions se trouveraient superposées (Fig 2.1).

Fig. 2.1 � Exemple de représentation de l'algorithme : Straight line

5

2.1.2 Graphes hiérarchiques

L'approche hiérarchique est une manière d'organiser la représentation de graphes orientés sousforme de couches [4]. On introduit pour le graphe une fonction qui associe à chaque sommet unentier, appelé couche associée au sommet. Cet ensemble de couches permet de mettre en évidenceune hiérarchie dans le graphe.A�n de mettre en évidence cette hiérarchie, on placera tous les sommets d'une même couche aumême niveau.Les graphes hiérarchiques ont de nombreuses utilisations telles que les diagrammes de classe oula représentation d'arbres généalogiques. Cet algorithme nous a semblé très intéressant, car ilmanipule également des graphes orientés. Cependant nous n'avons pas pu l'utiliser car il empêcheles rebouclages (Fig 2.2).

Fig. 2.2 � Exemple de représentation de l'algorithme : Graphes hiérarchiques

2.1.3 Graphes Orthogonaux

Ce type de représentation permet de relier les sommets d'un graphe à l'aide de séquences de seg-ments horizontaux et verticaux. Il existe de nombreuses applications utilisant cette représentation(diagrammes UML, organigramme...). Ceci à donné naissance à une nouvelle classe d'algorithmes,permettant de générer automatiquement ces graphes orthogonaux. Nous n'avons pas envisagéd'utiliser cet algortithme car il ne s'applique qu'à des graphes non orientés et ne permet pas dereboucler sur des états (Fig 2.3).

Fig. 2.3 � Exemple de représentation de l'algorithme : Graphes Orthogonaux

6

2.1.4 Circulaire

C'est l'algorithme auquel nous avons pensé en premier pendant la phase d'analyse de ce TERcar il a l'avantage d'être relativement simple à implémenter.L'idée est la suivante : on récupère le nombre d'états de l'automate et on dessine les états de façon"circulaire", c'est à dire que si il y a n états on obtient un polygone à n cotés.A�n que les états ne soient pas collés les uns aux autres, on dé�nit le rayon du cercle proportion-nellement au nombre d'états.Une fois que le rayon est dé�ni, on dessine les états un par un en e�ectuant une rotation de 2Π/n.Cependant cette représentation possède des limites quand on considère des automates possédantplus d'une dizaine d'états car sa représentation nécessite une taille trop importante. De plus cetalgorithme ne se préoccupe pas des transitions, il place uniquement les états de façon aérée. Ainsiplus l'automate a d'états (et donc de transitions), plus le nombre de croisements sera important,diminuant ainsi la lisibilité du graphique.Nous l'avons utilisé pendant la première partie de notre TER pour représenter rapidement desautomates, puis nous avons décidé de le conserver au cas où l'utilisateur souhaiterait visualiserdes automates à peu d'états (Fig 2.4).

Fig. 2.4 � Exemple de représentation de l'algorithme : Circulaire

2.1.5 Algorithme des ressorts

Cet algorithme est beaucoup plus général que ceux présentés précedemment. L'idée consiste àplacer au départ les états aléatoirement. Ensuite, tous les états se repoussent (a�n de ne pas êtretrop près les uns des autres) et ceux qui sont reliés par une transition s'attirent. Petit à petit lesétats se mettent en place et les forces de répulsion et d'attraction diminuent. Cet algorithme estdétaillé dans le chapitre "Algorithmes de Placement".Dans notre contexte, où nous devons représenter des graphes orientés avec des transitions pouvantboucler sur des états, c'est l'algorithme qui semblait le plus adapté (Fig 2.5).

Chacune de ces représentations présente des choix adaptés à des cas d'applications donnés.Après quelques journées de recherche et quelques échanges avec des auteurs d'applications déjàexistantes, notre choix s'est porté sur l'algorithme des ressorts.

7

Fig. 2.5 � Exemple de représentation de l'algorithme : Algorithme des ressorts

2.2 Quelques Outils

Ces travaux ont donné lieu à la création d'une multitude d'outils permettant de générer oud'éditer des graphes.Pendant notre phase de travail de recherche, nous avons trouvé une liste assez pertinente d'ou-tils et nous nous sommes concentrés sur les applications proches de celle que nous avions à réaliser.

Nous avons testé plusieurs outils existants (GraphViz, Vaucanson Project, Virtual AutomatorSimulator VAS, etc ....) écrits dans di�érents langages(C, Java ..) et possédant chacun des qualitésbien distinctes.

2.2.1 GraphViz

L'application GraphViz [6] permet de représenter graphiquement des graphes. Elle a été conçuepar une équipe des laboratoires de recherche de AT&T (American Telephone & Telegraph).

Cette application convient à la représentation de graphes très denses comprenant un très grandnombre de noeuds grâce à des algorithmes très puissants. Elle est très rapide à l'exécution et lerendu est optimisé a�n que les liens ne recouvrent pas les noeuds et qu'ils ne se croisent pas.

De plus, entièrement paramétrable, l'application permet de personnaliser le rendu des graphespar le choix des formes, des couleurs et des polices de caractères. Les formats de sortie sont trèsvariés.

Cependant, elle ne permet pas l'édition graphique (Drag & Drop) et nécessite de créer des�chiers d'entrée d'un format propriétaire très di�érent du format que nous devions utiliser (Fig2.6).

format propriétaire :

digraph G {

a -> b -> c;

e -> {f; c; a;}

}

8

Fig. 2.6 � Dessin de graphe orienté

2.2.2 The Vaucanson Project

Ce projet initié par Jacques Sakarovitch (ENST) et Sylvain Lombardy(LIAFA) en 2001 est unebibliothèque graphique écrite en C++(Fig 2.7). Le format d'entrée utilisé est le �chier XML dontla structure est proche de la nôtre. Les auteurs nous ont con�rmé qu'ils utilisaient la bibliothèqueGraphviz pour a�cher les automates et nous ont eux mêmes conseillé d'utiliser l'algorithme deFruchterman et Reingold dont nous parlerons dans le chapitre 4.

Fichier Xml utilsé par The Vaucanson Project

<automaton>

<content>

<states>

<state name="s0"/>

</states>

<transitions>

<transition src="s0" dst="s0" label="a"/>

<transition src="s0" dst="s0" label="b"/>

<initial state="s0"/>

<final state="s0"/>

</automaton>

Fig. 2.7 � Dessin de graphe orienté

9

2.2.3 Virtual Automator Simulator

Cette application [5] a attiré notre attention. Cet éditeur graphique écrit en Java et réalisé parMr Bovet Jean permet d'éditer graphiquement un automate (DRAG and DROP), de déplacer sesétats, de changer l'allure des transitions et également de le sauvegarder sous le format XML (Fig2.8).Nous n'avons pas réutiliser cette application car le �chier XML généré était très complexe ettotalement di�érent de celui utilisé par PepperMint.De plus cette application ne possédait aucun algorithme de placement. Nous nous sommes toutde même fortement inspiré de VAS, au niveau de l'édition graphique et avec l'accord de l'auteurnous avons réutiliser une petite partie de son code, notamment pour pourvoir repérer quand lasouris pointe sur l'une des transitions.

10

Fig. 2.8 � Interface graphique de VAS

Nous avons donc tiré parti de ces outils en concevant une application regroupant ces di�érentesqualités.

Pour information voici un rapide tableau récapitulatif.Un tableau plus complet [7] peut être trouvé en Annexe 1 (Fig 7.4 et 7.5).

11

Fig. 2.9 � Tableau récapitulatif

12

Chapitre 3

Organisation et calendrier

prévisionnel

Avant de commencer le développement de notre application, nous avons rédigé avec notreencadrant un cahier des charges, prévoyant l'organisation et l'évolution de notre travail tout aulong de ces quatre semaines.

3.1 Organisation en groupe

Comme nous l'avons remarqué durant la phase d'étude, ce projet est assez di�cile à répartiren quatre, car les parties sont étroitement liées. Nous avons donc choisi de composer deux groupesde travail.

Kostov Dimitre et Biche Florent (binôme A) devaient se charger de réaliser la partie concer-nant le dessin d'un automate, puis devaient y intégrer un algorithme de placement (Fruchtermanet Reingold cf chapitre 4), en permettant également le placement semi automatique des états.

Dameron Yann et Duca Max (binôme B) étaient chargés de développer l'autre partie concer-nant l'édition graphique et la manipulation des automates.

Pour la fusion des deux parties, nous avions préalablement convenu de réorganiser les binômesavec un membre respectif de chaque groupe. Ceci nous paraissait plus pratique car le groupe réa-lisant la fusion avait ainsi une connaissance complète des codes.

Pendant ce temps, l'autre groupe devait s'occuper de commencer la rédaction du rapport �nal.

C'est ce que le diagramme ci-dessous nous montre.

3.2 Diagramme de Gant

13

Fig. 3.1 � Diagramme de Gant

14

Chapitre 4

Algorithme de placement

Dans ce chapitre, nous présentons l'algorithme de Fruchterman et Reingold [9][10] dont nousnous sommes servi pour réaliser le placement d'état. Une fois les états placés, nous dessinons lestransitions sous forme de courbes de Bézier (Chapitre 5).

4.1 Algorithme de Fruchterman et Reingold

Cet algorithme fait parti de la classe des algorithmes dits à ressort, il a pour but de produireune image du graphe en deux dimensions qui correspond à quelques critères esthétiques, tels que :

1. Répartition homogène des états dans le cadre.

2. Minimisation des croisements des arêtes.

3. Uniformisation de la longueur des arêtes.

4. Respect de la symétrie du graphe.

5. Utilisation optimale de la surface du cadre.

En pratique, on met des ressorts entre chaque couple de sommets dont la longueur au repos et laforce dépend de la distance entre ces sommets dans le graphe. Ensuite, on laisse évaluer ce systèmepour essayer de trouver un point d'équilibre qui sera notre représentation. Voici l'algorithmegénéral [9] :

INITIALISATION : Positionnement aléatoire des sommets

TANT QUE k < Max_iter FAIRE

POUR TOUT sommet u FAIRE

POUR TOUT sommet v !-u FAIRE

SI distance (u;v ) < seuil ALORS

Calcul de la force de répulsion entre u et v

POUR TOUTE arête (u,v) FAIRE

Calcul de la force d'attraction entre u et v

POUR TOUT sommet u faire

Cumul des forces

Déplacement de u en fonction de la température globale

Diminuer la température globale

Les résultats de l'algorithme dépendent essentiellement de trois fonctions.

La fonction qui calcule la force d'attraction, celle qui calcule la force de répulsion et cellequi calcule la température du système.La notion de la température globale du système a été introduite pour limiter le déplacement des

15

sommets. Cette température diminue au cours du déroulement de l'algorithme ce qui implique queplus on approchera de l'équilibre, moins un sommet pourra se déplacer. En e�et, le déplacementde tous les sommets est inversement proportionnel à la température globale.Le plus di�cile est de trouver la manière dont on va calculer ces trois fonctions, c'est-à-dire : lesparamètres dont elles vont dépendre et le rapport entre ces paramètres pour avoir la représentationqui nous convient le plus .

Pour l'instant, on calcule :� les forces d'attraction et de répulsion par rapport à la distance entre les états et la taille dela surface de la fenêtre.La force d' attraction entre deux sommet vi et vj est dé�nie par :

Fa(vi, vj) = βijdαaij /k

βij est le poids de l'arrête (vi, vj), k est calculé en fonction de la surface de la fenêtre. dij

est la distance entre vi et vj sur le dessin . Si les sommets vi et vj ne sont pas reliés par unearrête alors Fa est égale à 0.

� La force de répulsion est dé�nie par :

Fr(vi, vj) = −k2/dαrij

La constante αa (respectivement αr ) sert à dé�nir le degré d'attraction (respectivement derépulsion), entre 2 sommets.

� La température par rapport à la surface et le nombre d'itérations qu'on a e�ectué.

Nous utilisons une variante de l'algorithme de Fruchterman et Reingold (Graph drawing byforce directed placement), qui en lui-même est une variante d'implémentation de l'algorithmegénéral pour placer les états de l'automate. Cet algorithme travaille dans une fenêtre de taille W(largeur) par L (hauteur).Nous donnons ici une version en pseudo code de l'algorithme de Fruchterman et Reingold tellequ'elle est présentée dans l'article original [10].Cet algorithme prend en entrée un graphe G représenté par ses sommets V et son ensemble d'arêtesE.

area := W*L;

G = (V,E) // Les sommets ont des positions initiales aléatoires

k := racine (area/|V| );

function fa(z) := begin return z*z/k end;

function fr(z) := begin return k*k/z end;

for i := 1 to iterations do begin

// Calcul des forces repulsives

for v in V do begin

// chaque sommet a deux vector .pos (position) et .disp (déplacement)

v.disp := 0;

for u in V do

if (u # v) then begin // u relie a v

delta := v.pos - u.pos; // delta est le vecteur difference

v.disp := v.disp + (delta / |delta|) fr(|delta|);

end

end

// Calcul des forces attractives

for e in E do begin

// Chaque arete est une paire ordonnee de sommets .v et .u

16

delta := e.v.pos - e.u.pos;

e.v.disp := e.v.disp - (delta/|delta|) fa|delta|;

e.u.disp := e.u.disp + (delta/|delta|) fa|delta|;

end

// Limiter le deplacement maximal a la temperature t

// et interdire de sortir de l ecran

for v in V do begin

v.pos := v.pos + (v.disp/|v.disp|) min(v.disp,t);

v.pos.x := min(W/2,max(-W/2,v.pos.x));

v.pos.y := min(L/2,max(-L/2,v.pos.y))

end

// reduit la temperature

t := cool(t)

end

L'idée consiste dans un premier temps à placer au départ les états aléatoirement, ensuite tousles états se repoussent et ceux qui sont reliés par une transition s'attirent. Petit à petit les étatsse mettent en place et les forces de répulsion/attraction diminuent.

Pour éviter que des états se chevauchent lors du calcul des forces de répulsion pour un état,on e�ectue le calcul en tenant compte de tous les états proches délimités par un seuil, au lieu detenir compte uniquement des états reliés.

Au début de l'implémentation, nous tenions compte de toutes les transitions. Nous avons re-marqué que cela ne donnait pas les résultats attendus. Nous n'avons donc pas tenu compte destransitions qui bouclaient sur un même état ni du nombre de transitions entre deux états.

On calcule k, la distance optimale entre les états comme suit :

k = C√

areanumberofvertices

où la constante C est trouvée expérimentalement. Nous voudrions que les états soient unifor-mément distribués dans la fenêtre et k est le rayon du secteur vide autour d'un état. On a prisC=1 comme dans de l'algorithme de Fruchterman et Reingold.Pour la fonction de température (paramètre t, fonction cool) on prend comme valeur initialet=W/10 et comme évolution cool(t) = W/(10*(1+numeroIteration)). Ces résultats sont trouvésexpérimentalement.

Voilà une petite partie des évolutions qu'on a essayé :cool(t) = W/(1 + numeroIteration)cool(t) = W/(1 + 10* numeroIteration)cool(t) = W/(10*(1+K*numeroIteration))

On calcule le seuil (seuil = 2*k). Si la distance entre deux états est plus petite que le seuil(c'est à dire plus petite que 2 fois le rayon du secteur vide autour d'un état) on calcule la force derépulsion entre ces deux états.

4.1.1 Fonctions d'attraction et de répulsion

On est parti de la fonction d'attraction abstraite qu'on a dé�ni au départ. Puisqu'on n'a pasde poids sur les arêtes on a βij=1 pour toutes les transactions. Après des essais avec plusieursvaleurs pour αa on a choisi αa=2 et �nalement notre fonction d'attraction est la même que cellede Fruchterman et Reingold.

17

Fa(vi, vj) = d2ij/k

De même pour la fonction de répulsion après des essais avec plusieurs valeurs pour αr on achoisi αr=1 et �nalement notre fonction de répulsion est la même que celle de Fruchterman etReingold.Fr(vi, vj) = −k2/dij

La �gure 4.1 illustre ces forces et leurs sommes par rapport à la distance. Le point où la sommedes forces d'attraction et de répulsion croisent l'axes des abscisses X, celui où les deux forces s'an-nuleraient mutuellement, est exactement le point k, la distance idéale entre les états.

Fig. 4.1 � Forces et distances [12]

Pour trouver le point d'équilibre du système on évalue 50 fois le système (valeur trouvée expé-rimentalement par rapport au rendu et au temps CPU ). On a rencontré le même problème d'e�etbloquant que celui expliqué dans l'article original de Fruchterman et Reingold lors de leurs essaisde représentation des arbres binaires, qui est illustré à la �gure 4.2

Fig. 4.2 � Représentation d'arbres binaires [12]

Sommets aaab, aaaba et aaabb sont attirés vers l'ancêtre aaa, mais ne peuvent pas dépasser

18

la barrière posée par les sommets ab et aba. On utilise la même heuristique que Fruchtermanet Reingold pour résoudre le problème qui consiste à ne pas prendre en compte les forces derépulsions chaque cinquième itération. Cette heuristique est utile, mais elle ne peut pas surmonterun problème d'e�et bloquant qui implique beaucoup de sommets.

4.2 Expérimentations

Voici un exemple d'exécution de notre algorithme avec un automate symétrique, on peut ob-server qu'on obtient un automate respectant les 5 critères dé�nis au début du chapitre 4.

Les états sont placés aléatoirement. Le dessin n'est pas compréhensible, la symétrie de la �guren'est pas visible, il y a beaucoup de croisements des transitions, la longueur des transitions n'estpas uniforme et l'automate n'est pas réparti proportionnellement dans le cadre (Fig 4.3).

Fig. 4.3 � Automate avant l'exécution de l'algorithme de Fruchterman

Après un premier appel de l'algorithme, on a une amélioration mais le résultat n'est toujourspas satisfaisant (Fig 4.4).

Fig. 4.4 � Algorithme en phase d'équilibre

Après un deuxième appel de l'algorithme on aperçoit la symétrie de l'automate, les croisementsdes transitions est minimale, et l'automate est répartie proportionnellement dans le cadre (Fig 4.5).

19

Fig. 4.5 � Algorithme en phase d'équilibre

Après un troisième lancement de l'algorithme on vois qu'on n'a pas beaucoup de changement.La �gure n'est pas loin de son point d'équilibre, la longueur des transitions est presque uniformeet l'automate occupe de manière homogène le cadre(Fig 4.6).

Fig. 4.6 � Automate après l'exécution de l'algorithme de Fruchterman

C'est un algorithme dont les résultats ne sont pas parfait dans tous les cas, le plus importantest qu'il est capable de traiter des automates relativement grands et avec une vitesse d'exécutionperformante. La plupart des automates testés ont été traité en moins d'une seconde, les autres enmoins de 10 secondes. Je site Fruchtermant et Rengold :L'algorithme de Davidson et Hrels qui est aussi une variante de l'algorithme à ressort semble avoiratteint un plus haut niveau de �exibilité et d'esthétisme pour la représantation des graphes quisont un peu plus complexes, mais pour le faire ils paient cher en temps d'exécution.

20

Chapitre 5

Conception Graphique

Dans cette partie, nous allons expliquer comment nous avons représenté les di�érents objets etcomment les manipuler.

5.1 Adaptation du diagramme de classes

Lors de la conception graphique, nous avons étudié et modi�é le diagramme de classes existant(voir en Annexe Fig 7.1) en utilisant au mieux la programmation orientée objet a�n de modi�erle moins possible le code qui nous a été fourni. En e�et, les classes qui décrivaient la manipulationd'automates ne nous permettaient pas d'ajouter des fonctionnalités graphiques (car l'applicationpepperMint fonctionnait uniquement de façon textuelle). C'est pour cela que nous avons ajouté 3classes (voir en Annexe Fig 7.2 et 7.3) :

5.1.1 AutomatonGraph

Cette classe est une classe �lle de la classe Automaton qui lui ajoute un attribut observable(en utilisant le pattern Observer/Observable) a�n de maintenir l'interface graphique à jour lorsdes modi�cations de l'automate. De plus, l'intérêt principal de cette classe est de manipuler lesobjets graphiques que nous avons dé�ni, à savoir StateGraph et TransitionGraph.

5.1.2 StateGraph

Cette classe est une classe �lle de la classe State qui ajoute des attributs permettant de spéci�erles caractéristiques graphiques. Ces attributs sont :

� Un entier static �xé à 40 qui correspond à la taille du cercle. Ce cercle est la représentationd'un état dans notre application graphique.

� Deux entiers faisant référence à la position du centre de l'état dans l'éditeur.� Un booléen permettant de savoir si l'état est pointé.� Un observable qui contient la liste des transitions à noti�er lors de la modi�cation de l'état.� Un booléen qui permet de savoir si la position de l'état est �xe ou pas. Cet attribut estprincipalement utilisé par l'algorithme du ressort.

5.1.3 TransitionGraph

Cette classe est une classe �lle de la classe Transition qui ajoute des attributs permettant decaractériser graphiquement les transitions. Ces attributs sont :

� Deux StateGraph correspondant à l'état de départ et d'arrivée de la transition.� Un identi�cateur unique représenté par un entier.� Un entier permettant de calculer la courbure de la transition.

21

Fig. 5.1 � Exemple de dessin en java

� Quatre entiers qui correspondent aux coordonnées des deux points de contrôle. Comme nousl'expliquerons dans la partie 5.2, les points de contrôle sont utilisés pour dessiner la courbe.

� Une CubicCurve2D qui est l'objet java qui représente la courbe.� Une �èche située à l'intersection de la courbe et de l'état d'arrivée.� Un booléen permettant de savoir si la transition est pointée.

5.1.4 ParserXMLGraph

Comme nous venons de l'expliquer, nous avons modi�é le diagramme de classe, c'est pourquoinous avons décidé d'adapter le parser pour qu'il génère un AutomatonGraph à la place d'un Auto-maton. L'application PepperMint utilise un parser pour traduire les �chiers xml en un objet javaAutomaton. Les �chiers xml doivent être conformes à un �chier automaton.dtd (voir Annexe).Nous avons donc dé�ni une nouvelle classe ParseXMLGraph qui hérite de la classe ParseXML.Nous avons modi�é le �chier automaton.dtd (voir Annexe) pour que l'on puisse prendre en comptede nouvelles balises xml utiles pour la représentation graphique. Ces balises mémorisent la positiondes états et des transitions. Ainsi notre classe ParseXMLGraph traduit un �chier xml en un objetjava AutomatonGraph.

Nous avons donc apporté ces modi�cations a�n de pouvoir représenter un automate graphique-ment. Ainsi dans la partie suivante, nous allons expliquer comment dessiner l'automate.

5.2 Dessin des composants de base

Dans cette partie, nous allons expliquer comment sont représentés les di�érents objets quiconstituent un automate.En java, les formes géométriques (courbes, cercles, segment de droite ...) sont généralement conte-nues dans un rectangle (Fig 5.1). Sur l'exemple de la �gure ??, on voit que pour représenter uncercle il ne faut pas donné son centre (le point B) mais l'angle en haut à gauche du carré qui lecontient (le point A).

5.2.1 Représentation d'un état

Les états sont représentés par des cercles d'une taille de 40 pixels de diamètre. On a�che aumilieu de cet état son nom. A�n de faciliter la lisibilité de l'automate, l'état initial est pointé parune �èche et l'état pointé par la souris est mis en évidence par une couleur di�érente en surbrillance(Figure 5.2).

22

Fig. 5.2 � Di�érentes représentations possibles d'un état.

5.2.2 Représentation d'une transition

Nous avons eu plus de di�cultés pour dessiner une transition. Notre première idée était dereprésenter les transitions à l'aide d'une courbe formée par des petits segments de droites, mais lerendu graphique n'était pas satisfaisant (Figure 5.3).

Fig. 5.3 � Dessin de polylignes.

Pendant la phase de recherche, nous avions été impressionné par la représentation des au-tomates faite par Visual Automata Simulator. Nous avons donc regardé le code source de cetteapplication a�n de connaître la structure utilisée pour représenter les transitions. La solution estd'utiliser les courbes de Bézier qui sont représentées en java par l'objet CubicCurve2D.Une CubicCurve2D est caractérisée par un point de départ P0, un point d'arrivée P3 et deuxpoints de contrôle. Les points de contrôle P1 et P2 servent à donner la forme de la courbe. Ladroite (P0P1) est la tangente à la courbe au point P0. De même pour la droite (P2P3) (Fig 5.4).

Fig. 5.4 � Représentation d'une courbe de Bézier [8]

Ceci correspond à une courbe de Bézier cubique dé�nie par les points de contrôle P0, P1, P2et P3. Son équation (1) est de la forme :

B(t) = (1− t)3 × P0 + 3× (1− t)2 × t× P1 + 3× (1− t)× t2P2 + t3 × P3, t ∈ [0, 1].

Pour construire la représentation de la transition, on commence par calculer la position despoints de contrôle. Il y a deux cas possibles :

� L'état de départ est di�érent de l'état d'arrivée :Dans ce cas, les deux points de contrôle sont les mêmes. On prend le milieu du segment

23

[P0P3] et on calcule la courbure de la transition. Cette courbure est obtenue en considé-rant le nombre de transitions déjà existantes allant de l'état de départ vers l'état d'arrivée.On utilise un coe�cient multiplicateur qui augmente la courbure en fonction du nombre detransitions à dessiner. Ceci nous permet de connaître les coordonnées du point de contrôle.

� L'état de départ et l'état d'arrivé sont les mêmes :Ici nous avons besoin de deux points de contrôle di�érents a�n de tracer la transition. Lespoints de contrôle sont placés de façon à ce que l'angle P1P3P2 soit de 2Π/5 (cette mesurea été trouvée après un jeu d'essais a�n de respecter des contraintes d'esthétisme).

A�n de dessiner la �èche en �n de courbe sur l'état d'arrivée, il nous faut trouver le pointd'intersection entre la courbe et le cercle représentant l'état d'arrivée. Sur ce problème, nousavons fait appel aux conseils d'un professeur du département de Mathématiques : M. HirschowitzAndré. Il nous a conseillé de nous servir de la formule des courbes de Bézier pour itérer a�n detrouver le point d'intersection.Nous partons du centre de l'état d'arrivée (soit t=1) et on itère la formule (1) jusqu'à trouver lepoint d'intersection en diminuant la valeur de t de 0,001 (Fig 5.5).

Fig. 5.5 � Schéma du parcours entre le centre de l'état vers le point d'intersection

A chaque tour de boucle, la formule nous donne la position d'un point que l'on obtient de lafaçon suivante :

Bx(t) = (1− t)3 × P0x + 3× (1− t)2 × t× P1x + 3× (1− t)× t2P2x + t3 × P3x, t ∈ [0, 1].

By(t) = (1− t)3 × P0y + 3× (1− t)2 × t× P1y + 3× (1− t)× t2P2y + t3 × P3y, t ∈ [0, 1].

Dès que la distance entre ce point et le centre de l'état d'arrivée est supérieure au rayon del'état, alors on a trouvé le point d'intersection au pixel près.

Il nous reste donc à tracer la �èche au bout de la transition. Ceci est facile car la droite (P2P3)est la tangente à la courbe au point P3. Nous avons donc la bonne orientation pour la �èche et ilnous su�t de la dessiner au point P3 (Fig 5.6).

Fig. 5.6 � Explication du tracé des transitions.

24

5.2.3 A�chage des étiquettes de transitions

Dans les automates que nous manipulons, les transitions sont étiquetées de la forme condi-tion/a�ectation(s). Ces étiquettes peuvent donc être assez longues et leur a�chage sur la repré-sentation peut donc nuire à la lisibilité de l'automate. Par défaut nous n'a�chons donc pas lesétiquettes des transitions, mais nous avons laissé à l'utilisateur plusieurs moyens de les voir.

� Pointer la transition : Lorsqu'une transition est pointée, elle est représentée de façon di�é-rente. A�n d'améliorer la représentation, nous avons également décidé d'a�cher l'étiquettede la transition pointée. Ainsi l'utilisateur n'a qu'à pointer la transition qui l'intéresse pourvoir la condition et les a�ectations s'y reportant.(Fig 5.7)

Fig. 5.7 � A�chage du label lorsqu'on pointe une transition

� A�cher le panel d'informations : L'utilisateur à la possibilité de faire a�cher les informationsrelatives aux transitions, aux ports et aux registres grâce à un panel d'informations. Ce panels'ouvre sur la droite de l'application et contient :� un tableau des ports (nom, type, sens)� un tableau des registres (nom, type, valeur)� un tableau des transitions(identi�ant, étiquette)Lorsque ce panel est ouvert, la représentation des transitions comporte en plus l'a�chage del'identi�ant, a�n que l'utilisateur puisse facilement les retrouver dans le panel d'informations.Si une transition est pointée alors on n'a�che pas son identi�ant mais son étiquette.(Fig 5.8)

� A�cher toutes les étiquettes : Cette option permet à l'utilisateur de forcer l'a�chage detoutes les étiquettes. Elle est utile pour les petits automates car elle évite de faire a�cher lepanel d'informations qui prend de la place dans la fenêtre(Fig 5.9)

5.3 Edition

Pour pouvoir faire fonctionner notre application, il faut au préalable dé�nir les ports et lesregistres du système. Ces ports et ces registres sont indispensables à la création/édition de tran-sitions car les conditions et les a�ectations doivent utiliser des variables déclarées. C'est pourquoilors de la création d'un nouvel automate, il est tout d'abord demandé à l'utilisateur de saisir lesports et les registres qu'il utilisera par la suite pour éditer les transitions. A tout moment, l'uti-lisateur peut modi�er les ports et les registres de l'automate. Par contre il n'est pas demandé dedé�nir les ports et les registres lors du chargement d'un automate puisque ces derniers ont déjàété dé�ni. (Fig 5.10)

25

Fig. 5.8 � A�chage des informations

Fig. 5.9 � A�chage de tous les labels

5.3.1 Création/Edition des états

Lors de la création d'un état, une fenêtre s'ouvre et demande à l'utilisateur d'entrer le nom del'état, de choisir si c'est l'état initial et si sa position est �xée. Il peut aussi éditer un état (c'est-à-dire changer son nom, faire qu'il devienne l'état initial ou �xer sa position pour les algorithmes)(Fig 5.11)

Si le nom de l'état est valide, c'est-à-dire que ce nom n'est pas déjà utilisé dans l'automate,alors lors de la validation, l'état sera ajouté à l'automate sinon il sera demandé à l'utilisateur dele changer (Fig 5.12).

On peut aussi supprimer un état, on retire tout d'abord les transitions qui lui sont liées, puison supprime l'état.

5.3.2 Création/édition des transitions

Lors de la création d'une transition, une fenêtre s'ouvre en demandant à l'utilisateur de donnerla condition et éventuellement les a�ectations nécessaires à la transition. Lorsque l'utilisateur

26

Fig. 5.10 � A�chage des ports et des registres

Fig. 5.11 � Création/édition d'un état.

valide, on véri�e que la condition et que les a�ectations sont correctes, c'est-à-dire que les variablescorrespondent à un port ou à un registre de l'automate, mais aussi que la syntaxe est correcte(véri�cation de la syntaxe grâce à un parser existant). (Fig 5.13)

S'il n'y a pas d'erreurs, la transition est ajoutée, sinon on informe l'utilisateur sur le champn'ayant pas réussi à passer les véri�cations et on lui laisse la possibilité de corriger son erreur.(Fig5.14)

Si on choisit de modi�er la transition, une fenêtre identique à celle de la création s'ouvre avecles champs remplis. Si on choisit de la supprimer, on la retire simplement de l'automate.

5.3.3 Déplacement d'un objet

Déplacer un état correspond à changer sa position en x et en y en fonction de la position de lasouris. Si on déplace un état, il faut que les transitions qui y sont rattachées suivent son déplace-ment. Comme nous l'avons vu dans la section 5.1 un état possède un attribut observable (patternObserver/Observable) qui contient l'ensemble des transitions à noti�er lorsqu'il est modi�é. Ceci

27

Fig. 5.12 � Erreur lors de création/édition d'un état.

Fig. 5.13 � Création/édition d'une transition.

nous permet donc d'informer en permanence les transitions concernées de façon à les réactualiserDéplacer une transition correspond à changer uniquement la position de ses points de contrôle. Sion déplace une transition qui n'est pas une boucle, on place les points de contrôle (qui sont égaux)à la position de la souris. Par contre si on se situe sur une boucle, on peut l'agrandir/rétrécir etla faire tourner autour de l'état. Les points de contrôle sont l'image du point pointé par la sourispar la rotation de centre le centre de l'état et d'angle plus ou moins 45 degrés.

5.3.4 Paramétrage des couleurs

Au fur et à mesure des réunions d'avancement, il nous est apparu indispensable de permettreà l'utilisateur de paramétrer ses propres couleurs. Il est donc possible de modi�er :

� La couleur des états (cercle et nom)� La couleur des transitions� La couleur des labels (condition / a�ectation des transitions)� La couleur de surbrillance.� La couleur de la �èche représentant l'état initial.

5.3.5 Choix des algorithmes de placement

Nous avons implémenté deux algorithmes de placement dont un très simpliste (mieux adaptélorsqu'il y a peu d'états) qui est l'algorithme du cercle et un autre plus complexe (mieux adaptélorsqu'il y a de nombreux états) qui est l'algorithme des ressorts (voir chapitre 2).Lors du lancement de l'application, l'algorithme par défaut est celui des ressorts, mais l'utilisateurpeut changer d'algorithme à l'aide la barre de menu.En cliquant sur le bouton de placement, l'automate est repositionné en utilisant l'algorithme choisi(Fig 5.15).

5.4 Sauvegarde/restauration

Nous avons développé un outil permettant de créer et de représenter des automates formésd'une centaine d'états, or l'utilisateur peut les placer de façon automatique ou personnalisée.Il nous a donc fallu lui permettre de sauver et de restaurer son travail, c'est-à-dire mémoriserla position des éléments qui composent l'automate. Pour cela nous avons prévu deux types desauvegarde (et de restauration).

28

Fig. 5.14 � Erreur lors de création/édition d'une transition.

Fig. 5.15 � Lancement de l'algorithme de placement.

5.4.1 Sauvegarde XML

La sauvegarde en xml consiste simplement à écrire le contenu de l'objet Automaton en utilisantla forme Xml dé�nie par l'application.Comme nous l'avons expliqué précédemment nous avons apporté quelques modi�cations au formatXML a�n de mémoriser la position des états et des transitions.Nous obtenons donc un �chier Xml ayant la forme suivante :

<?xml version='1.0'?>

<!DOCTYPE automaton SYSTEM "automaton.dtd">

<automaton>



<state posX="232" posY = "149">0</state>




<init>

<initial_state>0</initial_state>

<property>x=0</property>

</init>



<register type="int">

<name>x</name>

<value>0</value>

</register>



<port type="int" type_port = "in">

<name>a</name>

</port>



<transition>

<from>0</from>

<to>2</to>

29

<condition>true</condition>

<pointControle1>

<posX>342</posX>

<posY>115</posY>

</pointControle1>

<pointControle2>

<posX>342</posX>

<posY>115</posY>

</pointControle2>

</transition>

</automaton>

5.4.2 Restauration XML

Pour le chargement d'un �chier Xml, il faut faire appel à un parser qui va construire un objetde type Automaton et lui ajouter les états et les transitions contenus dans le �chier Xml.Les éléments dont la position est donnée par le �chier seront placés automatiquement par lesalgorithmes de placement, les autres seront dessinés à la position spéci�ée.

5.4.3 Sauvegarde et Restauration par sérialisation

La sérialisation nous permet de sauvegarder directement toutes les informations contenuespar notre objet Automaton. Lors de la restauration de l'objet, toutes les informations sont ainsiconservées, ce qui permet à l'utilisateur de retrouver son travail exactement dans le même état.

5.4.4 Sauvegarde de l'image

Durant le développement de l'application, il nous a été demandé d'ajouter une fonctionnalitépour permettre à l'utilisateur de sauver la représentation de l'automate sous forme d'image et demémoriser les informations relatives aux ports, aux registres et aux transitions dans un �chiertexte. Nous avons donc mis en place le code correspondant pour permettre la sauvegarde en JPG.Lors de cette sauvegarde, nous enregistrons automatiquement le �chier texte avec le même nom(seule l'extension change). Nous avons également prévu la sauvegarde sous forme de �chier EPS(et texte) grâce à 3 classes récupérées sur Internet, ceci a�n de pouvoir intégrer facilement lesimages dans d'éventuels rapports au format LaTeX.

5.5 Conclusion

Dans ce chapitre, nous avons vu comment nous avons adapté le diagramme de classe de l'ap-plication PepperMint puis nous avons énoncé les di�cultés rencontrées pour dessiner un automateet �nalement nous avons montré les fonctionnalités o�ertes par notre application. Grâce à cesfonctionnalités, il devient très simple de concevoir des automates. En e�et, l'utilisateur n'a plusbesoin de connaÎtre le xml, il doit simplement utiliser la souris.

30

Chapitre 6

Conclusion

Dans le cadre de ce TER, nous avons commencé par e�ectuer une phase de recherche sur lesdi�érentes possibilités existantes a�n de représenter des automates.

Après avoir étudié plusieurs algorithmes et testé di�érentes applications déjà réalisées, nousavons décidé que l'algorithme le mieux adapté à nos besoins était l'algorithme des ressorts, caril répondait à toutes les contraintes que nous avions. C'est donc cet algorithme que nous avonsdéveloppé pour placer automatiquement les états de nos automates. Nous avons gardé l'algorithmedu cercle au cas où l'utilisateur manipule de petits automates. L'utilisateur peut donc choisir letype de représentation correspondant le plus à ses besoins.Nous avons également réalisé un éditeur d'automate, qui permet d'ajouter, ou de supprimer desétats ou des transitions, mais aussi de modi�er un automate existant. L'utilisateur peut choisir lescouleurs de la représentation, ce qui rend l'application plus agréable.Comme nous l'avons vu, il est possible de sauvegarder un automate mais aussi de le restaurer parla suite. Pour cela nous avons réalisé plusieurs types de sauvegarde : Xml, Sérialisation, Image.

Durant la première phase de notre TER nous avons mis au point un cahier des charges avecle client. Ce cahier des charges dé�nissait les fonctionnalités que nous devions implémenter et lesdates auxquelles elles devaient être réalisées.Comme la représentation graphique de l'automate était plus en rapport avec l'éditeur qu'avec l'al-gorithme de placement, c'est le groupe Dameron-Duca qui s'est chargé de cette partie. Néanmoinspour mettre en place l'algorithme de placement, le groupe Biche-Kostov avait besoin de connaitreles propriétés de la représentation graphique. C'est pourquoi, nous avons convenu tous ensembled'une interface a�n que les deux groupes puissent développer séparément.Florent Biche et Dimitre Kostov ce sont alors chargés d'implémenter l'algorithme de placementpendant que Yann Dameron et Max Duca ont réalisé le dessin de l'automate et l'éditeur graphique.Après avoir réalisé la fusion des codes, chaque groupe a rédigé la partie du rapport liée à ces ac-tivités ainsi que le manuel de programmation.

Dans l'ensemble le cahier des charges à été respecté, c'est-à-dire que nous avons réalisé lestâches prévues et même plus, dans l'ordre de priorité qui avait été choisi.Par contre nous avions mal évalué le temps nécessaire pour les réaliser. En e�et nous avons passébeaucoup moins de temps que ce que nous pensions pour réaliser la fusion des codes et les fonctionscomme la sauvegarde, ce qui nous a permis d'améliorer le dessin de l'automate (les �èches) qui anécessité plus de temps que ce que nous avions envisagé.

Au �nal, notre application permet de créer et de manipuler de façon simple des automates.L'utilisateur n'est donc plus obligé de connaître le Xml pour pouvoir se servir de l'applicationPepperMint.

31

Nous aurions aimé mettre en place le code permettant d'a�cher la simulation sur la représen-tation graphique que nous avons réalisé, mais cette fonctionnalité étant optionnelle nous avonsprivilégié les améliorations graphiques et le confort d'utilisation.Il faudra donc que quelqu'un développe cette partie mais grâce au code mis en place nous pensonsque ce ne sera pas très di�cile.

32

Chapitre 7

Annexe

7.1 Format de la DTD

<!ENTITY % type "(int|boolean|array)">

<!ELEMENT automaton (state+, init, register*, port*, transition+)>

<!ELEMENT state (#PCDATA)>



<!ATTLIST state

posX CDATA #IMPLIED

posY CDATA #IMPLIED

>



<!ELEMENT init (initial_state, property?)>

<!ELEMENT initial_state (#PCDATA)>

<!ELEMENT property (#PCDATA)>

<!ELEMENT register (name, value, constraint?)>

<!ATTLIST register

type %type; #REQUIRED

>

<!ELEMENT port (name, constraint?)>

<!ATTLIST port

type_port (in | out | buffer) #REQUIRED

type %type; #REQUIRED

>

<!ELEMENT name (#PCDATA)>

<!ELEMENT value (#PCDATA)>

<!ELEMENT constraint (#PCDATA)>



<!ELEMENT transition (from, to, condition, (pointControle1, pointControle2)?, assignment*)>



<!ELEMENT from (#PCDATA)>

<!ELEMENT to (#PCDATA)>

<!ELEMENT condition (#PCDATA)>

<!ELEMENT assignment (var, expression)>

33

<!ELEMENT var (#PCDATA)>

<!ELEMENT expression (#PCDATA)>



<!ELEMENT pointControle1 (posX, posY)>

<!ELEMENT pointControle2 (posX, posY)>

<!ELEMENT posX (#PCDATA)>

<!ELEMENT posY (#PCDATA)>



7.2 Diagramme de Classe

Fig. 7.1 � Diagramme de classe existant.

34

Fig. 7.2 � Diagramme de classe de notre application (partie 1).

7.3 Tableaux comparatifs des applications

35


36


Fig. 7.5 � Tableau comparatif

37

Chapitre 8

Bibliographie

[3] http://www.algorithmic-solutions.info/leda_guide/graph_algorithms/graph_draw.html

[4] http://www.infres.enst.fr/~charon/MOD/rapports/dessinGraphes.pdf

[5] http://www.cs.usfca.edu/~jbovet/vas.html

[6] http://www.graphviz.org/

[7] adresse du site tableau voir powerpont présoutenance

[8] http://fr.wikipdia.org/wiki/Courbe_de_Bézier)

[9] http://isdm.univ-tln.fr/PDF/isdm6/isdm6a57_karouach2.pdf

[10] article publié par FRuCHTERMAN ET REINGOLD en 1991, Graph Drawing by Force-directed Placement

[11] http://www.enseignement.polytechnique.fr/informatique/IF/projets/rossin/sujet.html

[12]THOMAS M. J. FRUCHTERMAN* AND EDWARD M. REINGOLD

Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W.

Springfield Avenue, Urbana, IL 61801-2987, U.S.A.

http://www.cs.tu-bs.de/ips/tmuecke/sep/layout/planarity/

38

Documents

Développement d'une bibliothèque Java pour la manipulation ...deptinfo.unice.fr/twiki/pub/Minfo05/DepotDesRapports/Rapport_TER... · Comme on peut le voir sur l'exemple (Fig 1.1),