Graphes et ordonnancement

Le dredi sexy, supplanté par le dredi matheux. Voila un petit problème sur lequel je planche et pour lequel je ne refuserais pas un coup de main.

J’ai un graphe, représenté en mémoire par une matrice d’adjacence pondérée, i.e. une valeur non-zero dans la case (m,n) de la matrice indique une arête du noeud m vers le noeud n, avec une valeur entre 0 et 1.

Exemple:

Mon objectif: en supposant qu’il n’y a pas de cycles, trouver un algorithme pour ordonner les noeuds sous forme d’arbre dirigé et, du coup, établir une liste de précédence de calcul de chacun des noeuds.
Dans l’exemple trivial, l’ordre est [1, 2, 3].

Je suis intéressé par toute solution: bout de code, algorithme, librairie externe, litterature matheuse…

1er tiroir:
S’il y a des cycles (et il y en aura), possible de les isoler, et de les insérer dans la liste comme un noeud a calculer a part entiere ?

2eme tiroir:
Si je vous dis “temps réel” ? Le graphe pourra etre édité en temps réel par l’utilisateur. Imaginez des potards a la place des valeurs de la matrice, et vous avez l’idée. Donc, on doit pouvoir recalculer l’ordre rapidement, souvent et pour pas cher.

Toutes les bonnes idées sont acceptées!

EDIT: Le probleme en question s’appelle le Topological sorting. Question principale résolue, ce qui n’empeche pas de continuer a discuter du sujet. Il reste les histoires de cycle…

J’ai regardé ça : http://perso.ens-lyon.fr/eric.thierry/Grap…n-panhaleux.pdf

Je pense qu’il faut détecter les cycles avant, et trouver l’arrête qui cassera le cycle, et l’enlever.
Mais il peux y avoir des cas où faudra enlever plusieurs arrêtes.

Et ensuite tu pourras faire ton tri topologique.

Sinon je vois que le tri topologique fait appel au parcours en profondeur, et je pense que tu peux détecter les cycle ici, et supprimer les arrêtes, avec un genre de back track.
Si t’arrive a un nœud déjà marqué à l’aller et au retour alors tu supprimes la dernière arrete qui va vers ce nœud (mais je suis pas sur, c’est juste un idée)

Mais en supprimant les arrêtes tu vas perdre les propriétés du graphe de départ. Mais si tu fais de l’ordonnancement, et que les arrêtes sont des dépendance et que t’as un cycle, ça veut dire que t’as un cas poule - oeuf, et que tu peux pas vraiment choisir d’où partir…

J’ai aucune idée du temps d’exécution d’un tel algorithme. Mais tout les algos sont O(|S| + |A|) Faut voir si la modification du parcours en profondeur est pas trop compliquée. Donc je pense que ça faut le coup de coder et voir après. (Pour ton 2eme tiroir)

Si la matrice suivante est autorisée, tu risques d’avoir un problème avec tes cycles, donc faudra modéliser ton problème autrement ou bien rajouter quelques limites…:slight_smile:

[codebox]0 a 0 b 0
0 0 c 0 0
0 0 0 d e
0 f 0 0 g
h 0 0 0 0[/codebox]

Je pense que la Boost Graph Library peut grandement t’aider pour ton probleme…