Orientation d'un graphe - Page 1

Voila je copie un post que j'ai fait sur tigen

Bon voilà j'ai besoin de savoir si il existe un algorithme capable d'orienter un graphe non orienté :



Le point en bleu est considéré comme le départ et c'est le seul noeud ayant 2 arcs, les autres en ont 3.

On lui donne l'orientation de départ :



et le résultat doit être ca :



S'il vous plaît aidez moi (et si vous pouvez essayez de répondre en langage humain (pas trop de termes mathématiques si possible))

note : le graphe ne contient pas de portions non orientables (cf. ici)

l'adresse du post original est : http://www.tigen.org/pws/forum/index.php?action=sujet&forum=5&cat=115&topic=1559&page=1
pour voir les solutions qui ont déja été proposées.
(j'ai pas encore bien étudié celle de geogeo)

Voici celle que m'a donné Squale92 par mail :

Glop !
après un peu de réflexion, voici peut-être un petit quelque chose qui
pourrait
peut-être te donner quelques idées...

ci-joint, le graphe avec les noms de noeuds

Quand je dis qu'on détermine un lien, ou qu'on l'a, c'est qu'on a
trouvé son
sens.
je marque ça noeud1 -> noeud2

quand je parle de fils, c'est uniquement de fils directs (père/fils ;
PAS
grand-père/fils)


Tous tes noeuds sont non visités au départ
Tu connais le noeud de départ, et tu sais par quel arc tu commences.

Tu pars de Z pour aller à A
=> Tu marques le lien Z -> A et tu met A dans la file (file = A)
Z reste non visité.

Tu es en A. tu l'enlèves de la file (file = )
Tu veux visiter tous les noeuds qui sont fils de A et dont les liens ne
sont
pas déjà marqués.
=> Tu vas aller visiter B et C (tu les met dans une file, qui contient
maintenant B C)
=> Tu fait les liens A -> B et A -> C
Tous les liens touchant A sont définis => tu marques A comme visité.

à présent, les noeuds sur lesquels tu sais comment arriver, mais pas
comment
partir sont B et C.

commençons par B (on le sort de la file : C)
tu cherches à visiter tous ses fils => D (la file contient maintenant C
D)
tu marques les deux liens B -> D

à présent, tous les liens touchant B sont déterminés
=> On traite C (file = D)
les fils de C sont E et F (file = D E F)
=> tu déterminées C->E et C->F
tous les liens touchants C sont définis

On a à présent 3 noeuds en partie traités (on y arrive, mais n'en part
pas) :
D, E, et F

commençons pas D (file = E F)
on visites tous ses fils
=> on a le lien D->L (file = E F L)
On a traité tous les liens touchant D => on passe aux autres qui
étaient non
traités. (il reste E et F)

passons au suivant dans notre file (file = F L)
on est en E , on explore ses fils : I (file = F L I)
on marque les deux liens E->I
E est fini d'être traité => on passe au suivant dans la file

file = L I
on est sur F, on explore ses fils; il a J comme fils (file = L I J)
On marque F->J (les deux liens)
il n'y a plus de liens touchant F qui ne sois pas déterminé
=> on passe au suivant dans la file

le suivant est L (file = I J)
les fils de L sont Z (file = I J Z)
on marque L->Z

suivant dans la file : I (file = J Z)
fils de I est K ; on ajoute K à la file (file = J Z K)
on marque I -> K
on a traité tous les liens touchant I, on passe au suivant de la file

suivant dans la file est J (file = Z K)
on a pour fils de J K
=> On marque J->K est vu que K est déjà dans la file, on ne l'y remet
pas.
on a traité tous les fils de J, on passe au suivant dans la file

suivant dans la file est Z. (file = K)
on a déjà marqué tous les liens arrivant à Z, et tous les liens en
partant
on ne peut donc plus rien faire avec Z
on passe au suivant dans la file

le suivant dans la file est K (file = )
on a déjà marqué tous les liens touchant K
on ne peut donc plus rien faire avec K

la file est vide => on a fini.



En somme, pour résumer

on met le premier noeud de notre parcours (pas celui de départ, donc)
dans une
file
on détermine les chemins entre lui est ses fils direct, et on marque
leur sens
on ajoute ces fils à la file
et tant que la file n'est pas vide, on recommence : on supprime le
premier de
la file, on marque les liens vers ses fils, on ajoute ces fils à la
file, et
on passe au suivant dans la file


enfin, y'a peut-être des cas pour lesquels ça peut foirer, on sait
jamais...
bon courage pour tester

et son graphe joint :

toutes les solutions proposées m'ont l'air d'être un bon début pour la solution mais elle ne sont pas sures à 100%
apparament

Merci à celui qui aura la solution miracle (de preference facile à implémenter )

en fait, y'a un truc qui foire dans ma solution
c'est quand on est en L, comme voisin de L, je n'ai vu que Z... alors qu'il y a aussi K...
et justement, si on considère K comme fils de L (ce qui seera le cas avec mon algo...), ben ça merde

Le problème n'est pas bien défini.

Si tu considères bêtement la piste comme un graphe (non orienté) avec comme noeuds les jonctions de pistes, alors tu vas avoir un paquet de solutions qui ne sont pas ce que tu veux : dans ton exemple, la "première à droite" après le point en bleu pourrait parfaitement être orientée dans l'autre sens, puisque tu n'interdis pas à la piste de faire des angles aigus...

Donc il faut préciser un peu, par exemple en tenant compte de la géométrie de la piste : par exemple deux bouts de pistes qui font un angle de plus de 135° doivent être orientés, l'un arrivant vers le noeud, l'autre partant du noeud. Mais ça reste des hacks un peu crades, surtout que dans un truc comme F-Zero c'est plutôt des tiles organisées de façon géométrique (donc par exemple avec des virages à 90°, ce qui est très ambigu). Donc à moins d'imposer des contraintes un peu grotesques sur tes pistes, tu ne vas pas y arriver.


Moi ce que je comptais faire, pour Formula 0, c'est que l'IA soit pré-calculée sur PC par recherche exhaustive (oui c'est bourrin ), en cherchant tout simplement le mouvement qui minimise le temps jusqu'à l'arrivée (qui, elle, est formée d'une ligne de tiles avec une orientation). A partir de là, on peut orienter la piste facilement en comparant les temps nécessaires jusqu'à l'arrivée... On peut aussi s'en servir pour faire une évaluation de la progression sur la piste ^^

Je ne sais pas comment tu fais ton IA, mais ça me paraît une bonne solution pour avoir une IA un peu "intelligente"... (quitte après à rajouter qques heuristiques on-calc histoire de gérer les chocs, et pour que les données pré-calculées n'aient pas à être stockées en précision maximale)


En fait la méthode de l'IA a l'avantage de tenir compte à la fois des angles entre les pistes et de la distance des arcs du graphe, ce que ne fait pas du tout la méthode que tu proposais ou que tu proposais de chercher...

Bah en fait tu parles de la portion AC (sur le graphe de squale92) ?
je pense qu'il existe une orientation unique pour chaque portion afin que toutes les portions convergent vers l'arrivée sans retour en arriere possible.

je ne compte absolument pas voir les angles faits par les portions a chaque noeud car on peut tres bien tourner pour revenir en arriere (au sens des angles) et pourtant etre sur une route qui mene vers l'arrivée.

En dénombrant tous les chemins qui font un cycle en partant du point de départ et qui y reviennent sans passer 2 fois par le meme arc et en unifiant ces solutions je devrais pouvoir retrouver l'orientation non ?

Pour l'IA je comptais, une fois l'orientation connue, marquer la progression en incrementant des waypoints au fur et a mesure que l'on s'eloigne du point de départ et prendre la plus forte valeur pour continuer l'incrementation lors d'un passage sur un noeud qui a 2 peres.
Les bots essayeraient alors de toujours aller vers la case ayant une valeur plus forte que celle sur laquelle ils se trouvent (en regardant 2 à 3 cases devant eux) de cette manière les chocs sont gérés aussi et les bots ne sont jamais perdus.

Il n'y a aucune donnée précalculée sur mes pistes comme ca je pourrais permettre de faire des pack de pistes entierement oncalc sans avoir a gerer des info autres que le dessin de la piste elle meme.

edit : tu parlais surement du point bleu sur le graphe de geogeo, là aussi il n'y a qu'un sens possible celui qui va du jaune au bleu si on ne veut pas de retour en arriere (j'entend qu'on se rend compte qu'on est reparti en arriere au moment ou on arrive sur le point vert, je ne parle pas des angles)

Bon, si je comprends bien ton problème, tu dois déterminer pour chaque noeud si c'est une séparation ou une union...
ça fait donc 3 cas basiques:
- le noeud est relié à un segment, c'est une séparation, tu peux déterminer le sens des deux autres segment
- le noeud est relié à deux segments dirrigées vers le noeud, c'est une réunion tu peux déterminer la direction du troisième segment
- le noeud est relié à deux segments, mais dont les directions sont de même sens, tu ne peux savoir de quel type de noeud il s'agit
... bla bla ... 3e cas pas bon pour analyse linéaire.... problème pour orienter quelques cas particuliers... etc... bla bla...

Je te propose un algorithme tout bête de recherche de tous les chemins possibles, avec pour seules règles que pour chaque chaque segment ne peut être emprunté qu'une seule fois (donc pour le premier chemin, si sa direction a été déterminée, tu l'oublies ), et que tu t'arrêtes une fois l'arrivée atteinte (évidemment ).
La première fois tu gères cela de manière simple, en prenant par exemple toujours le premier segment lors de divisions...
Par la suite ton but principal est de découvrir de nouveaux chemins, tu peux donc emprunter des segments dont le sens a été défini précédemment
(tout en mémorisant que tu les as empruntés), mais tu dois donner la priorité à de nouveaux segments. Commencer par le début du circuit t'ammènerait à des problèmes trop complexes... Donc il faut prendre le tracé du dernier chemin calculé et choisir le dernier noeud (c à d le noeud le plus proche de la fin dans la liste linéaire des noeuds qui composent le chemin ) ayant toujours une liberté (un segment attaché dont le sens n'est pas encore défini). Partant de là tu suis la même procédure que précédemment, sachant que tu ne peux pas réutiliser le tracé de l'ancien chemin qui précède le noeud utilisé comme point de départ.

Expliqué comme ça ça parraît super complexe, mais ça devrait fonctionner correctement si je ne me suis pas trompé (g pas testé vu que je viens d'inventer ça ^^)

EDIT: Au fait, j'oubliais, pour vérifier si le chemin ne revient pas en arrière il faut faire tt ça par récurrence...

Merci d'avoir proposé des solutions (mais elles sont trop complexes à implémenter avec des files ou des parties récursives)

Voici la toute nouvelle solution que je viens de trouver (elle tue) :

au départ le graphe est non orienté :



on connait l'orientation de deux arcs (ceux accrochés au noeud de départ) :



on propage leurs orientations (un coup celle de l'arc du haut, un coup l'arc du bas), ce qui donne l'évolution suivante :








et voila le résultat

j'ai testé sur papier avec un graphe énorme et ca a marché !

Si vous trouvez une faille dans cette théorie dites le moi vite avant que je n'ai fini de l'implémenter

Merci

Y'a une faille : a la troisieme etape de ton algo, y'a une couille


Au niveau de l'ago recursif de GoldenCrystal, ca donnerai un truc dans le genre :

position = depart

do {

  parcours(position);

  position = orientation_not_set(); //donne une position dont on ne connait pas
                       // le sens d'un arc

while ( potision != NULL );




parcours(position) {

  fils = voisins(position);

  for (int i = 0 ; i < fils.size ; i++) {
     if (fils[i]==depart)  //on a fait le tour
       return TRUE;
     switch (orientation(position,fils[i]) {
       case 0: //arc non traité
         set_orientation(position,fils[i]);
         if ( ! parcours(fils[i]) ) { //echec
           reset_orientation(position,fils[i]);
           continue; //on cherche sur le noeud suivant
         } else { //succes
           return TRUE;
         }
         break;
       case 1: //deja traité et dans le bon sens
               //on a reussi a retomber sur le circuit
         return TRUE;
       case -1: //on irait en sens contraire : noeud suivant
         break;
  }

  if (i==fils.size) {
    //tous les arcs ont été traités, c'est qu'on est revenu en arrière
    return FALSE;
  }

}

Aïe mince tu as as raison

Je vais me pendre, allez adieu !

Bon j'abandonne les complications -> pas de dédoublements imbriqués

./4> mais si tu ne tiens pas compte des distances, tu ne pourras jamais orienter une piste comme ça :

/------\
|      |
^     / \
|    /  /\
|   /  / |
|  /  /  |
\-/--/---/

Je ne comprend pas, même avec mon algo pourri on peut orienter cette piste :

/------\ 
|      | 
=     / \ 
|    /  /\ 
|   /  / | 
|  /  /  | 
\-/--/---/

/-->---\ 
|      | 
=     / \ 
|    /  /\ 
^   /  / | 
|  /  /  | 
\-/--/---/

/-->---\ 
|      | 
=     / v 
|    /  /\ 
^   v  / | 
|  /  /  | 
\-/<-/---/

/-->---\ 
|      | 
=     / v 
|    /  /\ 
^   v  v v 
|  /  /  | 
\-/<-/-<-/

Merde c'est pas ce que je voulais écrire, dsl...

/------\
|      |
^     / \
|    /\  \
|   / |  |
|  /  /  |
\-/--/---/

et c'est pas un pb d'algo, c'est un pb inhérent à la question : si on ignore les distances/angles, on ne peut pas orienter cette piste sans faire des choix arbitraires...

Pollux :
Merde c'est pas ce que je voulais écrire, dsl...

/------\
|      |
^     / \
|    /\  \
|   / |  |
|  /  /  |
\-/--/---/

et c'est pas un pb d'algo, c'est un pb inhérent à la question : si on ignore les distances/angles, on ne peut pas orienter cette piste sans faire des choix arbitraires...

effectivement on peut pas.
Mais un tel graphe est interdit :

note : le graphe ne contient pas de portions non orientables (cf. ici)

Arf oui en effet je n'avais pas vu que c'était un graphe interdit

ya moyen d'orienter le graph mais ça demande une methodologie un peu complexe

Pollux: su un graph simple du genre



on commence par définir les points,
A, B, C D E F G H I J K L Z

et on lui dit ( - = "est relié a" )
A-B, A-C B-D B-D C-E C-F E-I E-I F-J F-J I-K J-K K-L D-L L-Z

aucun notion de distance/angle n'est donné dans ce cas et meme avec ce simple cas (et un peu de recherche) on peu arriver a orienter le graphe, mais ça demande un peu de temps de calcul

On suppose qu'on donne l'orientation du point Z, a savoir ( -> = "va vers" ) Z->A
(colorer en "gris" permet de marquer les noeud on tout les "acces" sont secure)
Donc :
Profondeur 0
Z->A

Profondeur 1
A->B et A->C et on colore A en gris pour le marquer comme sur

Profondeur 2
B->D et B->D et on colore B en gris pour le marquer comme sur
C->E et C->F et on colore C en gris

Profondeur 3
D->L et on colore D en gris
E->I (x2) et on colore E
F->J (x2) et on colore F

C'est ici que les choses se complique
Profondeur 4
L->Z On peu deja colorer Z vu qu'il est ok
L->K (oui on colore L en gris.)
I->K et on colore I
J->K et on colore J

Profondeur 5
La on rentre dans le conflt
a savoir que si on veux on a 1 chemin qui veux aller de K vers L et de K vers I et J mais L, I et J sont coloré donc on se rend compte qu'il y a un pbm.

la plusieurs solutions peuvent etre mises en oeuvre, la plus simple a mon sens serait de regarder a partir de K quel est le plus cours chemin pour mener a Z (a savoir K->L->Z mais ça marche pour cette carte, mais pour d'autre..)

Le meilleur moyen que tu aurait a faire serait plutot que ça soit le concepteur de la carte qui donne la direction sur les liens, du genre ta une "grille" de tile pour faire la carte et une "grille" de direction dans ce cas tu y gagne en souplesse et en rapidité (enfin c'est mon avis )

hibou/lionela> OK, donc on écarte ces cas-là... C'est un peu dommage je trouve ^^

Godzil
: ya moyen d'orienter le graph mais ça demande une methodologie un peu complexe

Ben nan C'est pas une question de méthodologie, c'est juste que y a une piste qu'on pourrait indifféremment orienter dans un sens ou dans l'autre...

Godzil>tu dis ce qu'il faut faire aux premières étapes, mais tu ne donnes pas l'algo... Ce qui fait que ce n'est pas tres juste ce que tu fais, tu incorpores des hypotheses que tu as visuellement, mais qui seraient difficiles à avoir avec un algo.
En fait, dès le noeud C, il y a ambuiguité, car on peut avoir :


Je pense que l'ago que j'ai mis plus haut marche bien. Je pense que c'est ce que GoldenCrystal présentait.

On cherche un premier chemin qui va du depart à l'arrivée : parcours d'un arbre en profondeur et retour en arrière quand on tombe sur un noeud deja visité.

Puis, pour les arcs pas encore orienté, on part d'un arc deja orienté, et on cherche un chemin vers un arc orienté dans le même sens.

Je vais essayé de faire un exemple visuel.

hop :

1-2-3-4 : parcours en profondeur
4 : pb on est arrivé à un noeud déjà vu : retour en arrière et on choisi un autre arc
5 : on continue le parcours en profondeur
6 & 7: re pb de noeud deja vu
8 : on arrive enfin à point de départ.

Puis on essaye de terminer les arcs pas encore orienté. On part de depart, at on va de noeud en noeud afin de chercher le premier arc non orienté: fig 9
10 - 11 : parcours en profondeur jusqu'à trouver un chemin ou y'a des arcs que l'on a precedement orienté.

On reitere l'opération précédente : 12 & 13


En fait mon algo que j'ai présenté est incorrect, celui la est mieux, mais à tester toujours.

parcours1(depart);
parcours2(depart); 
 
parcours1(position) { 
  int fils[];

  fils = voisins(position); 

  if (orientations(position,fils)!=0) //il y a deja une orientation d'établie : on est deja passé par la
    return FALSE;
 
  for (int i = 0 ; i < fils.size ; i++) { 
     if (fils[i]==depart)  //on a fait le tour 
       return TRUE;
     set_orientation(position,fils[i]); 
     if ( ! parcours1(fils[i]) ) { //echec 
       reset_orientation(position,fils[i]); 
       continue; //on cherche sur le noeud suivant 
    } else { //succes 
       return TRUE; 
    } 
  }
 
} 

//recherche de tous les arcs non orienté
parcours2(position) {

  int fils[];

  fils = voisins(position); 

  for (int i = 0 ; i < fils.size ; i++) {
    if (fils[i]==depart) { //on est arrivé
      set_orientation(position,fils[i]); 
      return;
    }
    if (orientation(position,fils[i])==0) { //pas encore fait
      set_orientation(position,fils[i]); 
      parcours3(fils[i]);
    }
    parcours2(fils[i]);
  } 
} 

//etabli un chemin, sachant qu'il existe deja des arcs orientés
parcours3(position) {
  int fils[];

  fils = voisins(position); 

  if (orientations(position,fils)!=0) { //il y a deja une orientation d'établie
    if (existe_chemin_orienté_vers_depart(position))
      return TRUE; //un chemin existe, on a reussi
    //il n'en existe pas : on est en fait revenu sur nos pas
    return FALSE;
  }

  for (int i = 0 ; i < fils.size ; i++) {
    set_orientation(position,fils[i]); 
    if (parcours3(fils[i]))
      return TRUE; //succes
    //echec
    reset_orientation(position,fils[i]);
  }

  //aucun fils n'a marché, echec
  return FLASE;
}