Discussion :

[vince73_2]

Bonjour à tous!


Je travaille actuellement sur un programme qui permet de convertir une expression régulière en un automate déterministe. J'aimerais pouvoir représenter l'automate produit. Pour cela, j'ai besoin de positionner correctement les noeuds de mon automate (qui peut être vu comme un graphe orienté).

J'ai vu qu'il existait l'algorithme de Fruchterman et le positionnement par ressort. J'ai essayé de l'implémenter en Java mais sans succès. Je voulais donc savoir si quelqu'un avait déjà implémenté ce genre d'algorithme et si cette personne pouvait m'aider....


Je vous remercie!

[FR119492]

Salut!

Je travaille actuellement sur un programme qui permet de convertir une expression régulière en un automate déterministe

Etrange formulation du problème! Wikipedia définit un automate comme un "dispositif se comportant de manière automatique, c'est-à-dire sans intervention d'un humain". Un programme informatique produit des résultats numériques, ou, cas échéant graphiques, mais jamais un dispositif.
Jean-Marc Blanc

[vince73_2]

Un automate traitant des expressions régulières n'est jamais qu'un graphe orienté, dont les arrêtes sont étiquetés par des symboles. Il s'agit d'un automate car le graphe produit permet de déterminer si oui ou non l'expression régulière est acceptée par l'automate. (Voir JFlex). Mais là n'est pas mon problème. Mon problème principal est de disposer de manière optimale les noeuds d'un graphe dans une surface (typiquement une fenêtre dont les dimensions sont précisées).

[pseudocode]

Un automate traitant des expressions régulières n'est jamais qu'un graphe orienté, dont les arrêtes sont étiquetés par des symboles. Il s'agit d'un automate car le graphe produit permet de déterminer si oui ou non l'expression régulière est acceptée par l'automate. (Voir JFlex). Mais là n'est pas mon problème. Mon problème principal est de disposer de manière optimale les noeuds d'un graphe dans une surface (typiquement une fenêtre dont les dimensions sont précisées).

Télécharge le logiciel "yEd" (java) et regarde s'il y a un type de layout qui correspond a tes attentes. Si c'est le cas, tu auras déjà un axe de recherche concernant l'algorithme qu'il te faut.



(ce n'est pas de la pub déguisée pour ce logiciel, bien que je l'utilise souvent. C'est surtout que ce logiciel inclut des algos de layout automatique)

[Franck Dernoncourt]

Personnellement j'utilise Graphviz : il n'est pas parfait mais peut beaucoup aider dans certaines situations.

• Site officiel : http://www.graphviz.org/
• Quelques exemples : http://www.omninerd.com/articles/Aut...y_and_Graphviz

[vince73_2]

Merci beaucoup pour votre aide, au fait je sais l'algorithme qu'il me faut : c'est Fruchterman (algorithme des ressorts), mais le problème c'est que je n'arrive pas à l'implémenter.