Reprise du message précédent :

euh... non, je sais pas ce que vous avez tous avec ce truc (ça doit faire 3 fois qu'on en parle ici) mais ça n'a rigoureusement rien à voir... Il cherche absoluement pas le chemin qui passe par tous les points sans passer deux fois par le même... il demande juste comment faire en sorte que le graph ait le moins de chevauchement possibles...

 
Peut etre pas le "moins possible", mais simplement obtenir un résultat pas loin de l'optimal !
 
Je ne pensais aps que ce serait aussi chaud !!

Ton problème, c'est typiquement ce que l'on peut trouver dans orcad ou tout autre soft du genre : c'est un problème de routage de circuits imprimés.
 
Bien que j'aime bien les algos génértiques, je pense pas qu'ils soient super efficaces pour résoudre ce genre de pb. Un algo exacte existe et je pense qu'il repose sur la théorie des graphes. Mais alors, lequel? J'en sais rien un algo de b-couplages peut-être? A voir... Mes cours de graphes sont loins.

Un algo exact? Tu veux dire "qui donne à chaque fois la meilleure réponse"? Non, y en a pas de comme ça, vu que le problème est NP Complet! Je cherche juste quelque chose d'acceptable, mais j'ai baucoup de mal à trouver de la littérature sur le net là dessus ! (à part une applet Java, mais elle ne prend pas en compte les intersections des arêtes)

tu n'a pas besoin de prendre en compte le nombre d'intersectections des arêtes entre elles, ça ne nuit pas vraiment à la lisibilité d'un graphe sauf s'il se confondent.
 
-pose toi d'abord la question de comment tu envisages "quelque chose d'acceptable" pour l'exemple d'un graphe complet (tout noeud est relié à tout noeud)
 
-si c'est dans le cadre d'un TP d'info (dans ce cas précise ton niveau d'étude !, si tu veux des réponses adaptées...), essaie de créer des fonctrions de distribution basées sur tes procédures de parcours de graphe : ça permet de produire des résultats souvent acceptables (cf mes screenshots ; 1: distribution circulaire avec parcours en profondeur; 2: distribution arborescente avec parcours en largeur)

 
Moi, je pense que ton pb est polynomiale...
 
Sinon, comment Intel arrive à graver ses CPU avec des millions de transistors et qui sont reliés entre-eux par des pistes qui ne se coupent pas (bon, oui, le cpu est aussi en plusieurs couches, mais dans ton cas, nb couches = 1)...

 
Non, non, ce n'est pas dans le cadre d'un TP d'info, mais plutôt d'un petit programme que je cherche à créer pour un ami. Pour ce qui est de mes études, j'ai fait une école d'ingé (Supélec), section informatique.
 
Pourrais tu un peu préciser tes idées? A quoi ça peut me servir de parcourir mon graphe (que ce soit en largeur ou en profondeur?)
 
Bien sûr que la qualité esthétique/de visibilité de l'arrangement de mon graphe est quelque chse de subjectif, mais si je parle de croisements d'arêtes, c'est parce que j'ai souvent lu que c'était un critère principal (et c'est vrai que lorsqu'il y a trop d'arêtes qui se croisent, c'est un peu le "bordel" ). En fait, ce qui d'érange kle plus, c'est quand y a des arêtes qui passent par dessous les sommets (genre un sommet qui n'a rien à voir ce trouve en plein sur une arête)
 
Encore une fois, mon but n'est pas de trouver LE placement optimal mais qqchose d'acceptable ! C'est pourquoi ton idée peut m'intéresser (par contre, je n'ai aucune donnée sur le niveau de "complétude" de mon graphe, c'est àdire que je ne connais pas le "taux d'arêtes"
 

 
 
Bah Intel place peut etre des millions de transistors sur ses procos, mais n'empêche que la façon dont ils sont agencés et reliés entre eux n'a rien d'aléatoire. Au contraire, ce sont des séquencess qui dovent se répéter. Ils ont des logiciels spécifiques pour faire ça!
 
D'autre part, le fait de disposer de plusieurs couches résout beaucoup de problèmes...
 
La résolution de mon problème est exponentielle, y a aucun doute là dessus (même si je sais que mon graphe ne fera jamais plus de 20 sommets...mais c'est déjà beaucoup)!
 
Je n'ai pour le moement aucune idée de savoir comment faire! J'ai trouvé des articles sur le net, mais à chaque fois, y avait pas de contenu détaillé (donc, pas d'algo en vue)
 
Concernant le recuit simulé, j'ai envie de tenter cette voie, mais je ne sais pas encore comment m'y prendre !

et si tu biaises en représentant la relation de couverture, le diagrame de Hasse quoi...tu réduis les chevauchement au minimum...mais peut etre ca rentre pas dans ton cahier des charges (vu que c plus la relation de base qui est décrite par le graphe)...c carrément au dessus de mon niveau, mais je propose les idées qui me viennent...
 
pas taper svp

 
C'est vrai que les transistors ne sont pas agencés au hasard. Mais si j'ai bien compris le problème qui est posé dans ce topic, les liens qui relient les sommets ne sont pas dû au hasard non plu. Donc, on pourrait assimiler les sommets à des composants électroniques et les liens qui les relient entre-eux à des pistes. Maintenant, faudrait arriver à trouver sur le web un algo de routage...

Bah dans mon appli, les liens ne sont pas là au hasard, mais vu que ces liens dépendent de facteurs humains, on pt considérer qu'ils sont aléatoirement placés (ainsi d'ailleurs que le nombre de sommets, qui est aléatoire!)
 
Pour le moment, je me fait une petite routine qui calcule le nombre de croisements !
 
Mais je cherche, je cherche pour l'algo de placement !  
 
Je sais que ce genre de boulot a déja été fait, genre le travail qui s'appelle "Drawing graphs nicely using simulated annealing" de Davidson et Harel! Le problème, c'est que je ne trouve nulle part de version électronique de ces travaux! Simplement, je sais que ça utilise le recuit simulé!
 
Si vous avez des pistes, n'hésitez pas !

Au fait, tes liens entre 2 sommets, ils sont forcément droits ou ils peuvent être coudés (un lien = plusieurs segments de droites)?

Bah a priori, ils sont droits. Si ca peut améliorer la lisibilité, pkoi pas coudés, mais on va dire "droits" quand meme !

Bah a priori, ils sont droits. Si ca peut améliorer la lisibilité, pkoi pas coudés, mais on va dire "droits" quand meme !

Je sais pas ce que ça vaut comme idée, mais est-ce-que ça serait pas bien de définir une grille virtuelle où une case ne peut contenir qu'un objet (un sommet ou un bout d'un lien). Ensuite, on applique l'algo du plus court chemin pour relier les sommets entre eux tout en faisant attention à ne pas passer par une case déjà occupée. Si l'ago échoue, alors on autorise à couper 1 case, et si ça échoue à nouveau 2 cases,... et ainsi de suite... Par contre, tes liens seront coudés.

Oui, y a de l'idée, mais par contre... :
- Pour l'algo des plus courts chemins, il fo quand meme que le nombre de chemins soit "petit" (les chelins étant des arcs), or ici, il est tres tres grand (toutes les combinaisons possibles....)
-Pour appliquer ton algo, il fo déja que les sommets soient placés sur le graphe... Or, pour ma part, justement, je vx que l'ago le fasse à ma place (ca lui facilite quand meme la tache)
-Finalement, cet algo se baserait uniquement sur une minimisation des longueurs des arcs, et donc, pas du tout sur une minimisation des croisements de ceux ci ! En fait, sur le lien Java donné plus haut, y a déja un algo de recuit simulé (ou du meme genre), permettant de minimiser les longueurs des arcs, ou plutot de ramener autant que faire se peut cette longueur à la longueur choisie par l'utilisateur (mais cet algo ne prend absolument pas en compte le nombre de croisements)
 

T'as essayé mon truc ou pas ?

A vrai dire, je n'avais pas replongé dedans! Vu que l'implémentation de ton truc ne sera pas facile, je préfère d'abord réessayer usr des exemples concrets et à la main!
Si je vois que ça marche, alors, oui, je l'implémenterai !
 
Par contre, dans ton algo, j'aimerais que tu rendes les choses un peu plus déterministes, car je me rends compte que quand je l'essaie à la main, on est souvent amenés à faire des choix, et on fait ces choix au feeling, et peut etre que c pour ca qu'il rend bien! Les hoix devraient etre faits par l'algo !

A quels niveaux ?
 
Poste-moi un exemple qui demande un choix "au feeling" que je regarde ça.
 
Sinon, je pense que ces choix peuvent être améliorés avec une courte passe du truc recuit machin. En effet, je suppose que c'est la façon de positionner les noeuds autour du noeuds père que ça coince... A priori, avec le système de poids, ça doit pas trop mal marcher, mais à la main, on a en effet facilement le problème des noeuds qui se chevauchent. A ce moment, un coup de recuit devrait permettre d'équilibrer l'occupation dans l'espace et résoudre ce problème. Il doit y avoir d'autres solutions plus aisées pour faire ça, il faudrait que je parte d'un exemple.

>Histoire de placement de noeuds et de liens...
A ne pas confondre avec les placements de lieux et de nains...
A+,

mais c'est un festival

 
Des codes de recuit simulé, ça doit se trouver, cherche "Metropolis", par exemple. Il te "suffit" d'étudier le code et de l'adapter à ton problème, essentiellement, cela consiste à trouver une bonne fonction de coût(genre, minimiser les croisements et les distances, un truc comme ça), et à optimiser le truc pour qu'il converge pas trop lentement. Sinon, tu peux commencer par étudier le code des applets java, elles sont plutôt bien foutues et elles font ce que tu veux. En y incorporant les idées de MagicBuzz, tu dois pouvoir pondre un code relativement efficace. (j'ai pas dit que c'était facile)