Heeeeeeeeelp siouplé !!!

Bonjour tout le monde. Voilà mon problème : je suis stagiaire et il faut que je "programme" le dessin d'un graphe composé de sommets et d'arêtes. J'ai donc en entrée une liste de sommets qui sont reliés entre eux par des arêtes (elles-même contenues dans une liste). Pour chaque sommet il peut y avoir une ou plusieurs arêtes qui y sont reliées. Je voudrais trouver un algorithme qui me permette de placer mes sommets du graphe sur ma page en réduisant autant que possible le nombre d'intersections de mes arêtes. Je dois peut-être vous préciser que certaines arêtes sont orientées mais pas toutes. Je dois donc programmer ceci en C mais je suis prêt à prendre tout ce que vous avez pour m'en servir de base. Si vous connaissez un site sur lequel il y a un algo (ou si vous possédez un algo) vraiment ça m'intéresse. J'en ai vu plusieurs mais à chaque fois je tombe sur des sites où on m'explique vaguement le principe sans trop de détails ! Si c'est possible je suis preneur de tout code réalisant ceci. Merci d'avance et à très bientôt Cédric ;) PS : j'ai déjà posé la question dans la rubrique Maths mais je crois qu'elle est passée inaperçue ! je veux pas surcharger le forum mais j'ai pas le choix, j'ai absolument besoin de votre aide. Merci encore

je crois que la librairie graphique GTK met a disposition un objet GtkCurv ou tu passe en
parametre tes points et il t'affiche un graphe..
apres ça dépend si tu programme sous nux ou doz..

---------------------------------------------------
reset by peer

en fait je ne sais toujours pas sous quel environnement je vais programmer. pour l'instant mon maitre de stage m'a juste demandé de trouver des algo performants avant son retour. L'aspect programmation je verrai plus tard lol! il faut que je trouve un algo qui a déjà fait ses preuves et que je l'adapte à mon problème sans utiliser de fonctions toutes faites de tel ou tel environnement parce que mes arêtes entre mes sommets sont un peu particulières ! Merci pour ton aide en tous cas, si tu as d'autres idées n'hésite pas !

Pour des problèmes d'optimisations comme ceux là, tu as toujours la solution d'appliquer une métaheuristique (de type recuit simulé ou algorithmes évolutionnaires) où ta fonction optimum correspond au nombre d'intersections de ton graphique, et les paramètres les coordoonées de tes sommets, mais c'est très lourd...!

En effet, tu devra calculer l'existence d'une intersection entre chaque couple d'arêtes (ce qui implique de calculer plusieurs produits vectoriels; puis l'intersection) et chercher à minimiser ce nombre d'intersections par ton algo. Tout dépend du nombre d'arêtes, mais rien que pour 10 arêtes tu aura quelquechose comme 45 intersections à calculer à chaque itération, pas très élégant pour un algorithme censé résoudre les problèmes combinatoires...

A oublier si tu as beaucoup d'arêtes donc... je ne vois rien d'autre, mais je suppose que de tels algorithmes doivent exister...

Bon courage..!