Salut à tous !  
Je fais une application java ou l'utilisateur est amené à créer un graphe de manière graphique très intuitive....
(Il s'agit de graphe relationnel)
Je peux sauvegarder ce graphe, et donc le recharger ensuite, ma question est :
Comment organiser les noeuds pour qu'il apparaisse le mieux possible quand je recharge le graphe ??  
Autrement dit : Existe-t-il des algorithmes pour présenter un graphe propre, avec le minimum de croisements d'arcs ?
Merci d'avance

http://java.sun.com/applets/jdk/1.1/demo/GraphLayout/

T'as de la chance, t'es tombé sur un problème NP-complet (problème du routage) ... T'as pas fini d'en chier.

Merci...Mais je crois qu'on à pas habitué les ingenieurs Sun à commenter leur Code...J'ai plus qu'à tout décortiquer    
Si quelqu'un d'autre à quelque chose de plus...comment dire..formel histoire de comprendre le principe de l'algo quoi.
(veux pô mourir idiot )

L'algo de l'applet de Sun repose sur le principe dit du "recuit simulé". Il permet de passer outre l'aspect NP-complet, mais par contre, il ne garantit pas qu'on trouve la solution optimale, seulement une assez bonne solution.
 
Le "recuit simulé", c'est quoi ? L'idée, c'est de faire cuire du verre ou du cristal dans un four : on laisse le système de refroidir progressivement. Ce faisant, l'"énergie globale" du système diminue. Puis de temps en temps, on fait rechauffer l'objet par un passage au four, ce qui augmente sa température, donc son "énergie globale", puis on le laisse refroidir à nouveau. On réitère l'opération jusqu'à avoir atteint un niveau d'"énergie" suffisamment bas/stable.
 
Pour revenir à l'applet de Sun, l'"énergie" correspond peu ou prou à la somme des longueurs des arcs, sauf croisement, qui augmente beaucoup l'énergie d'un des arcs croisés. A chaque itération, on perturbe légèrement le système pour globalement réduire la longueur de chaque arc, ou, localement l'augmenter un peu. La somme des longueurs diminue à chaque itération. L'énergie globale diminue. Le bouton "Shake" fait repasser le tout au four (ici très violent : tu pourrais aussi fabriquer un four qui chauffe moins que cela, ou qui chauffe le tout plus progressivement) : en déplaçant les noeuds, il augmente artificiellement la longueur des arcs, donc augmente l'"énergie globale" du système.
A quoi sert la phase de recuit : à sauter les maximum locaux, et donc à sauter de minimum local en minimum local, pour espérer tomber sur un minimum proche du minimum global.

Merci beaucoup   tes explications sont limpides

 
Juste pour ajouter qu'il existe pleins d'autres techniques pour essayer de tailler dans le lard et qu'on peut les combiner etc.
 
Comme dit Aimé Jacquet : "Y'a pas d'méthode". On avise au cas par cas pour choisir la combinaison de techniques.

Faudrait que je regarde dans mes cours, car finalement ca se rapproche enormément des problématiques de modélisation moléculaire que j'ai pu voir.
Par contre, si tu veux une voie originale, pas forcement performante mais intéressante à étudier, il y a les algorithmes génétiques.

C'est pas étonnant, j'ai utilisé des trucs comme ça en traitement de vidéo, en routage électronique et en conception de circuits ! Ca sert vraiment à tout et n'importe quoi.

merci beaucoup les gars, j'atends vos astuces!