Salut!
 
Voilà, pour les pros de l'algo et/ou de maths, j'ai un problème à régler (je ne suis même pas sûr qu'il y ait une solution). Tâchons de faire simple.
 
Je dispose dans mon programme de noeuds (N1, N2, N3, etc...) et de liens (L1 (entre N1 et N3), L2 (entre N2 et N3), L3 (entre N15 et N8))
Nous supposerons que les liens sont uniques (cad que 2 liens ne peuvent pas contenir la même paire de noeuds) et unidirectionnels (cad que N1-N2 est considéré équivalent à N2-N1)
 
Voilà! Disposant de tous ces noeuds et de tous ces liens (certains noeuds pouvant etre affectés à plusieurs liens vers divers noeuds), je chercherai à placer tout celà à l'écran, de la "meilleure" manière qui soit, sachant que mes critères peuvent être par exemple :
- le moins de croisement de liens possible
- éviter au maximum que des liens passent par dessous de noeuds (par exemple, qu'à l'écran, le lien entre N1 et N2 passe par dessous le noeud N3) - On a qu'à considérer que les noeuds seront représentés par des cercles de rayon n, ou alors, pour simplifier, par des points!
 
Voilà... Vous connaissez à peu pres mon probleme! Donc, je voulais savoir si vous connaitriez ou pourriez imaginer un algo pouvant m'aider (je ne demande pas que tout soit parfait, mais au moins un algo qui puisse me proposer un placement meilleur qu'un placement fait au hasard)
 
Merci

C'est très certainement une connerie mais bon...
 
 
function PlacerNoeud(Noeud, Graph, x, y, r)
    Si Noeud.DejaPlacé alors quitte fonction
    Sinon Noeud.DejaPlacé = true
    Placer noeud en x, y
    ArrayDeNoeuds = Rechercher tous les noeuds accessibles en un seul lien, et avec DejaPlacé = false
    Pour chaque ligne de ArrayDeNoeud
       Calculer x1 et y1 afin qu'ils représentent un point sur un cercle autour de Noeud de rayon r, répartis homogènement entre les noeuds.
       PlacerNoeud(ArrayDeNoeud[enCours], Graph, x1, y1, r/2)
    Fin Pour
Fin PlacerNoeud
 
Avec ça, tu devrais avoir un minimum de chevauchements.
 
Par contre, ça va pas être beau.
 
Il doit y avoir mieu. Pour rendre le truc plus beau, tu devrais pouvoir ensuite faire un scan de l'écran pour repositionner les noeuds sur une grille régulière.
 
PS: mon algo est loin d'être infaillible, je suis même pas sur qu'il est efficace du tout

M'enfin en y réfléchissant bien, il me semble assez logique... Puisqu'il positionne les uns à côté des autres les noeuds qui sont les plus proches. Seul problème, c'est si les noeuds sont beaucoup liés entre eux, mon algo devient complètement foireux, car la répartition en cercle ne suffit pas, il faut aussi tenir compte d'un "poids' correspondant aux noeuds voisins déjà placés, afin que le noeud soit le plus près possible d'eux (sur le cercle)
 
Je sais pas trop si tu vois ce que je veux dire...

Mon algo donne ça :
 

 

 
Il est donc tout à fait perfectible
Mais c'est quand même moins le bordel qu'au départ

J'ai l'impression que si tu fais une amélioration basique à cet algo, tu pourras obtenir un meilleur résultat.
 
Au lieu de partir bêtement d'un noeud au pif, recherche le noeud qui a le plus de liens.
 
Puis lors de la recherche des noeuds liés, trie-les selon leur nombres de liens.
 
Et enfin, lors de la recherche de x et y, prends en compte la direction des noeuds liés déjà positionnés.
 
A priori, ça devrait aller beaucoup mieu.

C'est un algo NP complet, ce qui veut dire que trouver la solution est très bourrin.
 
Il faut donc utiliser des techniques à la con comme des Montecarlo, des histoire de relaxation de l'énergie etc. Bon courage.

Et un petit algorithme génétique ?

vu la taille du génome, c'est pas gagné.

 
Merci pour tout le mal que tu t'es donné!
 
A vrai dire, le coup du r/2 me fait extrêment peur. D'une part, j'ai peur que l'on y voie plus rien, car au fur et à mesure que tu avance en profondeur dans l'algo (genre, essaie d'imaginer que tu as une chaîne simple, genre A->B->C->D->E...) les noeuds finissent par tous se retrouver les uns sur les autres... (car le rayon suit une suite géométrique de raison < 1). D'autre part, je ne suis pas sûr que cet algo donne quelque chose (ou en tout cas, je pige pas comment il pourrait répondre au probleme)! Je vais le réxaminer.
 
Sinon, j'avais eu une prof y a quelques années en théorie des graphes, j'ai pu retrouver son mail et je viens de lui soumettre le problème.... En espérant qu'elle y réponde Je vous tiendrai au courant! Bien sûr, si on pouvait résoudre mon problème ici même, ce serait encore mieux !
 
Pour ce qui est des algos génétiques...euh...?
 
Sinon, pour la ocmplétude, bah...je me rappelle plus trop ce que c'est qu'un problème NP Complet. Mais je veux biene xplorer des pistes si vous en avez !
 
Merci bien en tout cas!
 
PS : MagicBuzz => Bravo pour tes dessins

L'algorithme génétique est parfait pour ce genre de situation : il s'agit d'optimiser quelque chose, et on ne connait pas de methode precise pour y arriver. En très gros, il s'agit de mimer le mécanisme de la sélection naturelle : on représente nos données (par exemple ici la position des différents noeuds) sous formes de "genes". Ensuite on fait "muter" ces genes de façon aléatoire. A chaque "génération" ainsi obtenue, on conserve les génomes les plus adaptés, c'est à dire ceux produisant un résultat se rapprochant le plus possible du résultat "parfait".
C'est quelque chose de très simple à mettre en place, et qui peut donner de très bons résultats. Les principaux obstacles sont que :
1/ ça peut être très lent.
2/ Il faut trouver la mnbière la plus adaptée de représenter les données  à optimiser
2/ Il faut être capable d'évaluer la qualité d'un résultat donné.

Bah le coup du r/2 c'est juste pour pas avoir à gérer la superposition des noeuds. Mais évidement, tu peux t'en passer.
 
Sinon, le but de mon algo (qui sera certes pas efficace dans un certain nombre de cas, mais c'est déjà mieu que rien, surtout qu'il est simplissime) c'est de dégrossir. Ensuite, il vaut mieu de toute façon faire une passe afin de remettre les noeuds sur une grille régulière comme je l'ai déjà dit. Un petit algo bien sympa à pondre encore Grossomodo, on algo se contente de tenter de débroussailler le bordel ambient, en démêlant un certain nombre de noeuds vraiment trop flagrants, sans gérer la présentation

Ah ok ? C'est juste ça ? Comment tu viens de tout démystifier dans mon esprit là
 
C'est simplicimement bête comme truc en fait !
(enfin, chacun des 3 points noirs de ce système sont évidement autant de problèmes de substitution au problème original qui ne manqueront pas de le remplacer avantageusement )
 
M'enfin moi je préfère la méthode classique pour trouver un algo : observer et reproduire... Le plus chaud, c'est que quand à la base t'en ch*e pendant deux heures pour résoudre le problème avec ton cerveau normalement, bah t'as un peu de mal à l'expliquer ensuite sous forme d'algo... Et l'arrangement de graph rentre tout bien dans ce critère En tout cas, ça mériterait d'être posé en sujet de projet en bac + 2, y'a de quoi se prendre la tête, mais je pense que c'est bien plus simple qu'il n'y paraît (sans fausses prétententions)

C'est toute la force de la chose

 
En gros, ton algo, c'est "je commence par le premier noeud" et ensuite, tu procède par propagation, cad qu'au lieu de placer les noeuds au hasard, tu procède à la "queue leu leu". Et tu fais la meme chose pour chaque partie convexe du graphe.
 
Sinon le coup de l'algo égéntique me plait bien (j'avais déja entendu parler de ça) mais j'ai quand même besoin de plus de précisions pour pouvoir creuser cette voie. Déja, est ce que mon probleme se prete bien à ce genre d'algo? Ensuite...je me lance comment?
 
En tout cas, j'ai bien l'impression qu'il fo y aller un peu comme un bourrin (mais bien sûr, le fait de bien partir en sélectionnat directement les bons sommets avec lesquels commencer) peut éviter bien des galères...

Et la place mémoire prise par une génération dans le cas d'un génome aussi gros.

Dans le principe, ton problème se prete tout à fait à l'algorithme génétique. Le problème c'est que pour un nombre de noeuds important, les perfs vont vite devenir tres mediocres.
 
il existe des techniques plus déterministe, par exemple celle du "recuit simulé" (enfin mon prof l'appelait comme ça). Le principe est aussi simpliste : tu commences par disposer tes noeuds de manière aléatoire. Ensuite, tu déplace tes noeuds en fonction de leurs affinités les uns pour les autres : les noeuds liés s'attirent, les noeuds non liés se repoussent. Au bout d'un certain nombre d'itérations, le système va tendre vers un optimum. Après, à toi d'ajouter des contraintes pour éviter par exemple le chevauchement de noeuds...

aussi. Ca depends du nombre de noeuds.

Sinon, juste comme ça... Je viens de "rejouer" mon algo modifié avec la pondération par poids en fonction des éléments déjà en place, et mine de rien (bon, c'est peut-être un coup de pot ) il marche à 100%
 
Y'a juste qu'il faut prendre en compte que si :
A est lié à B
B est lié à C
A est lié à C
 
Il ne fait pas mettre B entre A et C, mais le décaller sur un côté. A priori, ça doit être faisable sans trop de difficulté.
 
Bon, j'ai quelques exemples en tête qui font que l'algo est loin d'être infaillible, mais tout de même, je trouve qu'il s'en sort plutôt bien pour un truc réfléchit en 5 minutes...

Y'a un peu de ça dans mon truc

T'ain y marche carrément bien mon truc en fait !
 

 

 

 
PS: désolé, y'a que 9 noeuds, donc ça simplifie le problème, mais à la base, j'ai pas envie d'y passer la nuit non plus

PS: ok, j'ai utilisé quelques trucs visuels en plus de l'algo. Mais je n'ai pas anticipé son fonctionnement par contre, j'ai bêtement suivi l'algo à la lettre, juste pour placer les nouveaux noeuds, j'ai fait en sorte qu'ils ne se chevauchent pas, mais ça doit être "relativement simple" à programmer de toute façon.
 
PS²: merde, j'ai oublié de mettre le lien entre C et F (mais ça change rien au final)
 
 
Donc, l'algo "complet" :
 
function PlacerNoeud(Noeud, Graph, x, y)  
    Si Noeud.DejaPlacé alors quitte fonction  
    Sinon Noeud.DejaPlacé = true  
    Placer noeud en x, y  
    ArrayDeNoeuds = Rechercher tous les noeuds accessibles en un seul lien, et avec DejaPlacé = false  
    Trier ArrayDeNoeuds par nombre de liens sur les noeuds, décroissant.
    Pour chaque ligne de ArrayDeNoeud  
       Calculer x1 et y1 afin que :
          - Si ArrayDeNoeud[enCours] est lié à d'autre noeuds, il est placé temporairement aux centre de gravité des noeuds liés.
          - Sinon il est n'importe où là où c'est libre, assez loin de Noeud (constante d)
          - Modifier x1 et y1 de façon à ce que le noeud en cours et ses liens actuellement affichables ne chevauche pas d'éléments éxistants (truc le plus dur à faire certainement). Si on peut pas, le détecter, et poser comme une merde le noeud à la position initiale (foutu pour foutu...)
       PlacerNoeud(ArrayDeNoeud[enCours], Graph, x1, y1)  
    Fin Pour  
Fin PlacerNoeud  
 
Faudrait tester avec plus de noeuds et des pièges, mais à priori, ce système semble plutôt bon.

MagicBuzz résout en quelques heures un problème sur lequel des gens planchent depuis 40-50 ans. Qui l'eu crû ?

Pas résolu
 
Mais en tout cas, un truc potable qui offre un taux de résolution acceptable.
 
Après évidement, il y a des pièges, mais il y a aussi de toute façon des cas où c'est irrésolvable...
 
A lié à B, C ET D
B lié à C, D ET A
C lié à D, A ET B
D lié à A, B ET C
 
Tu pourras tourner dans tous les sens, c'est irrésolvable.
 
Donc à partir de là, il n'y a pas d'algo ultime pour résoudre le problème. Donc un algo qui marche avec un nombre limité d'erreurs, et une rapidité imbattable (t'iras me trouver un truc plus simple toi ) c'est déjà pas mal. C'est toujours mieu qu'un algo génétique qui va prendre 20 heures pour au final capituler avec un nombre d'erreur qui sera peut-être pas inférieur sur un graph avec un grand nombre de noeuds

Je suis MDR
Ahaha, MagicBuzz excité
Bon, la nuit porte cnseil, mais promis, demain, j'essaie à la main ton algorithme, voir ce que ca peut donner. C'est vrai que ça devient vite prenant ces trucs là !

Comme ça a été dit, c'est NP complet.
Ca s'apparente au problème du voyageur de commerce (trouver le chemin le plus court entre N villes données).
 
Pour ça, il y a l'algo du recuit simulé (simulated annealing). Une petite recherche sur google s'impose.
 
J'ai pas regardé l'algo de MagicBuzz, mais si ça marche, autant l'utiliser, ou un mix de recuit simulé et de magicbuzz.

Salut MagicBuzz...
 
Dans ton algo, à un moment, il y a une zone de flou. Quand tu dis :
 
Si ArrayDeNoeud[enCours] est lié à d'autre noeuds, il est placé temporairement aux centre de gravité des noeuds liés.
 
Ce que tu appelles les "autres  noeuds", c'est "tous les noeuds non encore placés" ou alors "tous les noeuds tout court, meme ceux qui ne sont pas encore placés"? ou alors meme "seulement les noeuds déja placés".  
 

Si A est lié à B, C, D, E, alors on place A au centre de gravité de ces points (s'ils sont déjà positionnés, sinon ils n'entrent pas en ligne de compte évidement)

D'accord c'est ce dont je viens de me rendre compte en suivant ton exemple! Sinon, juste piur ton info, tu as oublié de lier C à F, mais bon, dans ce cas là, ça ne crée pas de problème.  
 
Enfin, y a un truc de non précisé dans ton algo, c'est que si un noeud que tu es en train de placer est déja lié à deux autres noeuds déja placés, alors il fo non pas le mettre au centre de gravité, mais disons à un point tel que les trois noeuds forment un triangle isocèlé...
 
PS : Tu utilises quoi comme soft pour faire tes petits dessins? Visio?

Nan, j'ai pas installé Visio, PowerPoint c'est moins bien mais ça marche aussi
C'est la version 2003.
 
Sinon, C et F, oui, je l'ai dis hier quand je m'en suis apperçu

Sinon, pour le coup du triangle, oui, j'avais un peu du mal à expliquer le truc. En fait, faire un triangle ne suffit pas. Il faut aussi tenter de trouver une position qui ne provoque pas de chevauchement. C'est je pense la partie la plus chaude de l'algo. Enfin, peut-être pas, mais j'ai aucune expérience "graphique" au niveau programmation, donc détecter que deux lignes se croisent, j'en suis tout bonnement incapable (mais à priori, c'est relativement basique )

Y'a deja eu des topics similaires :
http://forum.hardware.fr/forum2.ph [...] 0&subcat=0
http://forum.hardware.fr/forum2.ph [...] h=&subcat=
 
et ce lien interessant :
http://java.sun.com/applets/jdk/1.1/demo/GraphLayout/
 

 
Ca ressemble à ce que disait R3g ... chaque noeuds se repoussent si ils sont trop proches et ceux qui sont liés s'attirent quand ils sont trop éloignés. Ca marche plutot bien ... mais apparement ca bloque dans des situations un peu complexes (genre le dernier exemple).

jveuh aussi poster des captures  


 
j'espère que ça te donnera des idées

R3g : pour ton explication sur les algo génétiques, tu oublies le point le plus important : à chaque génération il n'y pas seulement une phase de « mutation » (où les « gènes » sont modifiés de façon aléatoire), mais aussi (et surtout) une phase de « croisement » ou les gènes des deux parents sont mélangés pour donner un nouveau gène unique : ni celui du père, ni celui de la mère, mais tenant un peu des deux. En gros a chaque génération on a donc :

• Sélection des individus a reproduire (avec des chances proportionelles a leur « performance »)
• Croisement des individus deux a deux (« crossover ») pour obtenir un nouvel ensemble d'invidus fils
• Mutation aléatoire des nouveaux gènes

Après il peut y avoir des variantes : plutôt que de « tuer » tous les parents on peut, par example, essayer de garder à chaque génération les N individus les plus performants.
 
Avec les algo génétiques il y a en gros deux difficultés :

• Le choix de la fonction qui déterminera la « performance » d'un individu. Dans le cas qui nous intéresse, ça pourra être le nombre de croisements des liens par exemple (qu'on cherchera donc a minimiser)
• Le codage d'une solution sous forme de « gène ». Dans notre cas ce sera le plus gros problème. Il faut trouver une manière de coder tes graphes sous forme de « gènes » de façon à ce que le croisement de deux gènes donne un nouveau graphe qui ressemble un peu à chaque parent...

Bon, je crois qu'il fo commencer par le début, cad une foncion d'évaluation d'un graphe.
 
Le plus simple pour le moment va être, slon la configuration obtenue, de calculer le nombre de croisements.
 
D'où le problème préliminaire :
 
Sachant que l'on a deux segments [AB] et [CD] avec A(xa,ya), B(xb,yb), C(xc,yc) et D(xd,yd), quelle est la méthode la plus rapide pour savoir si ces deux sgements se croisent?
 
Mon but est bien entendu de savoir si ils se croisent, sans nécessairement avoir à calculer l'intersection (enfin, mon but : le faire le plus rapidement possible)

"Le plus simple pour le moment va être, slon la configuration obtenue, de calculer le nombre de croisements."
 
mais pas forcément la plus simple à optimiser ^^
 
une idée supplémentaire : tester le chevauchement boule/segment
                          qui nuit bien plus (dans une premier temp) à la lisibilité du graphe qu'au nombre de croisements entre segments.
 

 
une solution élégante vient de me traversé l'esprit mais je dois partir; là.

hum la théorie des graphes ...
 
Mais ce qu'il demande c'est pas ce que certains appellent le syndrome du facteur chinois, ou le pb du représentant de commerce ?
 

 
Bah ce qu "il" demande (le "il", c'est moi), ce n'est pas exactement le problème du voyageur de commerce, non. Maintenant, le problème du voyageur de commerce peut se résoudre de "manière acceptable" avec le recuit simulé! Donc, je me demande si je ne vais pas pouvoir faire pareil avec mon problème, mais ça me parait quand même assez dur à formaliser!
 
je cherche, je cherche...

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...